A method includes accepting input including at least part of a codeword that has been encoded by an ECC defined by a set of parity check equations. The codeword includes data bits and parity bits. A decoding process is applied to the codeword using the data bits and only a first partial subset of parity bits in the input, and using only a second partial subset of equations. Upon a failure to decode the codeword using the partial subsets, the codeword is re-decoded using the data bits and all parity bits in the input, and using all equations. The set of parity check equations is defined such that any parity bit in the codeword appears in multiple equations, and any parity bit in the first partial subset of the parity bits appears in a plurality of equations in the second partial subset of the equations.