Layer specific LDPC decoder

• US 9,813,080 B1
• Filed: 06/23/2015
• Issued: 11/07/2017
• Est. Priority Date: 03/05/2013
• Status: Active Grant

• Current Assignee: Microsemi Solutions (U.S.), Inc. (Microchip Technology Incorporated)
• Original Assignee: Microsemi Solutions (U.S.), Inc. (Microchip Technology Incorporated)
• Inventors: Micheloni, Rino, Marelli, Alessia, Onufryk, Peter Z., Norrie, Christopher I. W.
• Primary Examiner(s): Chaudry, M. Mujtaba
• Application Number:
  US14/747,042
• Time in Patent Office: 868 Days
• Field of Search: None
• CPC Class Codes: H03M 13/112 with correction functions for the min-sum rule, e.g. using an offset or a scaling factor
• CPC Class Codes: H03M 13/114 Shuffled, staggered, layered or turbo decoding schedules

Abstract

A method to decode low-density parity check (LDPC) encoded data using a parity check matrix having a plurality of layers, includes receiving a plurality of values at a decoder. Each value of the plurality of values represents one of a plurality of bits of an LDPC codeword encoded using the parity check matrix. The LDPC codeword is decoded using layered scheduling. A functional adjustment is applied to an approximation of belief propagation used during the decoding. At least one layer specific functional adjustment is used to provide an estimate of the codeword. An apparatus to decode low-density parity check (LDPC) encoded data using a parity check matrix having a plurality of layers includes a decoder. The decoder includes circuitry to decode, layer by layer, the LDPC encoded data utilizing functional adjustments and an algorithmic approximation to belief propagation to provide an estimate of the LDPC codeword. The functional adjustments include layer specific parameters for at least two layers of the parity check matrix associated with the codeword.

Claims

1. An apparatus to decode low-density parity check (LDPC) encoded data using a parity check matrix having a plurality of layers, comprising:

a functional adjustment matrix containing functional adjustment parameters, each location in the functional adjustment matrix to provide a functional adjustment for a layer of the plurality of layers and an iteration of a plurality of iterations, the functional adjustment parameters including a first functional adjustment parameter for a first layer and a first iteration and a second functional adjustment parameter for a second layer and the first iteration, wherein the first functional adjustment parameter is different from the second functional adjustment parameter;

a check node processor coupled to the functional adjustment matrix, the check node processor having circuitry to perform check node processing on a plurality of values for each layer of the parity check matrix associated with a codeword utilizing an approximation to belief propagation, the check node processor configured to identify from the functional adjustment matrix a functional adjustment parameter for the particular layer and the particular iteration of the check node processing and configured to apply the identified functional adjustment parameter during the performing check node processing to alter the results of the check node processing;

a variable node processor coupled to the check node processor, the variable node processor having circuitry to perform variable node processing on a plurality of values for each layer of the parity check matrix associated with the codeword; and

a codeword estimate check processor coupled to the variable node processor, the codeword estimate check processor having circuitry to perform a check of an estimate of the codeword to determine if the estimate is valid.

2. The apparatus of claim 1, wherein the approximation to belief propagation is selected from the group consisting of normalized belief propagation, offset belief propagation, Two-Step Min Sum, Normalized Two-Step Min Sum, Log-FFT, Approximate Min*, RICHARDSON/NOVICHKOV, bit flipping, iterative majority logic, GAUSS-SIEDEL, and split row decoding.

3. The apparatus of claim 1, wherein the approximation to belief propagation uses a Min-Sum algorithm and the functional adjustment parameters are obtained through decoding simulations performed using the Min-Sum algorithm.

4. The apparatus of claim 1, wherein the approximation to belief propagation is a RICHARDSON/NOVICHKOV approximation to belief propagation algorithm, wherein a functional adjustment defines two functional adjustment parameters and the two functional adjustment parameters are obtained through decoding simulations performed using the RICHARDSON/NOVICHKOV approximation to belief propagation algorithm.

5. The apparatus of claim 1, wherein, during the first iteration, the check node processor is configured to apply the first functional adjustment parameter in check node processing of the first layer to modify a result of the check node processing of the first layer and is configured to apply the second functional adjustment parameter in check node processing of the second layer to modify a result of the check node processing of the second layer.

6. The apparatus of claim 1, wherein the check node processor is configured to apply the first functional adjustment parameter in check node processing of the first layer by multiplying a result of the check node processing of the first layer by the first functional adjustment parameter and is configured to apply the second functional adjustment parameter in check node processing of the second layer by multiplying a result of the check node processing of the second layer by the second functional adjustment parameter.

7. The apparatus of claim 1, wherein the check node processor is configured to apply the first functional adjustment parameter in check node processing of the first layer by dividing a result of the check node processing of the first layer by the first functional adjustment parameter and is configured to apply the second functional adjustment parameter in check node processing of the second layer by dividing a result of the check node processing of the second layer by the second functional adjustment parameter.

