Error resilient methods and apparatus for coding, transmitting and/or storing digital multimedia data are disclosed. Digital multimedia data is organized into channel blocks, which include columns of data. A priority is determined for each channel block, based on the data within the channel block. Different forward error correction (FEC) procedures may be selected for the channel blocks based on their priority. Also, channel blocks may be transmitted on different transmission channels, and/or stored on different storage elements, based on their priority. Also disclosed is the coding, as pre-interleaved channel blocks, of digital multimedia data having fixed-length segments. The fixed-length segments are ordered and arranged in pre-interleaved channel blocks containing rows and columns. Pre-interleaving of a channel block arranges consecutive fixed-length segments along its columns. FEC data is determined for each row and included in the channel block. The channel blocks are packetized along the columns.