Generating partially sparse generator matrix for a quasi-cyclic low-density parity-check encoder

1. A method for constructing a generator matrix using a Computer processor, the method comprising:

receiving a parity check matrix

H

=

[

H

1

,

1

H

1

,

2

…

H

1

,

N

H

2

,

1

H

2

,

2

…

H

2

,

N

⋮

⋮

⋱

⋮

H

M

,

1

H

M

,

2

…

H

M

,

N

]

,

 wherein each sub-matrix H i,j is a q×q circulant matrix;

rearranging the parity check matrix H by column and row permutations to obtain a rearranged parity check matrix

H

′

=

[

H

u

⁢

⁢

1

I

t

0

t

×

(

M

-

t

)

H

u

⁢

⁢

2

H

p

⁢

⁢

1

H

p

⁢

⁢

2

]

;

 wherein I t is an identity matrix of size t, 0 t×(m−t) is a zero matrix of size t×(M−t), and H u1 ,H u2 , H p1 and H p2 corresponds to sub-matrices in the rearranged parity check matrix H′ identified based on relative positions of the sub-matrices with respect to I t and 0 t× (m−t); and

constructing the generator matrix G=[I N−M H u1 T {tilde over (G)} T ], wherein I N−M is an identity matrix of size N-M, H u1 T is a transpose of H u1 and {tilde over (G)} T is a part of the generator matrix in systematic-circulant form constructed based on H′.

2. The method of claim 1 , wherein rearranging the parity check matrix H by column and row permutations further comprising:

enumerating a plurality of column and row permutations for the parity check matrix H; and

selecting one of the plurality of column and row permutations wherein the size of the identity matrix I t is a largest among the plurality of column and row permutations.

3. The method of claim 1 , wherein rearranging the parity check matrix H by column and row permutations further comprising:

enumerating all possible column and row permutations for the parity check matrix H; and

selecting one of the plurality of column and row permutations wherein the size of the identity matrix I t is maximized.

4. The method of claim 1 , further comprising:

storing the generator matrix G is a generator matrix memory.

5. The method of claim 4 , further comprising:

providing the generator matrix G to a low-density parity-check (LDPC) encoder.

6. The method of claim 5 , wherein the LDPC encoder is a quasi-cyclic (QC) LDPC encoder.

7. The method of claim 6 , wherein the QC LDPC encoder utilizes a Barrel shifter for parity generations when a sub-matrix G i,j of the generator matrix G is a sparse matrix.

8. A system, comprising:

a generator matrix construction module, the generator matrix construction module configured for:

receiving a parity check matrix

H

=

[

H

1

,

1

H

1

,

2

…

H

1

,

N

H

2

,

1

H

2

,

2

…

H

2

,

N

⋮

⋮

⋱

⋮

H

M

,

1

H

M

,

2

…

H

M

,

N

]

,

 wherein each sub-matrix H i,j is a q×q circulant matrix;

rearranging the parity check matrix H by column and row permutations to obtain a rearranged parity check matrix

H

′

=

[

H

u

⁢

⁢

1

I

t

0

t

×

(

M

-

t

)

H

u

⁢

⁢

2

H

p

⁢

⁢

1

H

p

⁢

⁢

2

]

,

 wherein I t is an identity matrix of size t, 0 t× (m−t) is a zero matrix of size t×(M×t), and H u1 ,H u2 ,H p2 and H p2 corresponds to sub-matrices in the rearranged parity check matrix H′ identified based on relative positions of the sub-matrices with respect to I t and 0 t×(m−t) ; and

constructing the generator matrix G=[I N−M H u1 T {tilde over (G)} T ], wherein I N−M is an identity matrix of size N ×M ,H u1 T is a transpose of H u1 and {tilde over (G)} T is a part of the generator matrix in systematic-circulant form constructed based on H′; and

a generator matrix memory in communication with the generator matrix construction module, the generator matrix memory configured for storing the generator matrix G constructed.

9. The system of claim 8 , wherein rearranging the parity check matrix H by column and row permutations further comprising:

enumerating a plurality of column and row permutations for the parity check matrix H; and

selecting one of the plurality of column and row permutations wherein the size of the identity matrix I t is a largest among the plurality of column and row permutations.

10. The system of claim 8 , wherein rearranging the parity check matrix H by column and row permutations further comprising:

enumerating all possible column and row permutations for the parity check matrix H; and

selecting one of the plurality of column and row permutations wherein the size of the identity matrix I t is maximized.

11. The system of claim 8 , further comprising:

a low-density parity-check (LDPC) encoder in communication with the generator matrix memory, the LDPC encoder configured for providing LDPC encoding based on the generator matrix G stored in the generator matrix memory.

12. The system of claim 11 , wherein the LDPC encoder is a quasi-cyclic (QC) LDPC encoder.

13. The system of claim 12 , wherein the QC LDPC encoder utilizes a Barrel shifter for parity generations when a sub-matrix G i,j of the generator matrix G is a sparse matrix.

14. A computer-readable device having computer-executable instructions for performing a method for constructing a generator matrix, the method comprising:

receiving a parity check matrix

H

=

[

H

1

,

⁢

1

H

1

,

2

…

H

1

,

N

H

2

,

1

H

2

,

2

…

H

2

,

N

⋮

⋮

⋱

⋮

H

M

,

1

H

M

,

2

…

H

M

,

N

]

 having a plurality of q×q circulant sub-matrices;

rearranging the parity check matrix H by column and row permutations to obtain a rearranged parity check matrix

H

′

=

[

H

u

⁢

⁢

1

I

t

0

t

×

(

M

-

t

)

H

u

⁢

⁢

2

H

p

⁢

⁢

1

H

p

⁢

⁢

2

]

,

 wherein I t is an identity matrix of size t, 0 t×(m−t) is a zero matrix of size t×(M −t), and H u1 , H u2 , H p1 and H p2 corresponds to sub-matrices in the rearranged parity check matrix H′ identified based on relative positions of the sub-matrices with respect to I t and 0 t×(m−t) ; and

constructing the generator matrix G =[I N−M H u1 T {tilde over (G)} T ]based on H′, wherein I N−M is an identity matrix of size N−M, H u1 T is a transpose of H u1 and {tilde over (G)} T is a part of the generator matrix in systematic-circulant form constructed based on H′.

15. The computer-readable device of claim 14 , wherein rearranging the parity check matrix H by column and row permutations further comprising:

enumerating a plurality of column and row permutations for the parity check matrix H to obtain a plurality of rearranged parity check matrices; and

selecting one of the plurality of column and row permutations wherein the size of the identity matrix I t is a largest among the plurality of rearranged parity check matrices.

16. The computer-readable device of claim 14 , wherein rearranging the parity check matrix H by column and row permutations further comprising:

enumerating all possible column and row permutations for the parity check matrix H to obtain all possible rearranged parity check matrices; and

selecting one of the plurality of column and row permutations wherein the size of the identity matrix I t is maximized.

17. The computer-readable device of claim 14 , wherein the method Further comprises:

storing the generator matrix G is a generator matrix memory.

18. The computer-readable device of claim 17 , wherein the method Further comprises:

providing the generator matrix G to a low-density parity-check (LDPC) encoder.

19. The computer-readable device of claim 18 , wherein the LDPC encoder is a quasi-cyclic (QC) LDPC encoder.

20. The computer-readable device of claim 19 , wherein the QC LDPC encoder utilizes a barrel shifter for parity generations when a sub-matrix G i,j of the generator matrix G is a sparse matrix.