Granted Patent B2

US 7,949,932 · App. 11/726,310 · Granted May 24, 2011

Abstract

Claims (259)

1. An apparatus for Low-Density Parity-Check (LPDC) encoding of data, comprising:

a processing element configured to produce an LDPC codeword of kp bits from

(k−j)p information bits based on a parity check matrix H=[H 1 |H 2 ], having dimension jk×kp, where

p is a prime number that is equal to or greater than both of numbers k and j,

H 2 is a sparse matrix of dimension jp×(k−j)p for the (k−j)p information bits,

H 1 is an upper triangular sparse matrix of dimension jp×jp for jp parity check bits, and

one or more of the second column through the p−1 th column of H have a column weight of two,

and where H 1 comprises a matrix β for the first p×p bits of H so that the first (p−1) rows of the first (p−1) columns of H are β matrices, where a β matrix has a column weight of two in the first through last column of the β matrix.

2. The apparatus of claim 1 , further comprising:

an input to the processing element for the (k−j)p information bits; and

a parity matrix generator coupled to the processing element and configured to generate the parity check matrix H=[H 1 |H 2 ].

3. The apparatus of claim 1 , wherein the processing element is further configured to receive a segment of information bits greater than (k−j)p bits and to divide the segment into a plurality of portions for production of an LDPC codeword for each portion.

4. The apparatus of claim 1 , further comprising:

a second processing element configured to receive a segment of information bits and divide the segment of information bits into (k−j)p-sized portions.

5. The apparatus of claim 4 , wherein the segment of information bits is streamed to the second processing element, and the second processing element is configured to buffer the streamed information bits for dividing the segment into the (k−j)p-sized portions.

6. The apparatus of claim 1 , wherein the second column through the p−1 th column of H each has a column weight of two.

7. An LDPC decoder, comprising:

an input port for data representative of an LDPC codeword of kp bits; and

a processor operable to produce (k−j)p information bits and jp parity check bits based on a parity check matrix H=[H 1 |H 2 ] of dimension jk×kp, wherein

p is a prime number that is equal to or greater than both k and j and

H 1 is an upper triangular matrix of dimension jp×jp corresponding to parity check bits, and one or more of columns 1 through column p of H 1 have a column weight of two,

and where H 1 comprises a matrix β for the first p×p bits of H so that the first (p−1) rows of the first (p−1) columns of H are β matrices, where a β matrix has a column weight of two in the first through last column of the β matrix.

8. The LDPC decoder of claim 7 , wherein the produced (k−j)p information bits and jp parity check bits are input to the processor for iterative processing for a predetermined number of iterations.

9. The LDPC decoder of claim 7 , wherein the processor is configured to receive as input the produced (k−j)p information bits and jp parity check bits, such that the processor is configured to iteratively process the information bits and parity check bits for a predetermined number of iterations, or until a signal to noise ratio metric has been satisfied.

10. The LDPC decoder of claim 7 , wherein columns 1 through p have column weights of two.

11. A method for LDPC encoding information, comprising:

producing a parity check matrix H=[H 1 |H 2 ] of dimension jk×kp from an array-like code, wherein

p is a prime number that is equal to or greater than both j and k,

H 1 is an upper triangular matrix of dimension jp×jp corresponding to the parity check bits, and column weights of one or more of columns 1 through p are two, where H 1 comprises a matrix β for the first p×p bits of H so that the first (p−1) rows of the first (p−1) columns of H are β matrices, where a β matrix has a column weight of two in the first through last column of the β matrix; and

producing LDPC codewords of kp bits based on the parity check matrix H=[H 1 |H 2 ].

12. The method of claim 11 , wherein the column weights of columns 1 through p are two.

13. The method of claim 11 , further comprising:

selecting p, j and k;

using the selected p, j and k to define a first matrix of dimension jk×kp of the form of

H

=

[

1

1

1

…

1

1

α

α

2

…

α

k

-

1

1

α

2

α

4

…

α

2

⁢

(

k

-

1

)

⋮

⋮

⋮

⋮

1

α

j

-

1

α

2

⁢

(

j

-

1

)

α

(

j

-

1

)

⁢

(

k

-

1

)

]

jp

×

kp

;

triangularizing, into an upper-triangular form, the first jp×jp rows and columns of the first matrix; and

substituting the β matrix of the form:

β

=

[

1

1

0

0

…

0

0

1

1

⋮

…

0

0

0

1

1

…

⋮

⋮

⋮

⋮

1

0

0

⋮

1

0

…

0

0

0

1

]

p

×

p

for the first p columns and rows of the upper-triangularized first matrix.

14. The method of claim 13 , further comprising:

eliminating 4-cycles in the triangularized first matrix.

15. A computer readable medium having stored thereon programming for a method comprising:

producing a parity check matrix H=[H 1 |H 2 ] of dimension jk×kp from an array-like code, wherein

p is a prime number that is equal to or greater than both j and k

H 1 is an upper triangular matrix of dimension jp×jp corresponding to the parity check bits, and column weights of one or more of columns 1 through p are two,

and where H 1 comprises a matrix β for the first p×p bits of H so that the first (p−1) rows of the first (p−1) columns of H are β matrices, where a β matrix has a column weight of two in the first through last column of the β matrix.

16. The computer readable medium of claim 15 , wherein the column weights of columns 1 through p are two.

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

selecting p, j and k;

using the selected p, j and k to define a first matrix of dimension jk×kp of the form of

H

=

[

1

1

1

…

1

1

α

α

2

…

α

k

-

1

1

α

2

α

4

…

α

2

⁢

(

k

-

1

)

⋮

⋮

⋮

⋮

1

α

j

-

1

α

2

⁢

(

j

-

1

)

α

(

j

-

1

)

⁢

(

k

-

1

)

]

jp

×

kp

;

triangularizing, into an upper-triangular form, the first jp×jp rows and columns of the first matrix; and

substituting the β matrix of the form:

β

=

[

1

1

0

0

…

0

0

1

1

⋮

…

0

0

0

1

1

…

⋮

⋮

⋮

⋮

1

0

0

⋮

1

0

…

0

0

0

1

]

p

×

p

for the first p columns and rows of the upper-triangularized first matrix.

Assignments (10)