Low density parity code (LDPC) decoding for memory with multiple log likelihood ratio (LLR) decoders

• US 8,301,979 B2
• Filed: 10/07/2009
• Issued: 10/30/2012
• Est. Priority Date: 10/07/2008
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk IL Ltd. (Western Digital Corporation)
• Inventors: Sharon, Eran, Alrod, Idan, Navon, Ariel, Lieber, Opher
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): Arcos, Jeison C
• Application Number:
  US12/574,982
• Publication Number:
  US 20100088575A1
• Time in Patent Office: 1,119 Days
• Field of Search: 708/233, 708/250, 714/728
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1072 in multilevel memories
• CPC Class Codes: H03M 13/1108 Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
• CPC Class Codes: H03M 13/1128 Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations
• CPC Class Codes: H03M 13/1142 using trapping sets
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence
• CPC Class Codes: H03M 13/6591 Truncation, saturation and clamping

Abstract

Data stored in memory is decoded using iterative probabilistic decoding and multiple decoders. A first decoder attempts to decode a representation of a codeword. If the attempt is unsuccessful, a second decoder attempts to decode the representation of a codeword. The second decoder may have a lower resolution than the first decoder. Probability values such as logarithmic likelihood ratio (LLR) values may be clipped in the second decoder. This approach can overcome trapping sets while exhibiting low complexity and high performance. Further, it can be implemented on existing decoders such as those used in current memory devices.

Claims

1. A computer-implemented method of decoding a representation of a codeword, comprising the steps of:

(a) applying a decoder to the representation of the codeword, the representation of the codeword comprises a set of bits, and the decoder associates a bit estimation with each bit indicating a probable value of the bit, each bit estimation has a respective absolute value;

(b) if the applying of the decoder fails to decode the representation of the codeword, reducing the respective absolute value of each bit estimation to a certain value, thereby obtaining a modified decoder; and

(c) applying the modified decoder to the representation of the codeword.

2. The computer-implemented method of claim 1, wherein the decoder comprises a soft decoder using a message passing algorithm.

3. The computer-implemented method of claim 1, wherein the set of bits comprises information bits and a parity bit.

4. The computer-implemented method of claim 3, wherein each bit estimation comprises a logarithmic likelihood ratio value.

5. The computer-implemented method of claim 3, wherein the respective absolute value of each bit estimation is greater when a reliability of the associated bit is greater.

6. The computer-implemented method of claim 5, wherein a polarity of each bit estimation indicates whether the associated bit is more likely a 0 or a 1.

7. The computer-implemented method of claim 1, wherein:

the decoding is performed in a multi-level non-volatile memory device and the codeword represents one of a plurality of data states in the multi-level non-volatile memory device.

8. A non-transitory processor-readable storage medium having processor-readable code embodied thereon, where the processor-readable code, when executed, performs the computer-implemented method of claim 1.

9. A decoder for a memory device which performs the computer-implemented method of claim 1.

10. A computer-implemented method of decoding a representation of a codeword, comprising the steps of:

(a) applying a decoder to the representation of the codeword;

(b) if the applying of the decoder terminates decoding of the representation of the codeword before convergence is reached;

changing a parameter of the decoder, wherein the parameter is associated with a reliability measure of at least one bit of the representation of the codeword, thereby obtaining a modified decoder; and

(c) applying the modified decoder to the representation of the codeword.

11. The computer-implemented method of claim 10, wherein the decoder comprises a soft decoder using a message passing algorithm.

12. The computer-implemented method of claim 10, wherein the parameter is used in determining a reliability measure for at least one step of the decoding algorithm.

13. The computer-implemented method of claim 12, wherein the reliability measure is a logarithmic likelihood ratio value.

14. The computer-implemented method of claim 13, wherein the parameter includes a parameter for clipping the logarithmic likelihood ratio value.

15. The computer-implemented method of claim 14, wherein the clipping is performed on an absolute value of the logarithmic likelihood ratio value.

16. The computer-implemented method of claim 10, wherein:

the decoding is performed in a multi-level non-volatile memory device and the codeword represents one of a plurality of data states in the multi-level non-volatile memory device.

17. A decoder for a memory device which performs the computer-implemented method of claim 10.

18. A non-transitory processor-readable storage medium having processor-readable code embodied thereon, where the processor-readable code, when executed, performs the computer-implemented method of claim 10.

19. A decoding apparatus, comprising:

a memory array; and

one or more controllers, the one or more controllers read a representation of a codeword from the memory array and apply a decoder to the representation of the codeword, the representation of the codeword comprises a set of bits, and the decoder associates a bit estimation with each bit indicating a probable value of the bit, each bit estimation has a respective absolute value, and if the decoder fails to decode the representation of the codeword, clips the respective absolute value of each bit estimation to a certain value thereby obtaining a modified decoder, and applies the modified decoder to the representation of the codeword.

20. The decoding apparatus of claim 19, wherein the decoder comprises a soft decoder using a message passing algorithm.

21. The decoding apparatus of claim 19, wherein the set of bits comprises information bits and a parity bit.

22. The decoding apparatus of claim 21, wherein each bit estimation comprises a logarithmic likelihood ratio value.

23. The decoding apparatus of claim 21, wherein the respective absolute value of each bit estimation is greater when a reliability of the associated bit is greater.

24. The decoding apparatus of claim 23, wherein a polarity of each bit estimation indicates whether the associated bit is more likely a 0 or a 1.

25. A computer-implemented method of decoding a representation of a codeword, comprising:

attempting to decode a representation of the codeword using iterative probabilistic decoding at a first resolution, the iterative probabilistic decoding uses reliability metrics comprising logarithmic likelihood ratios, and the first resolution comprises a first bit resolution by which the logarithmic likelihood ratios are computed; and

if the attempting fails, attempting to decode the representation of the codeword using iterative probabilistic decoding at a second, lower resolution the second, lower resolution comprises a second bit resolution, lower than the first bit resolution, by which the logarithmic likelihood ratios are computed.

26. A memory apparatus, comprising:

a memory array; and

one or more controllers, including a first decoder, an associated first processing unit, a second decoder, and an associated second processing unit, the one or more controllers read a representation of a codeword from the memory array and cause the first processing unit to provide first initial logarithmic likelihood ratio values to the first decoder, in response to which the first decoder attempts to decode the representation of the codeword using iterative probabilistic decoding, starting with the first initial logarithmic likelihood ratio values and ending with final logarithmic likelihood ratio values which result from operation of the first decoder, and if the attempt fails, cause the first decoder to provide the representation of the codeword and the final logarithmic likelihood ratio values to the second processing unit, where the second processing unit reduces magnitudes of at least some of the final logarithmic likelihood ratio values to provide modified logarithmic likelihood ratio values, and provides the modified logarithmic likelihood ratio values to the second decoder, where the second decoder attempts to decode the representation of the codeword using the modified logarithmic likelihood ratio values as second initial logarithmic likelihood ratios.

27. The memory apparatus of claim 26, wherein:

the second processing unit reduces magnitudes of at least some of the final logarithmic likelihood ratio values by clipping the magnitudes so that the magnitudes do not exceed a certain value, but does not change sign bits of the final logarithmic likelihood ratio values, to provide the modified logarithmic likelihood ratio values.