8. The apparatus of claim 1, wherein the functional adjustment parameters include a third functional adjustment parameter for the first layer and a second iteration, and a fourth functional adjustment parameter for the second layer and the second iteration, wherein the first functional adjustment parameter is different from the third functional adjustment parameter.

9. The apparatus of claim 1, wherein the functional adjustment matrix comprises a table that includes, for each functional adjustment parameter, a corresponding layer number and iteration number.

10. The apparatus of claim 1, wherein the approximation to belief propagation uses an Offset Min Sum algorithm and the functional adjustment parameters are obtained through decoding simulations performed using the Offset Min Sum algorithm, and further wherein the first functional adjustment parameter attenuates a result of the check node processing of the first layer by an amount that is greater than the amount by which the second functional adjustment parameter attenuates a result of the check node processing of the second layer.

11. The apparatus of claim 1, further comprising a plurality of functional adjustment matrices, each functional adjustment matrix in the plurality of functional adjustment matrices corresponding to a bit error rate, and wherein the apparatus is configured to identify a bit error rate and the check node processor is configured to use the functional adjustment matrix corresponding to the identified bit error rate to perform the check node processing.

12. The apparatus circuit of claim 1, wherein at least one functional adjustment parameter is different for each layer and for each iteration.

13. The apparatus of claim 1, further comprising data storage, the functional adjustment matrix stored in the data storage, as a table, prior to the performing check node processing, and wherein the values in the functional adjustment matrix are not changed during the performing check node processing or the performing variable node processing.

14. The apparatus of claim 1, wherein the check node processor is configured to apply the first functional adjustment parameter in the check node processing of the first layer by subtracting the first functional adjustment parameter from a result of the check node processing of the first layer and is configured to apply the second functional adjustment parameter in the check node processing of the second layer by subtracting the second functional adjustment parameter from a result of the check node processing of the second layer.

15. The apparatus of claim 1, wherein the check node processor is configured to apply the first functional adjustment parameter in the check node processing of the first layer by adding the first functional adjustment parameter to a result of the check node processing of the first layer and is configured to apply the second functional adjustment parameter in the check node processing of the second layer by adding the second functional adjustment parameter to a result of the check node processing of the second layer.

16. The apparatus of claim 1, wherein a functional adjustment parameter is used in a user defined function to obtain a quantity from the user defined function and the quantity is used during a check node calculation to change a result of the check node calculation, and wherein the user defined function uses a parameter from a previous layer during a check node calculation of a current layer.

17. The apparatus of claim 1, wherein the plurality of values are log-likelihood ratios (LLRs).

18. The apparatus of claim 5, wherein the approximation to belief propagation is a Two-Step Min Sum decoding algorithm and wherein the check node processing further comprises subtracting a functional adjustment parameter from each result of a check node message calculation performed using the Two-Step Min Sum algorithm, and wherein the first functional adjustment parameter is greater than the second functional adjustment parameter.

19. The apparatus of claim 1, wherein the approximation to belief propagation is a two-step Min Sum decoding algorithm, wherein the functional adjustment matrix includes two functional adjustment parameters corresponding to each layer and each iteration, and wherein:

when signs of incoming messages are the same, a Min Sum decoding algorithm is used for the decoding, the check node processing further including subtracting a first one of the two functional adjustment parameters from a result of each check node message calculation;

or

when signs of incoming messages are not the same, a difference in magnitude of the incoming messages is used as an independent variable in a function that uses a threshold value to compute a check node message value, wherein the other one of the two functional adjustment parameters is used as the threshold value.

20. The apparatus of claim 1, wherein the approximation to belief propagation uses an Approximate Min* algorithm and the functional adjustment parameters are obtained through decoding simulations performed using the Approximate Min* algorithm.

21. The apparatus of claim 1, wherein the approximation to belief propagation uses a normalized two-step Min Sum decoding algorithm, and wherein the identified functional adjustment parameter is only applied when signs of incoming messages are the same, by multiplying the identified functional adjustment parameter by a result of a check node message calculation performed using a normalized Min Sum algorithm.

22. The apparatus of claim 1, further comprising a plurality of functional adjustment matrices, wherein each functional adjustment matrix in the plurality of functional adjustment matrices comprises a table corresponding to a bit error rate, and wherein the apparatus is configured to identify a bit error rate of a nonvolatile memory device coupled to the apparatus and the check node processor is configured to use the table corresponding to the identified bit error rate to identify a functional adjustment parameter.

23. The apparatus of claim 1, wherein the functional adjustment parameters are determined by running simulations on exemplary nonvolatile memory devices at different bit error rates to identify variations between the approximation to belief propagation and a sum-product algorithm for different layers and iterations of the approximation to belief propagation.

24. The apparatus of claim 1, wherein the check node processor has circuitry to perform check node processing on a plurality of values for each layer of the parity check matrix associated with a codeword utilizing log-Fast Fourier transform (Log-FFT) decoding in which the check node processor is configured to apply the identified functional adjustment parameter by multiplying, in the Fourier domain, a magnitude of a check node message by the identified functional adjustment parameter.

