Multi-level LDPC layer decoder
Various embodiments of the present invention are related to methods and apparatuses for decoding data, and more particularly to methods and apparatuses for multi-level layered LDPC decoding. For example, in one embodiment an apparatus includes a variable node processor and a check node processor. The variable node processor is operable to generate variable node to check node messages and to calculate perceived values based on check node to variable node messages. The check node processor is operable to generate the check node to variable node messages and to calculate checksums based on variable node to check node messages. The check node processor includes a min finder circuit operable to identify a minimum, a next minimum and an index of minimum value in the variable node to check node messages. The variable node processor and check node processor are operable to perform layered multi-level decoding.
1. An apparatus for multi-level layered low density parity check decoding comprising:
a variable node processor, wherein the variable node processor is operable to generate variable node to check node messages and to calculate perceived values based on check node to variable node messages; and
a check node processor, wherein the check node processor is operable to generate the check node to variable node messages and to calculate checksums based on variable node to check node messages, the check node processor comprising a min finder circuit operable to identify a minimum, a next minimum and an index of minimum value in the variable node to check node messages, wherein the variable node processor and check node processor are operable to perform layered multi-level decoding.
2. The apparatus of claim 1 , wherein the variable node processor comprises an adder operable to add Q values to previous layer check node to variable messages for a previous layer to yield total soft log likelihood ratio values for the previous layer.
3. The apparatus of claim 1 , wherein the variable node processor comprises a normalization circuit operable to convert a message between a first format comprising a hard decision and a plurality of log likelihood ratio values and a second format comprises a second plurality of log likelihood ratio values, wherein the second format has a greater number of the log likelihood ratio values than the first format.
4. The apparatus of claim 1 , wherein the variable node processor comprises a shifter operable to shift total soft log likelihood ratio messages from a previous layer to a current layer.
5. The apparatus of claim 4 , wherein the previous layer and the current layer comprise circulants.
6. The apparatus of claim 1 , further comprising a shifter circuit operable to rearrange total soft log likelihood ratio messages to yield column ordered total soft log likelihood ratio messages.
7. The apparatus of claim 6 , wherein the shifter circuit is operable to shift the column ordered total soft log likelihood ratio messages from a previous layer to a current layer and to generate a hard decision.
8. The apparatus of claim 1 , wherein the variable node processor comprises a subtractor operable to subtract a current layer check node to variable node message from a current layer total soft log likelihood ratio message.
9. The apparatus of claim 8 , wherein the variable node processor further comprises a normalization circuit operable to convert a format of an output of the subtractor.
10. The apparatus of claim 1 , wherein the check node processor further comprises a scaler operable to scale the variable node to check node messages.
11. The apparatus of claim 1 , wherein the check node processor comprises a current layer message generator operable to generate a current layer check node to variable node message from an output of the min finder circuit.
12. The apparatus of claim 1 , wherein the check node processor comprises a previous layer message generator operable to generate a previous layer check node to variable node message from an output of the min finder circuit.
13. The apparatus of claim 1 , wherein the variable node processor and the check node processor are operable to process a plurality of circulant sub-matrices of an H matrix in parallel.
14. The apparatus of claim 1 , wherein the variable node comprises:
an adder operable to add Q values to a previous layer check node to variable message for a previous layer to yield total soft log likelihood ratio values for the previous layer;
a normalization circuit operable to convert the total soft log likelihood ratio values for the previous layer between a first format comprising a hard decision and a plurality of log likelihood ratio values and a second format comprises a second plurality of log likelihood ratio values to yield P messages for the previous layer, wherein the second format has a greater number of the log likelihood ratio values than the first format;
a shifter operable to shift the P messages from the previous layer to a current layer;
a subtractor operable to subtract a current layer check node to variable node message from the P messages for the current layer to yield D messages for the current layer; and
a second normalization circuit operable to convert the D messages for the current layer from the second format to the first format to yield the variable node to check node messages; and
wherein the check node processor further comprises:
a current layer message generator operable to generate the current layer check node to variable node message from an output of the min finder circuit; and
a previous layer message generator operable to generate the previous layer check node to variable node message from an output of the min finder circuit.
15. The apparatus of claim 1 , wherein the apparatus is implemented as an integrated circuit.
16. The apparatus of claim 1 , wherein the apparatus is incorporated in a storage device.
17. The apparatus of claim 1 , wherein the apparatus is incorporated in a storage system comprising a redundant array of independent disks.
18. The apparatus of claim 1 , wherein the apparatus is incorporated in a data transmission device.
19. A storage system comprising:
a storage medium maintaining a data set;
a write head operable to magnetically record the data set to the storage medium; and
a multi-level low density parity check layer decoder comprising:
a variable node processor, wherein the variable node processor is operable to generate variable node to check node messages and to calculate perceived values based on check node to variable node messages; and
a check node processor, wherein the check node processor is operable to generate the check node to variable node messages and to calculate checksums based on variable node to check node messages, the check node processor comprising a min finder circuit operable to identify a minimum, a next minimum and an index of minimum value in the variable node to check node messages.
20. A method of decoding data in a multi-level low density parity check layer decoder, comprising:
in a variable node processor, generating variable node to check node messages and calculating perceived values based on check node to variable node messages; and
in a check node processor, generating the check node to variable node messages and calculating checksums based on the variable node to check node messages, the check node processor comprising a min finder circuit operable to identify a minimum, a next minimum and an index of minimum value in the variable node to check node messages, wherein the variable node processor and check node processor are operable to perform layered multi-level decoding.