Search

CN-116582135-B - Improving error floor performance of BF decoders by identifying unreliable check nodes

CN116582135BCN 116582135 BCN116582135 BCN 116582135BCN-116582135-B

Abstract

The present invention relates to a technique related to improving error floor performance of a bit-flipping (BF) decoder. In some examples, error floor performance is improved by determining a set of unreliable Check Nodes (CNs) and using information about the set of unreliable CNs to calculate the roll-over energy of the Variable Nodes (VNs). In this way, the roll-over energy can be calculated more accurately, thereby reducing false floors. The set of unreliable CNs may be constructed by applying various criteria, such as criteria related to path length to an unsatisfied CN, the degree of VN in a path to an unsatisfied CN, and/or checksum values. The path length and VN degree may be used as selection criteria to determine which CNs are eligible to join the set of unreliable CNs. The checksum value may be used as a trigger condition to construct and/or use a set of unreliable CNs.

Inventors

  • Messam ASSADI
  • DUAN HONGWEI
  • Haman Batiar
  • ZHANG FAN

Assignees

  • 爱思开海力士有限公司

Dates

Publication Date
20260512
Application Date
20230208
Priority Date
20220208

Claims (20)

  1. 1. A method of iterative decoding of low density parity check codewords, i.e., LDPC codewords, the method being implemented on a computing device and comprising: During a first iteration, identifying an unsatisfied CN among a set of check nodes, CNs, wherein the set of CNs represents a result of applying a parity check equation to the LDPC codeword; Determining a set of unreliable CNs such that a path length between each CN in the set of unreliable CNs and the unsatisfied CN is less than or equal to a maximum allowed path length; Calculating a roll-over energy for each VN in a set of VNs based on the total number of unsatisfied CNs directly connected to a variable node, VN, and further based on the total number of satisfied CNs directly connected to the VN and belonging to the set of unreliable CNs; Updating bit values of a set of the VNs, wherein the updating comprises, for each VN in the set of VNs, determining whether to invert the bit values of the VNs based on an inversion energy of the VNs, and Based on the updated bit values of the set of VNs, the bit values of the set of CNs are updated for use during the next iteration.
  2. 2. The method of claim 1, wherein determining the set of unreliable CNs is conditioned on a checksum calculated using bit values of the set of CNs that are less than or equal to a threshold value.
  3. 3. The method of claim 2, wherein the threshold is set to a value associated with an expected checksum in the error floor region.
  4. 4. The method of claim 1, wherein determining the set of unreliable CNs comprises excluding connections to CNs that do not meet CN by a height VN, and wherein the height VN is any VN directly connected to more than a threshold number of CNs.
  5. 5. The method of claim 4, wherein the threshold number of CNs is less than or equal to five.
  6. 6. The method of claim 1, wherein the LDPC codeword is a quasi-cyclic LDPC codeword.
  7. 7. The method of claim 1, wherein the set of VNs corresponds to a parity check matrix divided into cyclic sub-matrices, the method further comprising: The use of the set of unreliable CNs is limited to a subset of VNs in each cyclic sub-matrix when calculating the roll-over energy.
  8. 8. The method of claim 7, further comprising: during the first iteration, selecting a subset of the VNs from a first direction, and During the next iteration, a subset of the VNs is selected starting from a second direction opposite the first direction.
  9. 9. The method of claim 7, wherein the subset of VNs comprises a continuous VN.
  10. 10. The method of claim 7, wherein the subset of VNs comprises discontinuous VNs.
  11. 11. An apparatus, comprising: A memory storing low density parity check code words, i.e., LDPC code words, and One or more processing units: During a first iteration, identifying an unsatisfied CN among a set of check nodes, CNs, wherein the set of CNs represents a result of applying a parity check equation to the LDPC codeword; Determining a set of unreliable CNs such that a path length between each CN in the set of unreliable CNs and the unsatisfied CN is less than or equal to a maximum allowed path length; calculating a roll-over energy for each VN in a set of VNs based on the total number of unsatisfied CNs directly connected to a variable node, VN, and further based on the total number of satisfied CNs directly connected to the VN and belonging to the set of unreliable CNs; Updating the bit values of the set of VNs by determining, for each VN of the set of VNs, whether to invert the bit values of the VN based on the inversion energy of the VN, and Based on the updated bit values of the set of VNs, the bit values of the set of CNs are updated for use during the next iteration.
  12. 12. The apparatus of claim 11, wherein the apparatus determines the set of unreliable CNs only in response to determining that a checksum calculated using bit values of the set of CNs is less than or equal to a threshold value.
  13. 13. The apparatus of claim 12, wherein the threshold is set to a value associated with an expected checksum in the error floor region.
  14. 14. The apparatus according to claim 11, wherein the apparatus excludes from the set of unreliable CNs any CN that does not meet CN by a height VN, and wherein the height VN is any VN directly connected to more than a threshold number of CNs.
  15. 15. The apparatus of claim 14, wherein the threshold number of CNs is less than or equal to five.
  16. 16. The apparatus of claim 11, wherein the set of VNs corresponds to a parity check matrix divided into cyclic sub-matrices, and wherein the one or more processing units are further to limit use of the set of unreliable CNs to a subset of VNs in each cyclic sub-matrix when calculating a roll-over energy.
  17. 17. The apparatus of claim 16, wherein the one or more processing units are further to: during the first iteration, selecting a subset of the VNs from a first direction, and During the next iteration, a subset of the VNs is selected starting from a second direction opposite the first direction.
  18. 18. An error correction system, comprising: a first low density parity check decoder, i.e., a first LDPC decoder, and A second LDPC decoder that decodes an LDPC codeword in a shorter time than the first LDPC decoder, wherein the second LDPC decoder is a bit flipping decoder that: During a first iteration, identifying an unsatisfied CN among a set of check nodes, CNs, wherein the set of CNs represents a result of applying a parity check equation to the LDPC codeword; Determining a set of unreliable CNs such that a path length between each CN in the set of unreliable CNs and the unsatisfied CN is less than or equal to a maximum allowed path length; Calculating a roll-over energy for each VN in a set of VNs based on the total number of unsatisfied CNs directly connected to a variable node, VN, and further based on the total number of satisfied CNs directly connected to the VN and belonging to the set of unreliable CNs; Updating the bit values of the set of VNs by determining, for each VN of the set of VNs, whether to invert the bit values of the VN based on the inversion energy of the VN, and Based on the updated bit values of the set of VNs, the bit values of the set of CNs are updated for use during the next iteration.
  19. 19. The error correction system of claim 18, wherein the bit flip decoder determines the set of unreliable CNs only in response to determining that a checksum calculated using bit values of the set of CNs is less than or equal to a threshold value.
  20. 20. The error correction system of claim 18, wherein the bit flip decoder excludes from the set of unreliable CNs any CN that is connected to an unsatisfied CN by a height VN, and wherein the height VN is any VN that is directly connected to more than a threshold number of CNs.

