Method and System for Decoding Low Density Parity Check Codes

• US 20110029756A1
• Filed: 07/28/2009
• Published: 02/03/2011
• Est. Priority Date: 07/28/2009
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Biscondi, Eric, Wolf, Tod David, Hoyle, David
• Granted Patent: US 8,392,789 B2
• Time in Patent Office: Days
• US Class Current: 712/22
• CPC Class Codes: H03M 13/1114 Merged schedule message passing algorithm with storage of sums of check-to-bit node messages or sums of bit-to-check node messages, e.g. in order to increase the memory efficiency
• CPC Class Codes: H03M 13/1117 using approximations for check node processing, e.g. an outgoing message is depending on the signs and the minimum over the magnitudes of all incoming messages according to the min-sum rule
• CPC Class Codes: H03M 13/112 with correction functions for the min-sum rule, e.g. using an offset or a scaling factor
• 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/1165 QC-LDPC codes as defined for the digital video broadcasting [DVB] specifications, e.g. DVB-Satellite [DVB-S2]
• CPC Class Codes: H03M 13/1188 wherein in the part with the double-diagonal at least one column has an odd column weight equal or greater than three
• CPC Class Codes: H03M 13/3715 Adaptation to the number of estimated errors or to the channel state
• CPC Class Codes: H03M 13/3723 using means or methods for the initialisation of the decoder
• CPC Class Codes: H03M 13/3753 using iteration stopping criteria
• CPC Class Codes: H03M 13/47 Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H03M 13/6544 IEEE 802.16 (WIMAX and broadband wireless access)
• CPC Class Codes: H03M 13/658 Scaling by multiplication or division
• CPC Class Codes: H03M 13/6583 Normalization other than scaling, e.g. by subtraction

Abstract

A method for decoding a codeword in a data stream encoded according to a low density parity check (LDPC) code having an m×j parity check matrix H by initializing variable nodes with soft values based on symbols in the codeword, wherein a graph representation of H includes m check nodes and j variable nodes, and wherein a check node m provides a row value estimate to a variable node j and a variable node j provides a column value estimate to a check node m if H(m,j) contains a 1, computing row value estimates for each check node, wherein amplitudes of only a subset of column value estimates provided to the check node are computed, computing soft values for each variable node based on the computed row value estimates, determining whether the codeword is decoded based on the soft values, and terminating decoding when the codeword is decoded.

Claims

1. A method for decoding a codeword in a data stream encoded according to a low density parity check (LDPC) code having an m×

j parity check matrix H, the method comprising;

initializing each of j variable nodes in a graph representation of the parity check matrix H with a soft value L(q_j) based on a jth symbol in the codeword, wherein the graph representation comprises m check nodes and j variable nodes and wherein a check node m provides a row value estimate R_mj to a variable node j and a variable node j provides a column value estimate L(q_mj) to a check node m if H(m,j) contains a 1;

computing row value estimates R_mj for each check node m, wherein amplitudes of only a subset of column value estimates L(q_mj) provided to the check node m are computed;

computing soft values L(q_j) for each variable node j based on the computed row value estimates R_mj;

determining whether the codeword is decoded based on the soft values L(q_j); and

terminating decoding when the codeword is decoded.

2. The method of claim 1, wherein the subset of the column value estimates L(q_mj) consists of two column value estimates L(q_mj).

3. The method of claim 1, wherein computing row value estimates R_mj comprises:

selecting a number λ

of the column value estimates L(q_mj) provided to the check node m having smallest absolute values; and

computing a row value estimate R_mj for each variable node j providing a column value estimate L(q_mj) to the check node m by

determining a sign of the row value estimate R_mj based a sign of the column value estimate L(q_mj);

when the variable node j provides one of a proper subset of the selected λ

column value estimates L(q_mj), determining an amplitude of the row value estimate R_mj based only on amplitudes of the other selected λ

column value estimates L(q_mj), wherein the column value estimates L(q_mj) in the proper subset of the selected λ

