System and method for reduced memory storage in LDPC decoding
View Patent ↗A low-density parity check (LDPC) decoder is provided that eliminates the need to calculate customized check node codeword estimates by considering the check node processor and the variable node processor as a single processer having a shared memory for storing common variables to be used during both the check node processing and the variable node processing of the iterative decoding method.
1. A method for decoding low-density parity check (LDPC) encoded data using a parity check matrix, the parity check matrix to define the connections between a plurality of check nodes and a plurality of variable nodes, the method comprising:
performing, at a processor of a LDPC decoder, check node processing at one check node of the plurality of check nodes using a variable node codeword estimate received from each of the plurality of variable nodes connected to the check node to generate a common check node codeword estimate, and sharing the common check node codeword estimate with each of the plurality of variable nodes connected to the one check node;
performing, at the LDPC decoder, variable node processing at one variable node of the plurality of variable nodes after removing a contribution of the one variable node from the common check node codeword estimate to generate an updated variable node codeword estimate;
calculating, at the LDPC decoder, a final codeword estimate as the sum of each of the common check node codeword estimates received at the one variable node and the variable node codeword estimate;
performing, at the LDPC decoder, a check of the final codeword estimate to determine if the final codeword estimate is a valid codeword; and
if the final codeword estimate is not determined to be a valid codeword, removing a contribution of the one check node from the updated variable node codeword estimate and repeating the steps of performing check node processing and performing variable node processing until the final codeword estimate is determined to be a valid codeword or until a maximum number of iterations is reached.
2. The method of claim 1 , further comprising:
receiving a plurality of log-likelihood ratios (LLRs) at each of the plurality of variable nodes of the decoder, each of the plurality of LLRs representing one of a plurality of bits of an LDPC codeword encoded using the parity check matrix; and
sharing the plurality of LLRs from each of the plurality of variable nodes with each of the connected check nodes as the variable node codeword estimates.
3. The method of claim 2 , wherein receiving the plurality of LLRs further comprises receiving the plurality of LLRs from a nonvolatile memory storage module.
4. The method of claim 1 , wherein performing check node processing further comprises performing check node processing using a min-sum decoding process.
5. The method of claim 4 , wherein performing check node processing using a min-sum decoding process further comprises selecting the two most minimum magnitude variable node codeword estimates from the variable node codeword estimates received from each of the plurality of variable nodes to generate the common check node codeword estimate.
6. The method of claim 5 , wherein performing variable node processing at the one variable node of the plurality of variable nodes after removing a contribution of the one variable node from the common check node codeword further comprises:
identifying the one of the two most minimum magnitude check node codeword estimates shared by the one check node that was contributed by the one variable node in the generation of the common check node codeword estimate; and
calculating a sum of the variable node codeword estimate of the one variable node and the identified one of the two most minimum magnitude check node codeword estimates shared by the one check node that was not contributed by the one variable node in the generation of the common check node codeword estimate from each of the plurality of check nodes connected to the one variable node to generate the updated variable node codeword estimate.
7. The method of claim 6 , wherein removing a contribution of the one check node from the updated variable node codeword estimate if the final node codeword estimate is not determined to be a valid code word further comprises, subtracting the identified one of the two most minimum variable node codeword estimates from the updated variable node codeword estimate.
8. The method of claim 1 , wherein the common check node codeword estimate comprises a common sign term calculated from the variable node codeword estimates received from each of the plurality of variable nodes connected to the one check node, and wherein removing the contribution of the one variable node from the common check node codeword estimate further comprises removing the contribution of the one variable node from the common sign term of the common check node codeword estimate.
9. The method of claim 1 , wherein performing check node processing further comprises performing check node processing using a sum-product decoding process.
10. The method of claim 9 , wherein performing check node processing using a sum-product decoding process further comprises:
determining a phi-function for each of the variable node codeword estimates received from each of the plurality of variable nodes; and
calculating a sum of the phi-functions for each of the variable node codeword estimates to generate the common check node codeword estimate.
11. The method of claim 10 , wherein determining a phi-function for each of the variable node codeword estimates further comprises accessing a phi-function look-up table to determine the phi-function.
12. The method of claim 10 , wherein determining a phi-function for each of the variable node codeword estimates further comprises performing a phi-function combinatorial decode to determine the phi-function.
13. The method of claim 10 , wherein performing variable node processing at the one variable node of the plurality of variable nodes after removing a contribution of the one variable node from the common check node codeword further comprises:
determining a phi-function of the variable node codeword estimate of the one variable node;
subtracting the phi-function of the variable node codeword estimate of the one variable node from the common check node codeword estimate; and
calculating a sum of the variable node codeword estimate of the one variable node and the result of the subtraction.
14. The method of claim 13 , wherein determining the phi-function of the one variable node codeword estimate further comprises accessing a phi-function look-up table to determine the phi-function.
15. The method of claim 13 , wherein determining the phi-function of the one variable node codeword estimate further comprises accessing a phi-function lookup table comprising entries for the sum of the variable node codeword estimates of the one variable node and the result of the subtraction.
16. The method of claim 13 , wherein determining the phi-function of the one variable node codeword estimate further comprises performing a phi-function combinatorial decode to determine the phi-function.
17. An LDPC decoder for decoding low-density parity check (LDPC) encoded data, the LDPC encoded data comprising a plurality of log-likelihood ratios (LLRs), each of the plurality of LLRs representing one of a plurality of bits of an LDPC codeword encoded using a parity check matrix, the decoder comprising:
a check node and variable node processor for performing check node processing at one check node of the plurality of check nodes using a variable node codeword estimate received from each of the plurality of variable nodes connected to the check node to generate a common check node codeword estimate, for sharing the common check node codeword estimate with each of the plurality of variable nodes connected to the one check node, for performing variable node processing at one variable node of the plurality of variable nodes after removing a contribution of the one variable node from the common check node codeword estimate to generate an updated variable node codeword estimate, and for calculating a final codeword estimate;
a codeword estimate check processor coupled to the check node and variable node processor, the codeword estimate check processor for performing a check of the final codeword estimate to determine if the final codeword estimate is a valid codeword; and
wherein the check node and variable node processor is configured for removing a contribution of the one check node from the updated variable node codeword estimate if the final codeword estimate is not determined to be a valid codeword, and for repeating the check node processing and variable node processing until the final codeword estimate is determined to be a valid codeword or until a maximum number of iterations is reached.
18. The decoder of claim 17 , further comprising an iteration counter coupled to the codeword estimate check processor, the iteration counter to determine if the maximum number of iterations of the iterative decoding is reached.
19. The decoder of claim 17 , further comprising a phi-function look-up table coupled to the check node and variable node processor.
20. The decoder of claim 17 , further comprising a phi-function combinatorial decode logic circuit coupled to the check node and variable node processor.
21. An LDPC decoder for decoding low-density parity check (LDPC) encoded data, the LDPC encoded data comprising a plurality of log-likelihood ratios (LLRs), each of the plurality of LLRs representing one of a plurality of bits of an LDPC codeword encoded using a parity check matrix, the decoder comprising:
a check node and variable node processor for performing check node processing at one check node of the plurality of check nodes using a sum-product decode process and a variable node codeword estimate received from each of the plurality of variable nodes connected to the check node to generate a common check node codeword estimate, for sharing the common check node codeword estimate with each of the plurality of variable nodes connected to the one check node, for performing variable node processing at one variable node of the plurality of variable nodes using sum-product decode processing after removing a contribution of the one variable node from the common check node codeword estimate to generate an updated variable node codeword estimate and for calculating a final codeword estimate;
a codeword estimate check processor coupled to the check node and variable node processor, the codeword estimate check processor for performing a check of the final codeword estimate to determine if the final codeword estimate is a valid codeword; and
wherein the check node and variable node processor is configured for removing a contribution of the one check node from the updated variable node codeword estimate if the final codeword estimate is not determined to be a valid codeword, and for repeating the check node processing and variable node processing until the final codeword estimate is determined to be a valid codeword or until a maximum number of iterations is reached.