A data storage device is disclosed comprising a non-volatile storage medium (NVSM). A first block of data is channel encoded into first channel data based on a channel code constraint, and the first channel data is error correction encoded to generate first redundancy bits. A second block of data is channel encoded into second channel data based on the channel code constraint and the first redundancy bits, and the first channel data and the second channel data are error correction encode to generate second redundancy bits. A third block of data is channel encoded into third channel data based on the channel code constraint and the second redundancy bits. The first, second and third channel data and the first and second redundancy bits are stored in the NVSM.