Universal and reconfigurable QC-LDPC encoder

• US 9,236,886 B1
• Filed: 09/17/2013
• Issued: 01/12/2016
• Est. Priority Date: 03/15/2013
• Status: Expired due to Fees

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Zhu, Jiangli, Tai, Ying Yu, Chen, Xiaoheng
• Primary Examiner(s): Blair, April Y
• Assistant Examiner(s): Gandhi, Dipakkumar
• Application Number:
  US14/029,697
• Time in Patent Office: 847 Days
• US Class Current: 1/1
• 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/1174 Parity-check or generator matrices built from sub-matrices representing known block codes such as, e.g. Hamming codes, e.g. generalized LDPC codes
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing
• CPC Class Codes: H03M 13/6561 Parallelized implementations

Abstract

The various implementations described herein include systems, methods and/or devices that may enhance performance of error control encoding. The method includes receiving information data and generating parity information based on an m×k parity matrix comprising an array of b×b circulant sub-matrices, including m columns of said sub-matrices, each column comprising k said sub-matrices. The method further includes dividing the information data into a plurality of b-sized trunks and generating m parity segments. Each parity segment consists of b bits, and each parity segment is generated by multiplying each of the k b×b circulant sub-matrices in a respective column of the parity matrix by a corresponding trunk of information data, where each multiplication of a b×b circulant sub-matrix by a corresponding trunk comprises b² concurrent computations. The method further includes generating a codeword based on the information data and the m parity segments.

Claims

1. A method for generating a QC-LDPC codeword by encoding circuitry, the method comprising:

generating parity information, based on a parity matrix P comprising an m×

k array of b×

b circulant sub-matrices, including m columns of said sub-matrices, wherein m, k and b are integers greater than 1, each column comprising k of the sub-matrices, wherein generating the parity information includes;

dividing information data into a plurality of b sized trunks; and

generating m parity segments, wherein;

each parity segment consists of b bits; and

each parity segment is generated by multiplying each of the k b×

b circulant sub-matrices in a respective column of the parity matrix P by a corresponding trunk of the information data, wherein each multiplication of a b×

b circulant sub-matrix by a corresponding trunk comprises b² concurrent computations, each of which mathematically combines a respective element of the b×

b circulant sub-matrix with a respective element of the corresponding trunk; and

generating the codeword to provide error-correction capability based on the information data and the m parity segments.

2. The method of claim 1, wherein each b×

b circulant sub-matrix comprises elements q(r,s) each having a value in accordance with q(r,s)=q(r+t mod (b), s+t mod (b)), wherein t is any value between 1 and b−

1, and all elements of the b×

b circulant sub-matrix correspond to the elements q(0,s), for s=0 to b−

1, in a first row of the b×

b circulant sub-matrix.

3. The method of claim 1, wherein:

each multiplication of the b×

b circulant sub-matrix by the corresponding trunk comprising b² concurrent computations occurs in a single clock cycle;

each parity segment is generated in k clock cycles; and

all m parity segments are generated in k·

m clock cycles.

4. The method of claim 1, wherein:

each parity segment is generated via k sub-operations; and

in k−

1 of the sub-operations, an intermediate result from a prior sub-operation is mathematically combined with the results from the b² concurrent computations.

5. The method of claim 4, wherein the last one of the k sub-operations generates a final result of b parity bits.

6. The method of claim 4, wherein a different trunk of the information data is used to perform each of the k sub-operations.

7. The method of claim 4, wherein the same trunk of the information data is used to perform the respective j-th sub-operation of the k sub-operations in each of the m columns of the P matrix.

8. The method of claim 1, wherein each multiplication of the b×

b circulant sub-matrix by the corresponding trunk is performed by a set of b² logic gates, the set of b² logic gates are coupled to receive b generator elements q(r,s), wherein for each generator element q(r,s), b of the logic gates receive the same generator element q(r,s).

9. The method of claim 8, wherein each of the b generator elements q(r,s) has a value in accordance with q(r,s)=q(r+t mod (b), s+t mod (b)), wherein t is any value between 1 and b−

1.

10. The method of claim 1, further comprising:

storing two or more distinct parity matrices;

