Method and apparatus for layer-specific LDPC decoding

• US 10,230,396 B1
• Filed: 09/25/2017
• Issued: 03/12/2019
• 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, Mujtaba M
• Application Number:
  US15/715,011
• Time in Patent Office: 533 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1048 using arrangements adapted for a specific error detection or correction feature
• CPC Class Codes: H03M 13/1108 Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
• 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
• CPC Class Codes: H03M 13/6577 Representation or format of variables, register sizes or word-lengths and quantization
• CPC Class Codes: H03M 13/658 Scaling by multiplication or division
• CPC Class Codes: H03M 13/6583 Normalization other than scaling, e.g. by subtraction

Abstract

Methods and apparatus are disclosed for decoding low-density parity check (LDPC) encoded data using a parity check matrix having a plurality of layers. The apparatus includes a decoder having circuitry to decode, layer by layer, a LDPC codeword utilizing functional adjustments and an algorithmic approximation to belief propagation to provide an estimate of the LDPC codeword, the functional adjustments including layer specific parameters for at least two layers of the parity check matrix associated with the LDPC codeword.

Claims

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

receiving a plurality of values at a decoder, each value of the plurality of values representing one of a plurality of bits of an LDPC codeword encoded using the parity check matrix;

decoding the LDPC codeword using layered scheduling; and

applying a functional adjustment to an approximation of belief propagation used during the decoding, wherein the applying includes applying a first functional adjustment parameter to a first layer and applying a second functional adjustment parameter to a second layer to provide an estimate of a codeword, wherein the first functional adjustment parameter is different from the second functional adjustment parameter.

2. The method 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 method of claim 1, wherein the approximation of belief propagation is a RICHARDSON/NOVICHKOV approximation to belief propagation algorithm and wherein the first functional adjustment parameter and the second functional adjustment parameter are obtained through decoding simulations performed using the RICHARD SON/NOVICHKOV approximation of belief propagation algorithm.

4. The method of claim 1, wherein the layer specific functional adjustment is a user defined function and the applying uses a quantity from the user defined function 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.

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

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

a decoder, the decoder including circuitry to decode, layer by layer, a LDPC codeword utilizing functional adjustments and an algorithmic approximation to belief propagation to provide an estimate of the LDPC codeword, the functional adjustments including layer specific parameters for at least two layers of the parity check matrix associated with the LDPC codeword, the layer specific parameters including a first functional adjustment parameter to modify the results of processing of a first layer of the plurality of layers and a second functional adjustment parameter to modify the results of processing of a second layer of the plurality of layers, the second functional adjustment parameter different from the first functional adjustment parameter.

7. The apparatus of claim 6, wherein the algorithmic 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.

8. The apparatus of claim 6, wherein the first functional adjustment parameter and a third functional adjustment parameter are obtained through decoding simulations performed using the RICHARDSON/NOVICHKOV approximation to belief propagation, the third functional parameter applied to the first layer to further modify the results of the processing of the first layer.

9. The apparatus of claim 6, wherein the circuitry adds the first functional adjustment parameter during the processing of the first layer to modify the results of the processing of the first layer and adds the second functional adjustment parameter during the processing of the second layer to modify the results of the processing of the second layer.

10. The apparatus of claim 6, wherein the decoder is configured to output a codeword estimate or perform another iteration of decoding if the codeword estimate is not valid.

11. The apparatus of claim 6, wherein each layer is one or more circulant rows in the parity check matrix associated with the LDPC codeword.

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

a 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 algorithm that approximates belief propagation, the algorithm applying a first functional adjustment parameter in the check node processing of a first layer to modify the results of the check node processing of the first layer and applying a 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, the second functional adjustment parameter different from the first functional adjustment parameter;

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;

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 a codeword; and

wherein the integrated circuit is configured to output the codeword if the estimate is a codeword or perform another iteration of decoding if the estimate is not a codeword.

13. The integrated circuit of claim 12, wherein the plurality of values for each layer are log-likelihood ratios (LLRs).

14. The integrated circuit of claim 12, wherein the algorithm that approximates belief propagation is an off-set Min Sum decoding algorithm that subtracts the first functional adjustment parameter during a check node message calculation.

15. The integrated circuit of claim 12, wherein the algorithm that approximates belief propagation is a two-step Min Sum decoding algorithm, wherein;

1. when signs of incoming messages are the same, a Min Sum decoding algorithm is implemented in the circuitry to decode;

or

2. 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 to compute a new value for the messages used in the circuitry to decode.

16. The integrated circuit of claim 12, wherein the algorithm that approximates belief propagation is a normalized two-step Min Sum decoding algorithm, wherein;

1. when signs of incoming messages are the same a normalized Min Sum algorithm is implemented in the circuitry to decode, and the circuitry multiplies first functional adjustment parameter by a message value during decoding of the first layer;

or

2. when signs of incoming messages are not the same, a new message value m_j is computed using the equation m_j=Σ

w_i*m_i, with constraint Σ

w_i=1, and {i=1, j} and used in the circuitry to decode.

17. The integrated circuit of claim 12, wherein the functional adjustment provides at least three different functional adjustment parameters for use during decoding of a layer.

18. The integrated circuit of claim 12, wherein, whether a stored parameter is used to apply the functional adjustment is determined by a message value during decoding.

19. The integrated circuit of claim 12, wherein each layer is one or more circulant rows in the parity check matrix associated with the codeword.

20. The integrated circuit of claim 12, wherein the algorithm that approximates 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.