A data storage device is disclosed comprising a non-volatile storage medium (NVSM), wherein a plurality of codewords and corresponding parity sector are written to the NVSM and then read from the NVSM. Each codeword read from the NVSM is processed using a Viterbi-type detector, thereby generating codeword reliability metrics. The codeword reliability metrics for at least some of the codewords are processed using a low density parity check (LDPC) type decoder, thereby generating a LDPC reliability metric for each symbol of at least one codeword. The LDPC reliability metrics for at least one of an un-converged codeword are processed using the parity sector, thereby updating the un-converged codeword reliability metrics. Processing the codeword reliability metrics with the LDPC decoder and updating the reliability metrics with the parity sector is repeated at least once before updating the LDPC reliability metrics of at least the un-converged codeword using the Viterbi-type detector.