selecting one of the two or more distinct parity matrices; and

generating parity information, based on the selected one of the two or more distinct parity matrices.

11. The method of claim 10, wherein a first parity matrix P1 of the two or more distinct parity matrices comprises an m1×

k1 array of b1×

b1 circulant sub-matrices, and a second parity matrix P2 of the two or more distinct parity matrices comprises an m2×

k2 array of b2×

b2 circulant sub-matrices, wherein one or more of m1, k1 and b1 is unequal to m2, k2 or b2, respectively.

12. An encoder device for generating a QC-LDPC codeword, the encoder comprising:

a P matrix memory configured to store at least one parity matrix P, comprising an m×

k array of b×

b circulant sub-matrices, including m columns of said sub-matrices, wherein m, k and b are integers greater than 1, each column comprising k of the sub-matrices;

an input buffer configured to store information data comprising k·

b bits;

control logic coupled to the input buffer, the reconfigurable P matrix memory and an output buffer, the control logic configured to divide the information data into a plurality of b-sized trunks;

a computational unit configured to generate parity information for the information data, the parity information comprising m parity segments, wherein;

each parity segment consists of b bits; and

each parity segment is generated by the computation unit by multiplying a respective trunk by each of the k b×

b circulant sub-matrices in a respective column of the parity matrix, wherein each multiplication of the respective trunk by a b×

b circulant sub-matrix comprises b² concurrent computations, each of which mathematically combines a respective element of the trunk with a respective element of the b×

b circulant sub-matrix;

the output buffer configured to store the m parity segments; and

the control logic further configured to generate the codeword based on the information data stored in the input buffer and the m parity segments stored in the output buffer.

13. The device of claim 12, wherein each b×

b circulant sub-matrix comprises elements q(r,s) each having a value in accordance with q(r,s)=q(r+t mod (b), s+t mod (b)) where t is any value between 1 and b−

1, and all elements of the b×

b circulant sub-matrix correspond to the elements q(0,s), for s=0 to b−

1, in a first row of the b×

b circulant sub-matrix.

14. The device of claim 12, wherein:

the computational unit is configured to multiply the b×

b circulant sub-matrix by the corresponding trunk in a single clock cycle;

each parity segment is generated in k clock cycles; and

all m parity segments are generated in k−

m clock cycles.

15. The device of claim 12, further including an intermediate results register configured to store intermediate results obtained from the computational unit, and

wherein the computational unit is configured to:

generate each parity segment via k sub-operations; and

in k−

1 of the sub-operations, mathematically combine an intermediate result from a prior sub-operation stored in the intermediate results register with the results from the b² concurrent computations.

16. The device of claim 15, wherein the last one of the k sub-operations generates a final result of b parity bits.

17. The device of claim 15, wherein a different trunk of the information data is used to perform each of the k sub-operations.

18. The device of claim 15, wherein the same trunk of the information data is used to perform the respective j-th sub-operation of the k sub-operations in each of the m columns of the P matrix.

19. The device of claim 12, wherein the computational unit comprises a set of b² logic gates coupled to receive b generator elements q(r,s) from the P-matrix memory, and each multiplication of the b×

b circulant sub-matrix by the corresponding trunk is performed by the set of b² logic gates, wherein for each generator element q(r,s), b of the logic gates receive the same generator element q(r,s).

20. The device of claim 19, wherein each of the b generator elements q(r,s) has a value in accordance with q(r,s)=q(r+t mod (b), s+t mod (b)), wherein t is any value between 1 and b−

1.

21. The device of claim 12, wherein:

the P matrix memory is further configured to store two or more distinct parity matrices;

the control logic is further configured to select one of the two or more distinct parity matrices; and

the computational unit is further configured to generate parity information, based on the selected one of the two or more distinct parity matrices.

22. The device of claim 21, wherein a first parity matrix P1 of the two or more distinct parity matrices comprises an m1×

k1 array of b1×

b1 circulant sub-matrices and a second parity matrix P2 of the two or more distinct parity matrices comprises an m2×

k2 array of b2×

b2 circulant sub-matrices, wherein one or more of m1, k1 and b1 is unequal to m2, k2 or b2, respectively.