Low density parity check decoder

• US 10,141,950 B2
• Filed: 07/07/2015
• Issued: 11/27/2018
• 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): Mehrmanesh, Elmira
• Application Number:
  US14/792,982
• Publication Number:
  US 20150311917A1
• Time in Patent Office: 1,239 Days
• Field of Search: 714758, 714801
• 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. A method and system for decoding low density parity check (“LDPC”) codes. An LDPC code decoder includes decoding circuitry configured to process blocks of an LDPC matrix. The decoding circuitry includes a control unit that controls processing by the decoding circuitry. The control unit is configured to cause the decoding circuitry to process blocks of a layer of the LDPC matrix out of order.

Claims

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

decoding circuitry configured to process blocks of an LDPC matrix, the decoding circuitry comprising;

a control unit that controls processing by the decoding circuitry, the control unit configured to cause the decoding circuitry to process blocks of a layer of the LDPC matrix out of order,

wherein the control unit is configured to cause the decoding circuitry to process each block of the LDPC 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 (check node unit (CNU) Partial state processing).

2. The LDPC code decoder of claim 1, wherein the decoding circuitry is configured to generate a Q message by combining an R message with a P message.

3. The LDPC code decoder of claim 1, wherein the decoding circuitry further comprises a permuter configured to permute a P message.

4. The LDPC code decoder of claim 3, wherein the permuter is configured to permute the P message by a difference of permutation of a second block currently being processed and permutation of a block previously processed;

wherein the second block currently being processed and the block previously processed are in a same block column of the LDPC matrix.

5. The LDPC code decoder of claim 1, wherein the decoding circuitry is configured to subtract a second R old message from a permuted P message to generate a Q message.

6. The LDPC code decoder of claim 1, wherein the decoding circuitry is configured to select one of an updated P message and a channel log-likelihood ratio (LLR) for storage in a P memory, wherein a channel LLR is selected to initialize decoding.

7. The LDPC code decoder of claim 1, wherein the decoding circuitry is further configured to select an R message from a plurality of previously generated possible R messages based on at least a message index value and a sign bit.

8. The LDPC code decoder of claim 1, wherein the LDPC matrix is quasi-cyclic.

9. A method comprising:

processing blocks of a layer of a low density parity check (LDPC) matrix out of order, the processing of each of the blocks comprising;

an R new update step comprising providing an R new message, the R new message produced for a block of a different layer of the matrix from a layer containing a block currently being processed;

an R old update step comprising selecting an R old message, the R old message produced for a layer of the matrix currently being processed;

a P message step comprising generating updated P messages;

a Q message step comprising computing variable node messages (Q messages); and

a partial state step comprising updating partial state of a block row based on Q messages computed for the block (check node unit (CNU) Partial state processing).

10. The method of claim 9, further comprising generating a Q message by combining an R message with a P message.

11. The method of claim 9, further comprising permuting a P message.

12. The method of claim 11, wherein permuting the P message comprising permuting the P message by a difference of permutation of a second block currently being processed and permutation of a block previously processed;

wherein the second block currently being processed and the block previously processed are in a same block column of the LDPC matrix.

13. The method of claim 9, further comprising subtracting a second R old message from a permuted P message to generate a Q message.

14. The method of claim 9, further comprising selecting one of an updated P message and a channel log-likelihood ratio (LLR) for storage in a P memory, and further comprising selecting a channel LLR to initialize decoding.

15. The method of claim 9, further comprising selecting an R message from a plurality of previously generated possible R messages based on at least a message index value and a sign bit.

16. The method of claim 9, wherein the LDPC matrix is quasi-cyclic.