Low density parity check decoder for irregular LDPC codes

• US 8,555,140 B2
• Filed: 02/05/2013
• Issued: 10/08/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 Kumar, Choi, Gwan S.
• Primary Examiner(s): Merant, Guerrier
• Application Number:
  US13/759,225
• Publication Number:
  US 20130151922A1
• Time in Patent Office: 245 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 (LDPC) code decoder, comprising:

a control unit that controls decoder processing, the control unit configured to cause the decoder to process blocks of an LDPC matrix in a first sequence, and to compute R messages for the blocks in a second sequence that is different from the first sequence, wherein the first sequence specifies a first set of blocks of a given layer to be processed at a given time and a second set of blocks of the given layer to be processed after the first set of blocks;

wherein the first set specifies only blocks of the given layer that are not dependent on a result of a previously processed layer and the second set specifies blocks of the given layer that are dependent on a result of the previously processed layer.

2. The decoder of claim 1, wherein the second sequence specifies R new computation for blocks of a plurality of layers of the matrix during partial state processing performed for blocks of a single layer of the matrix specified by the first sequence.

3. The decoder of claim 1, wherein the second sequence identifies blocks to process for R messages based on the blocks identified in the first sequence being non-zero blocks for which Q message processing depends on a block of the second sequence.

4. The decoder of claim 1, wherein at least one of the first sequence and the second sequence specifies an out of order sequence for processing of the blocks.

5. 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 produces an R new message 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 for a layer of the matrix currently being processed;

a P message substep that generates updated P messages; and

a Q message substep that computes variable node messages (Q messages).

6. The decoder of claim 5, wherein the control unit is configured to cause the decoder to generate an updated P message based on a determination of a final state for a block row.

7. A method for decoding a low density parity check (LDPC) code, comprising:

processing blocks of an LDPC matrix in a first sequence;

computing R messages for the blocks in a second sequence that is different from the first sequence;

specifying, via the first sequence, a first set of blocks of a given layer to be processed at a given time and a second set of blocks of the given layer to be processed after the first set of blocks;

wherein the first set specifies only blocks of the given layer that are not dependent on a result of a previously processed layer and the second set specifies blocks of the given layer that are dependent on a result of the previously processed layer.

8. The method of claim 7, further comprising computing R new messages, in accordance with the second sequence, for blocks of a plurality of layers of the matrix during partial state processing performed for blocks of a single layer of the matrix specified by the first sequence.

9. The method of claim 7, further comprising identifying, in the second sequence, blocks to process for R messages based on the blocks identified in the first sequence being non-zero blocks for which Q message processing depends on a block of the second sequence.

10. The method of claim 7, wherein at least one of the first sequence and the second sequence specifies an out of order sequence for processing of the blocks.

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

an R new update substep that produces an R new message 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 for a layer of the matrix currently being processed;

a P message substep that generates updated P messages; and

a Q message substep that computes variable node messages (Q messages).

12. The method of claim 11, wherein the processing of the P message substep comprises generating an updated P message based on a determination of a final state for a block row.

13. A low density parity check (LDPC) code decoder, comprising:

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

process blocks of an LDPC matrix out of order; and

process each block of the matrix in processing substeps comprising;

an R new update substep that produces an R new message 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 for a layer of the matrix currently being processed;

a P message substep that generates updated P messages; and

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

a first permuter that permutes a P message, wherein the permuter permutes the P message by the difference of the permutation of a block currently being processed and the permutation of a block previously processed;

wherein the block currently being processed and the block previously processed are in a same block column.

14. The decoder of claim 13, further comprising:

a P message generator that combines an R message with a Q message to produce a P message; and

a Q message generator that combines an R message with a P message to produce a Q message.

15. The decoder of claim 13, further comprising a Q message memory that stores a Q message that is to be combined with an R message to produce a P message.

16. The decoder of claim 13, further comprising a P message memory that stores a P message that is to be combined with an R message to produce a Q message.

17. The decoder of claim 13, wherein the control unit is configured to cause the decoder to generate an updated P message based on a determination of a final state for a block row.

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

processing blocks of an LDPC matrix out of order; and

processing each block of the matrix in processing substeps comprising;

an R new update substep that produces an R new message 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 for a layer of the matrix currently being processed;

a P message substep that generates updated P messages; and

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

permuting a P message, wherein the permuting comprises permuting the P message by the difference of the permutation of a block currently being processed and the permutation of a block previously processed;

wherein the block currently being processed and the block previously processed are in a same block column.

19. The method of claim 18, further comprising:

combining an R message with a Q message to produce a P message; and

combining an R message with a P message to produce a Q message.

20. The method of claim 18, further comprising storing a Q message that is to be combined with an R message to produce a P message.

21. The method of claim 18, further comprising storing a P message that is to be combined with an R message to produce a Q message.

22. The method of claim 18, wherein generation of the updated P message comprises generating the updated P message based on a determination of a final state for a block row.