Nested LDPC encoders and decoder

Abstract

An LDPC encoding system produces an encoded block by encoding the data as i data sub-blocks using an LDPC code H 1 , XOR'ing the H 1 sub-block code words to generate a block code word and further encoding the block code word using an LDPC code H 2 to produce p parity bits. The encoded block consists of a concatenation of the H 1 code words and the p parity bits. To decode the encoded block, the system decodes each H 1 sub-block code word and, if all of the H 1 sub-block code words converge, the block has been successfully decoded. Otherwise, if one of the H 1 code words fails to converge, the system performs an “extended” decoding operation in which the system produces a vector C by XOR'ing the i−1 properly decoded H 1 sub-block code words. The system then combines the vector C with the sign values of the failed H 1 sub-block code word, appends the parity bits and decodes the result as an H 2 code word over the H 2 LDPC code. For a next iteration, the system removes the vector C from the non-parity sign bits of the decoded H 2 code word and provides the results along with the associated reliability information to an ISI detector for further decoding to produce an updated failed H 1 code word. The updated H 1 sub-block code word is then iteratively decoded as part of an H 2 code word, and so forth, by combing and removing the vector C.

1. A method for encoding a block of b data bytes, the method including the steps of:
 A. encoding sub-blocks of the data using a first low density parity check (LDPC) code H 1  to produce sub-block parity bits; 
 B. producing sub-block code words by appending the sub-block parity bits to the corresponding sub-blocks of data bytes; 
 C. combining the sub-block code words to produce an H 1  block code word; 
 D. encoding the H 1  block code word using a second LDPC code H 2  to produce block parity bits; and 
 E. producing an encoded block by concatenating the sub-block code words and the block parity bits. 
 
     
     
       2. A method of decoding an encoded block that includes b data bytes that are encoded into i sub-block code words and p block parity bits, the method including the steps of:
 A. decoding the i sub-blocks using a first LDPC code H 1  and retaining sign values for sub-blocks that converge; 
 B. determining if any sub-block fail to converge and
 if none of the sub-blocks fail to converge determining the block successfully decoded, 
 if more than one fails to converge determining the block decoded unsuccessfully, and 
 if only one sub-block fails to converge performing an extended decoding operation that uses the p block parity bits, the extended decoding operation including the steps of
 i. combining the sign values for the i−1 sub-block code words that converged to produce a vector C; 
 ii. combining the failed sub-block code word with the vector C to produce an H 1  block code word and appending the block parity bits to the H 1  block code word to produce a code word of a second LDPC code H 2  with the H 1  block code word as a data portion; 
 iii. decoding the H 2  code word over the H 2  LDPC code to produce an updated H 2  code word; 
 iv. combining the vector C with the data portion of the updated H 2  code word and providing the result as an updated failed sub-block code word to an ISI detector; 
 v. further updating the failed sub-block code word in the ISI detector; 
 vi. combining the vector C with the updated failed sub-block code word and appending the p parity bits to produce a further updated H 2  code word; 
 vii. decoding the further updated H 2  code word over the H 2  LDPC code to produce a further updated H 2  code word; and 
 viii. repeating steps iv-vii until the H 2  code word either converges over the H 2  LDPC code or a predetermined number of iterations have been performed; 
 ix. if the H 2  code word converges removing the vector C from the data portion and including the result with the i−1 previously decoded sub-block code words as a successfully decoded block; and 
 x. if the H 2  code word fails to converge determining that the block unsuccessfully decoded. 
 
 
 
     
     
       3. The method of  claim 2  further including
 providing the p parity bits to the ISI detector, and 
 updating the p parity bits and appending the updated parity bits to the updated H 1  block code word to produce the updated H 2  code word. 
 
     
     
       4. A system for decoding an encoded block that includes d data bytes that are encoded into i sub-block code words over a first LDPC code H 1  and p block parity bits that correspond to a second LDPC code H 2 , the system including:
 A. an ISI detector for assigning sign values and reliability information to the respective sub-block code words and separately assigning sign values to the p parity bits; 
 B. an LDPC decoder for decoding H 1  code words over the H 1  LDPC code and H 2  codewords over the H 2  LDPC code; and 
 C. one or more buffers for retaining sign values for the decoded sub-block code words that converge; 
 D. one or more XOR gates or firmware for
 i. producing a vector C that is a combination of i−1 correctly decoded sub-block code words, 
 ii. combining the vector C with a failed sub-block code word to produce an H 1  a block code word that is also a data portion of an H 2  code word, and 
 iii. combining the vector C with the data portion of an updated H 2  code word to produce an updated failed sub-block code word, 
 
  wherein the ISI detector and the LDPC decoder decode the sub-block code words over the H 1  LDPC code in an on-the-fly decoding operation and in an extended decoding operation the ISI detector decodes an updated failed sub-block code word and the LDPC decoder decodes the corresponding H 1  block code word and appended p parity bits as an H 2  code word over the H 2  LDPC code. 
 
     
     
       5. The system of  claim 4  wherein the ISI detector further
 assigns reliability information to the p parity bits, and 
 during the extended decoding operation updates the sign values and the reliability information separately for the failed sub-block code word and the p parity bits. 
 
     
     
       6. The system of  claim 4  wherein the LDPC decoder in an extended decoding operation further decodes over the H 1  LDPC code an updated failed sub-block code word that corresponds to the H 2  code word that converged over the H 2  LDPC code. 
     
     
       7. A method of decoding an encoded block that includes b data bytes that are encoded into i sub-block code words and p block parity bits, the method including the steps of:
 a. independently decoding respective sub-block code words over a first LDPC code; 
 b. if all of the sub-block code words converge, determining the block successfully decoded; 
 c. if more than one sub-block code word does not converge, determining that the block decoded unsuccessfully; and 
 d. if a single sub-block code word fails to converge iteratively decoding the failed sub-block code word by
 i. producing an associated code word of a block-level LDPC code by combining sign values associated with the failed sub-block with a vector C that is a combination of the i−1 sub-block code words that converged, associating therewith the reliability information that corresponds to the failed sub-block code word and appending thereto sign values and reliability information for the p parity bits, 
 ii. decoding the code word over the block-level LDPC code to produce an updated code word, 
 iii. removing the vector C from the non-parity portion of the updated code word to produce an updated sub-block code word that corresponds to the failed sub-block code word, 
 iv. decoding the updated sub-block code word to further update the associated sign and reliability information associated with the failed sub-block code word, and 
 v. repeating steps i-iv using the updated sign value and reliability information until the code word converges over the block-level LDPC code or until a predetermined number of iterations have been performed, and 
 vi. if the code word converges over the block-level LDPC code removing the vector C from the non-parity portion of the code word and using the result in the decoded block to produce a successfully decode block, and 
 vii. if the code word does not converge over the block-level LDPC code determining that the block decoded unsuccessfully. 
 
 
     
     
       8. The method of  claim 7  further including the steps of
 updating the sign and reliability information associated with the p parity bits; and 
 in the step of repeating the steps i-iv including the updated sign and reliability information for the p parity bits. 
 
     
     
       9. The method of  claim 8  wherein the step of decoding the updated sub-block code word includes decoding using an ISI detector. 
     
     
       10. The method of  claim 9  wherein the step of producing an associated code word of a block-level LDPC code further includes re-reading the failed sub-block code word. 
     
     
       11. The method of  claim 10  wherein the step of producing an associated code word of a block-level LDPC code further includes re-reading the sub-block code words that converged.