To improve error correction when errors occur in consecutive bits of user data, the user data can be stored in an interleaved manner. Data of a data unit can be interleaved to generate a permutated data unit. A checksum of the permutated data unit can then be calculated, and an error correction code can be generated over the data unit and the checksum. The error correction code can also be interleaved to generate a permutated error correction code. The permutated data unit, the checksum, and the permutated error correction code can then be concatenated to generate a storage data unit for storage in a memory.