Granted Patent B2

US 8,024,641 · App. 12/704,850 · Granted Sep 20, 2011

Abstract

Claims (39)

1. A method for constructing a low-density parity-check (LDPC) code having a structured parity check matrix comprising the steps of:

a) constructing a structured base parity check matrix having a plurality of sub-matrices, the sub-matrices are selected from a group consisting of permutation matrix, pseudo-permutation matrix, and zero matrix; and

b) expanding the structured base parity check matrix into an expanded parity check matrix, the expanding step comprising:

replacing each non-zero member of the sub-matrices by a permutation matrix or a pseudo-permutation matrix; and

replacing each zero member of the sub-matrices by a zero matrix.

2. The method of claim 1 wherein the sub-matrices in the plurality of sub-matrices have the same size.

3. The method of claim 1 wherein the base parity check matrix is in the form of H=[H d |H p ], H d being a data portion of the parity check matrix, H p being a parity portion of the parity check matrix.

4. The method of claim 3 wherein the parity portion of the structured base parity check matrix comprises a dual diagonal.

5. The LDPC code constructed using the method of claim 1 .

6. A device using the LDPC code of claim 5 .

7. A method for encoding data using the LDPC code of claim 5 .

8. A method for decoding data stream encoded using the LDPC code of claim 5 comprising the steps of:

a) receiving a set of input values corresponding to variable nodes of the structured parity check matrix; and

b) estimating a probability value of the variable nodes based on the plurality of parity checks contained within a block of parity checks corresponding to a row of sub-matrices of the base parity check matrix, over the blocks of the base parity check matrix.

9. The method of claim 8 wherein the estimating step is repeated until a termination criterion is reached.

10. A method for constructing a low-density parity-check (LDPC) code having a structured parity check matrix comprising the steps of:

a) constructing a structured base parity check matrix having a plurality of sub-matrices, a subset of the plurality of the sub-matrices is concatenated using sub-matrices selected from a group consisting of permutation matrix, pseudo-permutation matrix, and zero matrix; and

b) expanding the structured base parity check matrix into an expanded parity check matrix, the expanding step comprising:

replacing each non-zero member of the sub-matrices by a permutation matrix or a pseudo-permutation matrix; and

replacing each zero member of the sub-matrices by a zero matrix.

11. The method of claim 10 wherein the subset of the sub-matrices is a minority of the plurality of sub-matrices.

12. A device for decoding data stream encoded using LDPC code, comprising:

a) intra-layer storage elements for receiving a set of input values corresponding to variable nodes of a structured parity check matrix, and for storing an updated variable nodes information;

b) processing units for estimating a probability value of the variable nodes based on a plurality of parity checks contained within a block of parity checks corresponding to a row of sub-matrices of a base parity check matrix;

c) a read network for delivering the updated variable nodes information from the intra-layer storage elements to the processing units;

d) inter-layer storage for storing additional information from sub-matrices concatenated using sub-matrices selected from a group consisting of permutation matrix, pseudo-permutation matrix, and zero matrix; and

e) a write network for delivering results from the processing units to the intra-layer storage elements.

13. A storage medium readable by a computer encoding a computer program for execution by the computer to carry out a method for constructing a low-density parity-check (LDPC) code having a structured parity check matrix, the computer program comprising:

code means for constructing a structured base parity check matrix having a plurality of sub-matrices, the sub-matrices are selected from a group consisting of permutation matrix, pseudo-permutation matrix, and zero matrix;

code means for expanding the structured base parity check matrix into an expanded parity check matrix;

code means for replacing each non-zero member of the sub-matrices by a permutation matrix or a pseudo-permutation matrix; and

code means for replacing each zero member of the sub-matrices by a zero matrix.

14. A method for constructing a low-density parity-check (LDPC) code having a structured parity check matrix comprising the steps of:

a) constructing a structured base parity check matrix H=[H d |H p ], H d being a data portion of the parity check matrix, H p being a parity portion of the parity check matrix;

b) selecting a parity portion of the structured base parity check matrix so that when expanded, an inverse of the parity portion of the expanded parity check matrix is sparse; and

c) expanding the structured base parity check matrix into an expanded parity check matrix.

15. The LDPC code constructed, using the method of claim 14 .

16. A device using the LDPC code of claim 14 .

17. A method for encoding data using the LDPC code having the structured parity check matrix constructed according to the method of claim 14 .

Assignments (12)