column value estimates L(q_mj) have the smallest absolute values of the selected λ

column value estimates L(q_mj); and

when the variable node j provides any of the other column value estimates L(q_mj), determining an amplitude of the row value estimate R_mj based on amplitudes of all of the selected λ

column value estimates L(q_mj).

4. The method of claim 3,

wherein determining a sign of the row value estimate R_mj further comprises computing the sign as the sign of the column value estimate L(q_mj) multiplied by a product of signs of the column value estimates L(q_mj) provided to the check node m, and

wherein determining an amplitude of the row value estimate R_mj based only on amplitudes of the other selected λ

column value estimates L(q_mj) comprises computing the amplitude as a product of a scale factor and a sum of Ψ

functions of absolute values of the other selected λ

column value estimates L(q_mj), and

wherein determining an amplitude of the row value estimate R_mj based on amplitudes of all of the selected λ

column value estimates L(q_mj) comprises computing the amplitude as a product of the scale factor and a sum of Ψ

functions of absolute values of all of the selected λ

column value estimates L(q_mj).

5. The method of claim 4, wherein a Ψ

function of the absolute value of a first column value estimate x and the absolute value of a second column value estimate y is defined as

Ψ

(x,y)=sgn(x)sgn(y)min(|x|,|y|)+log(1+e<sup>−

|x+y|</sup>)−

log(1+e<sup>−

|x−

y|</sup>).

6. The method of claim 1, further comprising:

storing an optimal number of the row value estimates R_mj for all check nodes m in each data word of a first plurality of single instruction multiple data (SIMD) addressable data words, wherein each data word consists of a number of bytes, wherein the optimal number is a largest integer factor of an expansion factor of the parity check matrix H, wherein the largest integer factor is less than or equal to the number of bytes.

7. The method of claim 4, further comprising:

storing an optimal number of the soft values L(q_j) in each data word of a second plurality of SIMD addressable data words, wherein each data word consists of the second number of bytes and wherein the optimal number of the soft values L(q_j) is determined empirically for the parity check matrix H.

8. The method of claim 1, further comprising:

storing an optimal number of the row value estimates R_mj for all check nodes m in each data word of a plurality of single instruction multiple data (SIMD) addressable data words, wherein each data word consists of a number of bytes, wherein the optimal number is determined empirically for the parity check matrix H.

9. The method of claim 1, wherein the parity check matrix H is derived from m_b×

n_b base parity check matrix H_b using an expansion factor z, wherein m_b=m/z and n_b=j/z, and wherein each element H_b(m_b,n_b) is a z×

1 submatrix, and wherein determining whether a codeword is decoded further comprises;

converting the soft values L(q_j) to j hard values;

grouping the j hard values into an n_b×

1 information matrix I wherein each element I(n_b,1) is a z×

1 submatrix of the j hard values;

computing the product of the base parity check matrix H_b and the information matrix I, wherein the product is an m_b×

1 matrix I′

wherein each element I′

(m_b,1) is a z×

1 submatrix; and

determining the codeword is decoded when all elements of all submatrices I′

(m_b,1) are zero.

10. The method of claim 7, wherein computing the product comprises:

for each row m_b of the parity check matrix H_b, forming a dot product of the row m_b and the information matrix I to generate a submatrix I′

(m_b,1), wherein computing a product of a submatrix I(n_b,1) and a submatrix H_b(m_b,n_b) is performed by circular shifting the submatrix I(n_b,1) by a circular shift value of the submatrix H_b(m_b,n_b).

11. A computer readable medium comprising executable instructions to perform a method for decoding a codeword in a data stream encoded according to a low density parity check (LDPC) code having an m×

j parity check matrix H, the method comprising;

initializing each of j variable nodes in a graph representation of the parity check matrix H with a soft value L(q_j) based on a jth symbol in the codeword, wherein the graph representation comprises m check nodes and j variable nodes and wherein a check node m provides a row value estimate R_mj to a variable node j and a variable node j provides a column value estimate L(q_mj) to a check node m if H(m,j) contains a 1;

