Encoder for quasi-cyclic low-density parity-check codes over subfields using fourier transform
A quasi-cyclic low-density parity-check (QC-LDPC) encoder includes a Fourier transform circuit configured to receive an input message and to generate a transformed message based on the input message. The transformed message includes leading symbols with indices corresponding to leading elements of cyclotomic cosets of a finite field with respect to a subfield. The QC-LDPC encoder further includes a matrix multiplier circuit configured to multiply the leading symbols of the transformed message by leading symbols of a transformed LDPC generator matrix to generate leading symbols of transformed parity symbols associated with an LDPC codeword. The QC-LDPC encoder is configured to provide the leading symbols of the transformed parity symbols to an inverse Fourier transform circuit to generate parity information of the LDPC codeword.
1. A data storage device comprising:
a non-volatile memory; and
a quasi-cyclic low-density parity-check (QC-LDPC) encoder configured to encode data for storage into the non-volatile memory, the QC-LDPC encoder including:
a Fourier transform circuit configured to receive an input message and to generate a transformed message based on the input message, wherein the transformed message includes leading symbols with indices corresponding to leading elements of cyclotomic cosets of a finite field with respect to a subfield; and
a matrix multiplier circuit configured to multiply the leading symbols of the transformed message by leading symbols of a transformed LDPC generator matrix to generate leading symbols of transformed parity symbols associated with an LDPC codeword,
wherein the QC-LDPC encoder is configured to provide the leading symbols of the transformed parity symbols to an inverse Fourier transform circuit to generate parity information of the LDPC codeword.
2. The data storage device of claim 1 , wherein the transformed message further includes non-leading symbols, and wherein the matrix multiplier circuit does not multiply the non-leading symbols of the transformed message with any symbols of the transformed LDPC generator matrix.
3. The data storage device of claim 1 , further comprising circuitry configured to combine the parity information with the input message to generate the LDPC codeword.
4. The data storage device of claim 3 , wherein the Fourier transform circuit and the circuitry are each configured to receive the input message.
5. The data storage device of claim 3 , wherein the circuitry includes selection logic configured to concatenate the input message and the parity information to generate the LDPC codeword.
6. The data storage device of claim 1 , wherein the Fourier transform circuit is configured to receive all blocks of symbols of the input message, and wherein the inverse Fourier transform circuit is configured to receive only parity symbols.
7. The data storage device of claim 1 , wherein the LDPC codeword is formed of binary symbols.
8. The data storage device of claim 1 , wherein the LDPC codeword is formed of non-binary symbols.
9. The data storage device of claim 1 , further comprising a controller that is operationally coupled to the non-volatile memory, wherein the controller includes the QC-LDPC encoder.
10. The data storage device of claim 1 , wherein the non-volatile memory has a three-dimensional (3D) configuration that is monolithically formed in one or more physical levels of arrays of memory cells having an active area above a silicon substrate, and further comprising circuitry associated with operation of the memory cells.
11. A method comprising:
at a quasi-cyclic low-density parity-check (QC-LDPC) encoder of a data storage device, performing:
receiving an input message;
generating a transformed message based on the input message, wherein the transformed message includes leading symbols with indices corresponding to leading elements of cyclotomic cosets of a finite field with respect to a subfield;
multiplying the leading symbols of the transformed message by leading symbols of a transformed LDPC generator matrix to generate leading symbols of transformed parity symbols associated with an LDPC codeword; and
providing the leading symbols of the transformed parity symbols to an inverse Fourier transform circuit to generate parity information of the LDPC codeword.
12. The method of claim 11 , further comprising combining the parity information with the input message to generate the LDPC codeword.
13. The method of claim 12 , wherein the parity information is concatenated with the input message to generate the LDPC codeword.
14. The method of claim 11 , wherein the transformed message is generated by a Fourier transform circuit, and wherein the leading symbols of the transformed parity symbols are generated by a matrix multiplier circuit.
15. The method of claim 14 , wherein the transformed message further includes non-leading symbols, and wherein the matrix multiplier circuit does not multiply the non-leading symbols of the transformed message with any symbols of the transformed LDPC generator matrix.
16. The method of claim 14 , wherein the Fourier transform circuit receives all blocks of symbols of the input message, and wherein the inverse Fourier transform circuit receives only parity symbols.
17. The method of claim 11 , wherein the LDPC codeword is formed of binary symbols.
18. The method of claim 11 , wherein the LDPC codeword is formed of non-binary symbols.
19. The method of claim 11 , wherein the data storage device further includes a controller and a non-volatile memory that is operationally coupled to the controller, and wherein the controller includes the QC-LDPC encoder.
20. The method of claim 19 , wherein the non-volatile memory has a three-dimensional (3D) configuration that is monolithically formed in one or more physical levels of arrays of memory cells having an active area above a silicon substrate, and wherein the non-volatile memory further includes circuitry associated with operation of the memory cells.