25. A nonvolatile memory controller comprising:

an encoder configured to encode data using a low-density parity check (LDPC) matrix having a plurality of layers to generate a codeword;

circuitry for storing a functional adjustment matrix containing functional adjustment parameters, each functional adjustment parameter corresponding to a layer of the plurality of layers and an iteration of a plurality of iterations, the functional adjustment parameters including a first functional adjustment parameter for a first layer and a first iteration and a second functional adjustment parameter for a second layer and the first iteration, wherein the first functional adjustment parameter is different from the second functional adjustment parameter; and

a decoder having circuitry to perform check node processing on a plurality of values for each layer of the LDPC matrix associated with the codeword utilizing an approximation to belief propagation, the decoder configured to identify from the functional adjustment matrix a functional adjustment parameter for the particular layer and the particular iteration of the check node processing and configured to apply the identified functional adjustment parameter to alter the results of the check node processing, the decoder having circuitry to perform variable node processing on a plurality of values for each layer of the LDPC matrix associated with the codeword and having circuitry to perform a check of an estimate of the codeword to determine if the estimate is valid.

26. The nonvolatile memory controller of claim 25, wherein, during the first iteration, the decoder is configured to apply the first functional adjustment parameter in the check node processing of the first layer to modify the results of the check node processing of the first layer and is configured to apply the second functional adjustment parameter in the check node processing of the second layer to modify the results of the check node processing of the second layer.

27. The nonvolatile memory controller of claim 25, wherein the approximation to belief propagation uses an approximation to belief propagation algorithm and the functional adjustment parameters are obtained through decoding simulations performed using the approximation to belief propagation algorithm.

28. The nonvolatile memory controller of claim 25, wherein the approximation to belief propagation decoding is selected from the group consisting of normalized belief propagation, offset belief propagation, Two-Step Min Sum, Normalized Two-Step Min Sum, Log-FFT, Approximate Min*, RICHARDSON/NOVICHKOV, bit flipping, iterative majority logic, GAUSS-SIEDEL and split row decoding.

29. The apparatus of claim 28, wherein the functional adjustment parameters are determined by running simulations on exemplary nonvolatile memory devices at different bit error rates to identify variations between the approximation to belief propagation and a sum-product algorithm for different layers and iterations of the approximation to belief propagation.

30. A nonvolatile memory system comprising:

a plurality of nonvolatile memory devices; and

a nonvolatile memory controller coupled to the nonvolatile memory devices, the nonvolatile memory controller including;

an encoder configured to encode data using a low-density parity check (LDPC) matrix having a plurality of layers to generate a codeword;

circuitry for storing in the nonvolatile memory system a functional adjustment matrix containing functional adjustment parameters, each functional adjustment parameter corresponding to a layer of the plurality of layers and an iteration of a plurality of iterations, the functional adjustment parameters including a first functional adjustment parameter for a first layer and a first iteration and a second functional adjustment parameter for a second layer and the first iteration, wherein the first functional adjustment parameter is different from the second functional adjustment parameter; and

a decoder comprising;

a check node processor coupled to the functional adjustment matrix, the check node processor having circuitry to perform check node processing on a plurality of values for each layer of the LDPC matrix associated with the codeword utilizing an approximation to belief propagation, the nonvolatile memory controller configured to identify from the functional adjustment matrix a functional adjustment parameter for the particular layer and the particular iteration of the check node processing and the check node processor configured to apply the identified functional adjustment parameter during the performing check node processing to alter the results of the check node processing;

a variable node processor coupled to the check node processor, the variable node processor having circuitry to perform variable node processing on a plurality of values for each layer of the LDPC matrix associated with the codeword; and

a codeword estimate check processor coupled to the variable node processor, the codeword estimate check processor having circuitry to perform a check of an estimate of the codeword to determine if the estimate is valid.

31. The nonvolatile memory system of claim 30, wherein the approximation to belief propagation is selected from the group consisting of normalized belief propagation, offset belief propagation, Two-Step Min Sum, Normalized Two-Step Min Sum, Log-FFT, Approximate Min*, RICHARDSON/NOVICHKOV, bit flipping, iterative majority logic, GAUSS-SIEDEL and split row decoding.

32. The nonvolatile memory system of claim 31, wherein the functional adjustment parameters are determined by running simulations on exemplary nonvolatile memory devices at different bit error rates to identify variations between the approximation to belief propagation and a sum-product algorithm for different layers and iterations of the approximation to belief propagation.

33. The nonvolatile memory system of claim 30, further comprising a plurality of functional adjustment matrices, each functional adjustment matrix in the plurality of functional adjustment matrices corresponding to a bit error rate, and wherein the apparatus is configured to identify a bit error rate of a nonvolatile memory device of the plurality of nonvolatile memory devices and the check node processor is configured to use the functional adjustment matrix corresponding to the identified bit error rate to perform the check node processing.