computing row value estimates R_mj for each check node m, wherein amplitudes of only a subset of column value estimates L(q_mj) provided to the check node m are computed;

computing soft values L(q_j) for each variable node j based on the computed row value estimates R_mj;

determining whether the codeword is decoded based on the soft values L(q_j); and

terminating decoding when the codeword is decoded.

12. The computer readable medium of claim 11, wherein the subset of the column value estimates L(q_mj) consists of two column value estimates L(q_mj).

13. The computer readable medium of claim 11, wherein computing row value estimates R_mj comprises:

selecting a number λ

of the column value estimates L(q_mj) provided to the check node m having smallest absolute values; and

computing a row value estimate R_mj for each variable node j providing a column value estimate L(q_mj) to the check node m by

determining a sign of the row value estimate R_mj based a sign of the column value estimate L(q_mj);

when the variable node j provides one of a proper subset of the selected λ

column value estimates L(q_mj), determining an amplitude of the row value estimate R_mj based only on amplitudes of the other selected λ

column value estimates L(q_mj), wherein the column value estimates L(q_mj) in the proper subset of the selected λ

column value estimates L(q_mj) have the smallest absolute values of the selected λ

column value estimates L(q_mj); and

when the variable node j provides any of the other column value estimates L(q_mj), determining an amplitude of the row value estimate R_mj based on amplitudes of all of the selected λ

column value estimates L(q_mj).

14. The computer readable medium of claim 13,

wherein determining a sign of the row value estimate R_mj further comprises computing the sign as the sign of the column value estimate L(q_mj) multiplied by a product of signs of the column value estimates L(q_mj) provided to the check node m, and

wherein determining an amplitude of the row value estimate R_mj based only on amplitudes of the other selected λ

column value estimates L(q_mj) comprises computing the amplitude as a product of a scale factor and a sum of Ψ

functions of absolute values of the other selected λ

column value estimates L(q_mj), and

wherein determining an amplitude of the row value estimate R_mj based on amplitudes of all of the selected λ

column value estimates L(q_mj) comprises computing the amplitude as a product of the scale factor and a sum of Ψ

functions of absolute values of all of the selected λ

column value estimates L(q_mj).

15. The computer readable medium of claim 11, wherein the method further comprises:

storing an optimal number of the row value estimates R_mj for all check nodes m in each data word of a first plurality of single instruction multiple data (SIMD) addressable data words, wherein each data word consists of a number of bytes, wherein the optimal number is a largest integer factor of an expansion factor of the parity check matrix H, wherein the largest integer factor is less than or equal to the number of bytes; and

storing an optimal number of the soft values L(q_j) in each data word of a second plurality of SIMD addressable data words, wherein each data word consists of the second number of bytes and wherein the optimal number of the soft values L(q_j) is determined empirically for the parity check matrix H.

16. The computer readable medium of claim 11, wherein the parity check matrix H is derived from m_b×

n_b base parity check matrix H_b using an expansion factor z, wherein m_b=m/z and n_b=j/z, and wherein each element H_b(m_b,n_b) is a z×

1 submatrix, and wherein determining whether a codeword is decoded further comprises;

converting the soft values L(q_j) to hard values;

grouping the hard values into an n_b×

1 information matrix I wherein each element I(n_b,1) is a z×

1 submatrix of hard values;

computing the product of the base parity check matrix H_b and the information matrix I, wherein the product is an m_b×

1 matrix I′

wherein each element I′

(m_b,1) is a z×

1 submatrix; and

determining the codeword is decoded when all elements of all submatrices I′

(m_b,1) are zero.

17. The computer readable medium of claim 14, wherein computing the product comprises:

for each row m_b of the parity check matrix H_b, forming a dot product of the row m_b and the information matrix I to generate a submatrix I′

