Interleaved Forward Error Correction (FEC) encoded data from multiple FEC encoders for transport over a multi-channel physical transport medium, with cyclical rotation of the FEC encoded data bytes across transport channels in a given transmission interval as well as across time within each transport channel. A plurality of parallel FEC encoders are used to generate respective parallel FEC-encoded data streams, the outputs of which are then interleaved across a plurality of transport channels in a given transmission time interval, and, within each transport channel, the interleaved order varies over the time intervals.