DATA STORAGE WITH INCREMENTAL REDUNDANCY

• US 20080282106A1
• Filed: 05/12/2008
• Published: 11/13/2008
• Est. Priority Date: 05/12/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Anobit Technologies, Ltd. (Apple Inc.)
• Inventors: Shalvi, Ofir, Sokolov, Dotan, Gurgi, Eyal, Sommer, Naftali, Golov, Oren
• Granted Patent: US 8,234,545 B2
• Time in Patent Office: Days
• US Class Current: 714/6
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G11C 2029/0411 Online error correction

Abstract

A method for operating a memory includes encoding input data with an Error Correction Code (ECC) to produce input encoded data including first and second sections, such that the ECC is decodable based on the first section at a first redundancy, and based on both the first and the second sections at a second redundancy that is higher than the first redundancy.

Output encoded data is read and a condition is evaluated. The input data is reconstructed using a decoding level selected, responsively to the condition, from a first level, at which a first part of the output encoded data corresponding to the first section is processed to decode the ECC at the first redundancy, and a second level, at which the first part and a second part of the output encoded data corresponding to the second section are processed jointly to decode the ECC at the second redundancy.

Claims

1. A method for operating a memory that includes a plurality of memory cells, comprising:

encoding input data with an Error Correction Code (ECC) so as to produce input encoded data comprising first and second sections, such that the ECC is decodable based on the first section at a first redundancy, and based on both the first and the second sections at a second redundancy that is higher than the first redundancy;

storing the input encoded data in the memory cells;

after storing at least part of the input encoded data, reading from the memory cells output encoded data; and

evaluating a condition related to the output encoded data and reconstructing the input data using a decoding level selected, responsively to the evaluated condition, from a group of decoding levels consisting of;

a first decoding level, at which a first part of the output encoded data corresponding to the first section of the input encoded data is processed so as to decode the ECC at the first redundancy; and

a second decoding level, at which the first part and a second part of the output encoded data corresponding to the second section of the input encoded data are processed jointly so as to decode the ECC at the second redundancy.

2. The method according to claim 1, wherein the condition comprises a failure to reconstruct the input data at the first redundancy.

3. The method according to claim 1, wherein evaluating the condition comprises estimating a distortion level in the memory cells in which the first part is stored, and wherein the condition is defined with respect to the estimated distortion level.

4. The method according to claim 1, wherein the ECC is decodable based on the first section at a first error correction capability, and based on both the first and the second sections at a second error correction capability that is higher than the first error correction capability.

5. The method according to claim 1, wherein storing the input encoded data comprises partitioning the plurality of the memory cells into a data storage area and a redundancy storage area different from the data storage area, storing the first section in the data storage area and storing the second section in the redundancy storage area.

6. The method according to claim 1, wherein reading the output encoded data comprises reading the first part from the memory cells in a single read operation, and reading the second part in another read operation.

7. The method according to claim 1, wherein storing the input encoded data comprises storing the first and second sections in the memory cells before reading the output encoded data.

8. The method according to claim 1, wherein encoding the input data comprises producing the second section responsively to processing the first part of the output encoded data.

9. The method according to claim 1, wherein the first section comprises uncoded data bits, wherein encoding the data comprises selecting a subset of the uncoded data bits from the first section and encoding the selected subset to produce redundancy bits, and wherein the second section comprises the redundancy bits.

10. The method according to claim 9, wherein reconstructing the input data using the second decoding level comprises decoding the redundancy bits in the second part so as to reconstruct the subset of the uncoded data bits, replacing the subset of the uncoded data bits in the first part with the reconstructed subset of the uncoded data bits, and decoding the first part, including the replaced subset, so as to reconstruct the input data.

11. The method according to claim 1, wherein reconstructing the input data using the first decoding level comprises determining a number of errors that were corrected by the ECC at the first redundancy and comparing the number to a threshold, and wherein encoding the input data comprises producing and storing the second section responsively to the number exceeding the threshold.

12. The method according to claim 11, wherein producing and storing the second section comprise storing in the second section locations in the memory of bits in which the errors that were corrected by the ECC are located.

13. The method according to claim 1, wherein encoding the input data comprises encoding redundancy bits produced by the ECC in the first and second sections with an additional ECC.

14. The method according to claim 1, wherein the memory cells comprise analog memory cells.

15. The method according to claim 14, wherein storing the input encoded data comprises writing storage values that represent the data in the first section to a group of the analog memory cells and verifying the written storage values, and wherein encoding the data comprises estimating a storage reliability of the group and producing the second section responsively to the estimated storage reliability.

16. The method according to claim 15, wherein writing and verifying the storage values comprise applying a sequence of programming iterations to the analog memory cells in the group, and determining a number of the programming iterations in the sequence based on the estimated storage reliability.

17. The method according to claim 1, wherein encoding the input data comprises measuring a distortion in the memory cells, and producing the second section only responsively to determining that the first redundancy is insufficient for decoding the ECC in the presence of the distortion.

18. The method according to claim 1, wherein the condition is defined with respect to a location in the memory of the memory cells in which the first part is stored.

19. The method according to claim 1, and comprising accepting a reliability indication regarding the memory cells in which the first part is stored, wherein the condition is defined with respect to the reliability indication.

