Low density parity check decoder for irregular LDPC codes

• US 8,418,023 B2
• Filed: 05/01/2008
• Issued: 04/09/2013
• Est. Priority Date: 05/01/2007
• Status: Active Grant

• Current Assignee: Texas A&M University System
• Original Assignee: Texas A&M University System
• Inventors: Gunnam, Kiran K., Choi, Gwan S.
• Primary Examiner(s): Merant, Guerrier
• Application Number:
  US12/113,755
• Publication Number:
  US 20080301521A1
• Time in Patent Office: 1,804 Days
• Field of Search: None
• US Class Current: 714/758
• CPC Class Codes: H03M 13/1105 Decoding
• CPC Class Codes: H03M 13/1128 Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations
• CPC Class Codes: H03M 13/116 Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
• CPC Class Codes: H03M 13/1177 Regular LDPC codes with parity-check matrices wherein all rows and columns have the same row weight and column weight, respectively
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

A method and system for decoding low density parity check (“LDPC”) codes. An LDPC decoder includes a control unit that controls decoder processing, the control unit causing the decoder to process the blocks of a low density parity check (“LDPC”) matrix out of order. A decoder embodiment may process the layers of the LDPC matrix out of order and/or perform partial state processing on out of order blocks of the LDPC matrix and/or generate R messages out of order.

Claims

1. A low density parity check code decoder, comprising:

a control unit that controls decoder processing, the control unit configured to;

cause the decoder to process blocks of a low density parity check (“

LDPC”

) matrix out of order; and

schedule computation of R messages for a first non-zero block and computation of P messages and Q messages for a second non-zero block such that R messages for the first non-zero block are generated while processing the second non-zero block based on a determination of need for the R messages for the computation of P and Q messages for the second non-zero block;

wherein the first non-zero block and the second non-zero block are in a same column of the matrix.

2. The decoder of claim 1, wherein the control unit causes the decoder to process layers of the LDPC matrix out of order.

3. The decoder of claim 1, further comprising an array of check node units that perform partial state processing on blocks of the LDPC matrix.

4. The decoder of claim 3, wherein the check node units perform partial state processing on out of order blocks of the LDPC matrix.

5. The decoder of claim 1, wherein the control unit is configured to cause the decoder to update the P message based on a determination of a final state for each block row.

6. The decoder of claim 1, further comprising an R select unit that provides an R message based on the values stored in a final state storage array, wherein the R select unit produces the R message of a dependent layer block based on a determination that a non-zero block being processed in a current layer of a present column of the matrix.

7. The decoder of claim 1, further comprising an R select unit that provides an R message based on the values stored in a final state storage array, wherein the R select unit produces the R message for a layer of the matrix currently being processed.

8. The decoder of claim 1, wherein the control unit schedules no processing of zero blocks of the LDPC matrix.

9. The decoder of claim 1, wherein the control unit is configured to cause the decoder to scheduling R new message computation of a block independent of partial state processing of the block row to which the block belongs.

10. The decoder of claim 1, wherein the control unit is configured to cause the decoder to process each block of the matrix in processing substeps comprising:

an R new update substep that provides an R new message, wherein the R new message is produced for a block of a different layer of the matrix from a layer containing a block currently being processed;

an R old update substep that;

selects an R old message, wherein the R old message is produced for a layer of the matrix currently being processed;

a P message substep that generates updated P messages;

a Q message substep that computes variable node messages (Q messages); and

a partial state substep that updates partial state of a block row based on Q messages computed for the block (CNU Partial state processing).

11. The decoder of claim 10, further comprising a selector coupled to the Q message storage array, the selector selects one of a Q message and a channel log-likelihood ratio (“

LLR”

) for storage in the Q message storage array, wherein the selector selects an LLR to initialize the decoder.

12. The decoder of claim 1, further comprising a P sum adder array that sums a Q message provided by a Q message storage array and an R new message provided by an R new selector unit to produce an updated P message.

13. The decoder of claim 1, further comprising a cyclic shifter that shifts an updated P message.

14. The decoder of claim 1, further comprising a Q subtractor array that subtracts an R old message from a shifted updated P message to produce an updated Q message.

15. The decoder of claim 1, wherein the controller comprises a storage array that stores sequence information that determines the processing order of at least one of matrix blocks, R new messages, and matrix layers.

16. The decoder of claim 15, wherein the sequence information is selected based on at least the LDPC matrix to be decoded.

17. The decoder of claim 1, wherein a number of processing elements in the decoder is based on the size of a circulant processed, and wherein the circulant is processed in block serial fashion.

18. A method for decoding a low density parity check code, comprising:

processing blocks of a low density parity check (“

LDPC”

) matrix out of order; and

scheduling computation of R messages for a first non-zero block and computation of P messages and Q messages for a second non-zero block such that R messages for the first non-zero block are generated while processing the second non-zero block based on a determination of need for the R messages for the computation of P and Q messages for the second non-zero block;

wherein the first non-zero block and the second non-zero block are in a same column of the matrix.

19. The method of claim 18, further comprising processing layers of the LDPC matrix out of order.

20. The method of claim 18, further comprising scheduling R new message computation of a block independent of partial state processing of the block row to which the block belongs.

21. The method of claim 18, further comprising providing an R message based on the values stored in a final state storage array, wherein an R message of a dependent layer block is produced based on a determination that a non-zero block being processed in a current layer of a present column of the matrix.

22. The method of claim 18, further comprising selecting an R message based on the values stored in a final state storage array, wherein the R message is produced for a layer of the matrix currently being processed.

23. The method of claim 18, further comprising processing each block of the matrix in processing substeps comprising:

an R new update substep that provides an R new message, wherein the R new message is produced for a block of a different layer of the matrix from a layer containing a block currently being processed;

an R old update substep that;

selects an R old message, wherein the R old message is produced for a layer of the matrix currently being processed;

a P message substep that generates updated P messages;

a Q message substep that computes variable node messages (Q messages); and

a partial state substep that updates partial state of a block row based on Q messages computed for the block (CNU Partial state processing).

24. The method of claim 18, further comprising scaling a Q message provided to CNU array to reduce the magnitude of the Q message.

25. The method of claim 18, further comprising selecting one of a Q message and a channel log-likelihood ratio (“

LLR”

) to generate a P message, the LLR is selected to initialize decoding.

26. The method of claim 18, further comprising update the P message based on a determination of a final state for each block row.

27. The method of claim 18, further comprising cyclically shifting an updated P message.

28. The method of claim 19, further comprising subtracting an R old message from a shifted updated P message to produce an updated Q message.

29. The method of claim 18, further comprising determining the processing order of at least one of matrix blocks, R new messages, and matrix layers based on sequence information based at least in part on the LDPC matrix to be decoded.

30. The method of claim 18, further comprising processing a circulant in sub-block serial fashion.