Non-binary LDPC decoder with low latency scheduling
Various embodiments of the present invention provide systems and methods for decoding of non-binary LDPC codes. For example, a low density parity check data decoder is disclosed that includes a variable node processor operable to perform variable node updates based at least in part on check node to variable node message vectors, a check node processor operable to perform check node updates and to generate the check node to variable node message vectors, and a scheduler operable to cause the variable node processor to use check node to variable node message vectors from multiple decoding iterations when performing the variable node updates for a given decoding iteration.
1. An apparatus for low density parity check data decoding comprising:
a variable node processor operable to perform variable node updates based at least in part on check node to variable node message vectors;
a check node processor operable to perform check node updates and to generate the check node to variable node message vectors; and
a scheduler operable to cause the variable node processor to use check node to variable node message vectors from multiple decoding iterations when performing the variable node updates for a given decoding iteration, wherein the decoding comprises non-layer decoding.
2. The apparatus of claim 1 , wherein the scheduler is operable to switch the variable node processor between the check node to variable node message vectors from the multiple decoding iterations when the check node processor completes the check node to variable node message vectors for one of the multiple decoding iterations.
3. The apparatus of claim 2 , wherein the variable node processor is switched when the check node processor completes the check node to variable node message vectors for a last one of the multiple decoding iterations.
4. The apparatus of claim 1 , wherein the variable node processor is operable to generate variable node to check node messages for a block of data in the given decoding iteration based in part on the check node to variable node message vectors from the multiple decoding iterations.
5. The apparatus of claim 1 , wherein the given decoding iteration comprises a current decoding iteration, and wherein the multiple decoding iterations comprise a previous decoding iteration prior to the current decoding iteration and an earlier decoding iteration prior to the previous decoding iteration.
6. The apparatus of claim 1 , wherein the scheduler is operable to cause the variable node processor to perform successive decoding iterations without idle cycles between the successive decoding iterations.
7. The apparatus of claim 1 , wherein the scheduler is operable to cause the check node processor to perform successive decoding iterations without idle cycles between the successive decoding iterations.
8. The apparatus of claim 1 , wherein the check node processor performs min-sum based low density parity checking.
9. The apparatus of claim 8 , wherein the check node processor comprises finding lowest log likelihood ratio values, second lowest LLR values, and index of lowest LLR.
10. The apparatus of claim 1 , wherein the apparatus is implemented as an integrated circuit.
11. The apparatus of claim 1 , wherein the apparatus is incorporated in a storage device.
12. The apparatus of claim 11 , wherein the storage device comprises:
a storage medium maintaining a data set; and
a read/write head assembly operable to sense the data set on the storage medium and to provide an analog output corresponding to the data set, wherein the variable node processor is operable to receive a signal derived from the analog output.
13. The apparatus of claim 11 , wherein the storage device comprises a redundant array of independent disks.
14. The apparatus of claim 1 , wherein the apparatus is incorporated in a transmission system.
15. A method for decoding non-binary low density parity check encoded data, the method comprising:
generating check node to variable node messages for a current decoding iteration in a check node processor of a non-layer low density parity check decoder circuit; and
performing variable node updates for a next decoding iteration in a variable node processor of the non-layer low density parity check decoder circuit based in part on check node to variable node messages for a previous decoding iteration while the check node processor is generating check node to variable node messages for the current decoding iteration, and further based in part on the check node to variable node messages for the current decoding iteration.
16. The method of claim 15 , further comprising switching from the check node to variable node messages for a previous decoding iteration to the check node to variable node messages for the current decoding iteration when the check node processor completes the check node to variable node messages for the current decoding iteration.
17. The method of claim 15 , further comprising generating the check node to variable node message based on a min-sum calculation.
18. The method of claim 17 , wherein the min-sum calculation comprises finding lowest LLR values, second LLR values and indexes of lowest LLR values.
19. The method of claim 15 , wherein no delays are inserted between decoding iterations in the check node processor or in the variable node processor.
20. A storage system comprising:
a storage medium maintaining a data set;
a read/write head assembly operable to sense the data set on the storage medium and to provide an analog output corresponding to the data set;
an analog to digital converter operable to sample a continuous signal to yield a digital output; and
a non-layer low density parity check decoder operable to decode the digital output comprising:
a variable node processor operable to perform variable node updates based at least in part on check node to variable node message vectors;
a check node processor operable to perform check node updates and to generate the check node to variable node message vectors; and
a scheduler operable to cause the variable node processor to use check node to variable node message vectors from multiple decoding iterations when performing the variable node updates for a given decoding iteration.