Guided Simulated Annealing in Non-Volatile Memory Error Correction Control

• US 20080244368A1
• Filed: 03/31/2007
• Published: 10/02/2008
• Est. Priority Date: 03/31/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Chin, Henry, Mokhlesi, Nima
• Granted Patent: US 7,971,127 B2
• Time in Patent Office: Days
• US Class Current: 714/800
• CPC Class Codes: G06F 11/1072 in multilevel memories
• CPC Class Codes: G11C 11/5642 Sensing or reading circuits; Data output circuits
• CPC Class Codes: G11C 29/00 Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation

Abstract

Data stored in non-volatile storage is decoded using iterative probabilistic decoding. An error correcting code such as a low density parity check code may be used. In one approach, initial reliability metrics, such as logarithmic likelihood ratios, are used in decoding sensed states of a set of non-volatile storage elements. The decoding attempts to converge by adjusting the reliability metrics for bits in code words which represent the sensed state. Simulated annealing using an adjustable temperature parameter based on a level of error in the data read from the system can be performed to assist the iterative decoding process. The simulated annealing can introduce randomness, as noise for example, into the metric based decoding process. Moreover, knowledge of the device characteristics can be used to guide the simulated annealing process rather than introducing absolute randomness. The introduction of a degree of randomness adds flexibility during the iterative decoding that permits possible faster convergence times and convergence in situations where data may otherwise be uncorrectable.

Claims

1. A method of reading non-volatile memory, comprising:

reading a set of user data from a set of non-volatile storage elements;

detecting one or more errors associated with the set of user data;

iteratively decoding the user data using reliability metrics for portions of the set of user data, the decoding includes simulating annealing for one or more portions of user data to cause a change in one or more of the corresponding reliability metrics.

2. The method of claim 1, wherein:

simulating annealing includes guiding the simulated annealing based on a predetermined characterization of said set of non-volatile storage elements.

3. The method of claim 1, wherein:

simulating annealing includes introducing a random adjustment to one or more of said reliability metrics.

4. The method of claim 1, wherein:

simulating annealing includes setting a parameter to influence a degree of randomness inserted into the iterative decoding.

5. The method of claim 4, wherein:

setting the parameter includes setting the parameter based on said one or more errors associated with the set of user data.

6. The method of claim 5, wherein:

setting the parameter includes setting the parameter to increase the degree of randomness for larger errors associated with the user data.

7. The method of claim 4, wherein setting the parameter comprises setting the parameter to zero.

8. The method of claim 1, wherein:

iterative decoding includes, for at least one iteration, determining a predicted value for one or more of said portions of user data to use during a subsequent iteration;

simulating annealing includes, providing a range of adjustments to said one or more reliability metrics relative to said predicted value and selecting, at least partially at random, one of the adjustments from the range.

9. The method of claim 8, wherein providing the range of adjustments includes centering the range with respect to said predicted value.

10. The method of claim 9, wherein providing the range of adjustments includes offsetting the range with respect to the predicted value based on characterizing a data retention property of the set of non-volatile storage elements.

11. The method of claim 1, wherein:

the iterative decoding is iterative probabilistic decoding;

the reliability metrics are logarithmic likelihood ratios.

12. The method of claim 11, wherein:

the simulated annealing includes randomly adjusting one or more of the logarithmic likelihood ratios after one or more iterations.

13. The method of claim 1, wherein:

the set of non-volatile storage elements is a set of NAND flash memory cells.

14. The method of claim 1, wherein:

the set of non-volatile storage elements is a set of multi-state flash storage elements.

15. The method of claim 1, wherein:

iteratively decoding the user data includes performing one or more parity checks.

16. The method of claim 1, wherein:

reading includes at least one of voltage sensing and current sensing.

17. A method according to claim 1, wherein:

the user data includes one or more parity bits.

18. A method of reading non-volatile memory, comprising:

detecting state information for a set of non-volatile storage elements;

providing one or more code words based on the state information;

detecting one or more errors associated with the one or more code words;

performing a number of iterations of decoding for said one or more code words, wherein decoding includes assigning reliability metrics to bits of the one or more code words and adjusting the reliability metrics for subsequent decoding iterations in an attempt to decrease said one or more errors; and

after the number of iterations, simulating annealing for the one or more code words, wherein simulating annealing includes providing at least a pseudo-random adjustment to one or more of said reliability metrics.

19. A method of reading non-volatile memory, comprising:

detecting state information for a set of non-volatile storage elements;

providing one or more code words based on the state information;

detecting one or more errors associated with the one or more code words; and

performing a number of iterations of decoding for the one or more code words, wherein decoding includes assigning reliability metrics to bits of the one or more code words and adjusting the reliability metrics for subsequent decoding iterations in an attempt to decrease the one or more errors, wherein at least one the iterations includes guiding an adjustment to at least one reliability metric based on a predetermined characterization of the set of non-volatile storage elements.