Description

Improving error floor performance of BF decoders by identifying unreliable check nodes Background Error Correction Codes (ECC) are often used in various types of data storage devices, such as NAND flash memory. ECC is also often used in data transfer processes. The ECC points to a code that adds redundant data or parity data to a message so that a receiver equipped with a decoder can recover the message even if one or more errors occur during transmission or storage. In general, an ECC decoder can correct a limited number of errors, depending on the type of code used and/or the error correction capabilities of the decoder itself. Low Density Parity Check (LDPC) codes are examples of ECC. In ECC decoding (including LDPC decoding), a tradeoff typically needs to be made between error correction capability and computational cost (e.g., power consumption or processing time). In general, the higher the error correction capability, the more complex the decoding process and the higher the power consumption and/or the longer the processing time. A Bit Flipping (BF) decoder and a Minimum Sum (MS) decoder are examples of ECC decoders that may perform LDPC code decoding. BF decoders are significantly faster but have lower error correction capabilities than more complex decoders, such as MS decoders. Disclosure of Invention Techniques related to improving error floor performance (error floor performance) of BF decoders are described. In particular, an example is described that involves reducing an error floor area (error floor region) of a BF decoder by utilizing an improved BF decoding method with information about unreliable Check Nodes (CNs) during a rollover decision. Error floor (error floor) is the area in the Code Failure Rate (CFR) versus Failed Bit Count (FBC) curve where there are more than a certain number of errors (failed bits) in the received codeword sequence that the decoder cannot successfully decode a certain percentage of the codewords in the codeword sequence. The number of code failures in the error floor region is small compared to the number of correctly decoded codewords. However, even a small number of code failures may be unacceptable depending on the performance requirements of the computing environment in which the data is transmitted or stored. In an example, a method for iteratively decoding an LDPC codeword involves identifying, during a first iteration, an unsatisfied CN among a set of CNs. The set of CNs represents the result of applying a parity check equation to an LDPC codeword. The method further involves determining a set of unreliable CNs such that a path length between each CN in the set of unreliable CNs and an unsatisfied CN is less than or equal to a maximum allowed path length. The method further involves calculating a roll-over energy (FLIPPING ENERGY) for each VN in the set of VNs based on a total number of unsatisfied CNs directly connected to the Variable Node (VN). The roll-over energy of each VN in the set of VNs is further calculated based on the total number of satisfied CNs that are directly connected to the VN and belong to the set of unreliable CNs. The method further involves updating the bit values of the set of VNs, wherein updating includes, for each VN in the set of VNs, determining whether to invert the bit values of the VNs based on an inversion energy of the VN. The method further involves updating the bit values of the set of CNs for use during a next iteration based on the updated bit values of the set of VNs. In the example method described above, determining the set of unreliable CNs may be conditioned on a checksum calculated using the bit values of the set of CNs that are less than or equal to the threshold. Further, the threshold may be set to a value associated with an expected checksum in the error floor region. In the example method described above, determining a set of unreliable CNs may involve excluding CNs connected to unsatisfied CNs by a height VN. The height VN may be any VN directly connected to more than a threshold number of CNs. In some embodiments, the threshold number of CNs is less than or equal to five. In the above example method, the LDPC codeword may be a quasi-cyclic LDPC codeword. In the example method described above, the set of VNs may correspond to a parity check matrix divided into cyclic sub-matrices, in which case the method may further involve restricting use of the set of unreliable CNs to a subset of VNs in each cyclic sub-matrix when calculating the roll-over energy. The subset of VNs may be selected by starting to select the subset of VNs from a first direction during a first iteration and starting to select the subset of VNs from a second direction opposite to the first direction during a next iteration. The subset of VNs may be selected to include a continuous VN or a discontinuous VN. In an example, an apparatus includes a memory to store an LDPC codeword. The apparatus further includes means for identifying, durin