(m_b,1), wherein computing a product of a submatrix I(n_b,1) and a submatrix H_b(m_b,n_b) is performed by circular shifting the submatrix I(n_b,1) by a circular shift value of the submatrix H_b(m_b,n_b).

18. A digital system comprising:

a processor; and

a memory configured to store software instructions, wherein when executed by the processor, the software instructions cause the digital system to perform a method for decoding a codeword in a data stream encoded according to a low density parity check (LDPC) code having an m×

j parity check matrix H, the method comprising;

initializing each of j variable nodes in a graph representation of the parity check matrix H with a soft value L(q_j) based on a jth symbol in the codeword, wherein the graph representation comprises m check nodes and j variable nodes and wherein a check node m provides a row value estimate R_mj to a variable node j and a variable node j provides a column value estimate L(q_mj) to a check node m if H(m,j) contains a 1;

computing row value estimates R_mj for each check node m, wherein amplitudes of only a subset of column value estimates L(q_mj) provided to the check node m are computed;

computing soft values L(q_j) for each variable node j based on the computed row value estimates R_mj;

determining whether the codeword is decoded based on the soft values L(q_j); and

terminating decoding when the codeword is decoded.

19. The digital system of claim 18, wherein the subset of the column value estimates L(q_mj) consists of two column value estimates L(q_mj).

20. The digital system of claim 18, wherein computing row value estimates R_mj comprises:

selecting a number λ

of the column value estimates L(q_mj) provided to the check node m having smallest absolute values; and

computing a row value estimate R_mj for each variable node j providing a column value estimate L(q_mj) to the check node m by

determining a sign of the row value estimate R_mj based a sign of the column value estimate L(q_mj);

when the variable node j provides one of a proper subset of the selected λ

column value estimates L(q_mj), determining an amplitude of the row value estimate R_mj based only on amplitudes of the other selected λ

column value estimates L(q_mj), wherein the column value estimates L(q_mj) in the proper subset of the selected λ

column value estimates L(q_mj) have the smallest absolute values of the selected λ

column value estimates L(q_mj); and

when the variable node j provides any of the other column value estimates L(q_mj), determining an amplitude of the row value estimate R_mj based on amplitudes of all of the selected λ

column value estimates L(q_mj).

21. The digital system of claim 18, further comprising:

a memory configured to store a first plurality of single instruction multiple data (SIMD) addressable data words and a second plurality of SIMD addressable data words, wherein each data word consists of a number of bytes; and

wherein the method further comprises;

storing an optimal number of the row value estimates R_mj for all check nodes m in each data word of the first plurality of SIMD addressable data words, wherein the optimal number is a largest integer factor of an expansion factor of the parity check matrix H, wherein the largest integer factor is less than or equal to the number of bytes, and

storing an optimal number of the soft values L(q_j) in each data word of the second plurality of SIMD addressable data words, wherein the optimal number of the soft values L(q_j) is determined empirically for the parity check matrix H.

22. The digital system of claim 18, wherein the parity check matrix H is derived from m_b×

n_b base parity check matrix H_b using an expansion factor z, wherein m_b=m/z and n_b=j/z, and wherein each element H_b(m_b,n_b) is a z×

1 submatrix, and wherein determining whether a codeword is decoded further comprises;

converting the soft values L(q_j) to hard values;

grouping the hard values into an n_b×

1 information matrix I wherein each element I(n_b,1) is a z×

1 submatrix of hard values;

computing the product of the base parity check matrix H_b and the information matrix I, wherein the product is an m_b×

1 matrix I′

wherein each element I′

(m_b,1) is a z×

1 submatrix, wherein computing the product comprises for each row m_b of the parity check matrix H_b, forming a dot product of the row m_b and the information matrix I to generate a submatrix I′

(m_b,1), wherein computing a product of a submatrix I(n_b,1) and a submatrix H_b(m_b,n_b) is performed by circular shifting the submatrix I(n_b,1) by a circular shift value of the submatrix H_b(m_b,n_b); and

determining the codeword is decoded when all elements of all submatrices I′

(m_b,1) are zero.