20. A data storage apparatus, comprising:

an interface, which is operative to communicate with a memory that includes a plurality of memory cells; and

a processor, which is connected to the interface and is coupled to encode input data with an Error Correction Code (ECC) so as to produce input encoded data comprising first and second sections, such that the ECC is decodable based on the first section at a first redundancy and based on both the first and the second sections at a second redundancy that is higher than the first redundancy, to store the input encoded data in the memory cells, to read from the memory cells output encoded data after storing at least part of the input encoded data, to evaluate a condition related to the output encoded data and to reconstruct the input data using a decoding level selected, responsively to the evaluated condition, from a group of decoding levels consisting of;

a first decoding level, at which a first part of the output encoded data corresponding to the first section of the input encoded data is processed so as to decode the ECC at the first redundancy; and

a second decoding level, at which the first part and a second part of the output encoded data corresponding to the second section of the input encoded data are processed jointly so as to decode the ECC at the second redundancy.

21. The apparatus according to claim 20, wherein the condition comprises a failure to reconstruct the input data at the first redundancy.

22. The apparatus according to claim 20, wherein the processor is coupled to estimate a distortion level in the memory cells in which the first part is stored, and wherein the condition is defined with respect to the estimated distortion level.

23. The apparatus according to claim 20, wherein the ECC is decodable based on the first section at a first error correction capability, and based on both the first and the second sections at a second error correction capability that is higher than the first error correction capability.

24. The apparatus according to claim 20, wherein the processor is coupled to partition the plurality of the memory cells into a data storage area and a redundancy storage area different from the data storage area, to store the first section in the data storage area and to store the second section in the redundancy storage area.

25. The apparatus according to claim 20, wherein the processor is coupled to read the first part from the memory cells in a single read operation, and to read the second part in another read operation.

26. The apparatus according to claim 20, wherein the processor is coupled to store the first and second sections in the memory cells before reading the output encoded data.

27. The apparatus according to claim 20, wherein the processor is coupled to produce the second section responsively to reconstructing the input data using the first decoding level.

28. The apparatus according to claim 20, wherein the first section comprises uncoded data bits, wherein the processor is coupled to select a subset of the uncoded data bits from the first section and to encode the selected subset to produce redundancy bits, and wherein the second section comprises the redundancy bits.

29. The apparatus according to claim 28, wherein the processor is coupled to decode the redundancy bits in the second part so as to reconstruct the subset of the uncoded data bits, to replace the subset of the uncoded data bits in the first part with the reconstructed subset of the uncoded data bits, and to decode the first part, including the replaced subset, so as to reconstruct the input data.

30. The apparatus according to claim 20, wherein the processor is coupled to determine a number of errors that were corrected by the ECC at the first redundancy, to compare the number to a threshold and to produce and store the second section responsively to the number exceeding the threshold.

31. The apparatus according to claim 30, wherein the processor is coupled to store in the second section locations in the memory of bits in which the errors that were corrected by the ECC are located.

32. The apparatus according to claim 20, wherein the processor is coupled to encode redundancy bits produced by the ECC in the first and second sections with an additional ECC.

33. The apparatus according to claim 20, wherein the memory cells comprise analog memory cells.

34. The apparatus according to claim 33, wherein the processor is coupled to cause the memory device to write storage values that represent the data in the first section to a group of the analog memory cells and to verify the written storage values, and is further coupled to estimate a storage reliability of the group and to produce the second section responsively to the estimated storage reliability.

35. The apparatus according to claim 34, wherein the processor is coupled to cause the memory device to apply a sequence of programming iterations to the analog memory cells in the group so as to write the storage values, and is further coupled to determine a number of the programming iterations in the sequence based on the estimated storage reliability.

36. The apparatus according to claim 20, wherein the processor is coupled to measure a distortion in the memory cells and to produce the second section only responsively to determining that the first redundancy is insufficient for decoding the ECC in the presence of the distortion.

37. The apparatus according to claim 20, wherein the condition is defined with respect to a location in the memory of the memory cells in which the first part is stored.

38. The apparatus according to claim 20, wherein the processor is coupled to accept a reliability indication regarding the memory cells in which the first part is stored, and wherein the condition is defined with respect to the reliability indication.

39. A data storage apparatus, comprising:

a memory, which comprises a plurality of memory cells; and

a processor, which is coupled to encode input data with an Error Correction Code (ECC) so as to produce input encoded data comprising first and second sections, such that the ECC is decodable based on the first section at a first redundancy and based on both the first and the second sections at a second redundancy that is higher than the first redundancy, to store the input encoded data in the memory cells, to read from the memory cells output encoded data after storing at least part of the input encoded data, to evaluate a condition related to the output encoded data and to reconstruct the input data using a decoding level selected, responsively to the evaluated condition, from a group of decoding levels consisting of;

a first decoding level, at which a first part of the output encoded data corresponding to the first section of the input encoded data is processed so as to decode the ECC at the first redundancy; and

a second decoding level, at which the first part and a second part of the output encoded data corresponding to the second section of the input encoded data are processed jointly so as to decode the ECC at the second redundancy.