Data storage with incremental redundancy

• US 8,234,545 B2
• Filed: 05/12/2008
• Issued: 07/31/2012
• Est. Priority Date: 05/12/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Shalvi, Ofir, Sokolov, Dotan, Gurgi, Eyal, Golov, Oren, Sommer, Naftali
• Primary Examiner(s): Riad, Amine
• Application Number:
  US12/119,069
• Publication Number:
  US 20080282106A1
• Time in Patent Office: 1,541 Days
• Field of Search: 714/748
• US Class Current: 714/768
• 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 with a first error correction capability when decoded only based on the first section, and is decodable with a second error correction capability, higher than the first error correction capability, when decoded based on both the first and the second sections;

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 with the first error correction capability; and

a second decoding level, at which both 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 with the second error correction capability.

2. The method according to claim 1, wherein the condition comprises a failure to reconstruct the input data with the first error correction capability.

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 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. The method according to claim 8, 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.

10. 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 with the first error correction capability 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.

11. The method according to claim 10, 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.

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

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

14. The method according to claim 13, 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.

15. The method according to claim 14, 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.

16. 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 section is insufficient for decoding the ECC in the presence of the distortion.

17. 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.

18. 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.

19. 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 with a first error correction capability when decoded only based on the first section, and is decodable with a second error correction capability, higher than the first error correction capability, when decoded based on both the first and the second sections, 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 with the first error correction capability; and

a second decoding level, at which both 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 with the second error correction capability.

20. The apparatus according to claim 19, wherein the condition comprises a failure to reconstruct the input data with the first error correction capability.

21. The apparatus according to claim 19, 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.

22. The apparatus according to claim 19, 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.

23. The apparatus according to claim 19, 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.

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

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

26. The apparatus according to claim 19, 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.

27. The apparatus according to claim 26, 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.

28. The apparatus according to claim 19, wherein the processor is coupled to determine a number of errors that were corrected by the ECC with the first error correction capability, to compare the number to a threshold and to produce and store the second section responsively to the number exceeding the threshold.

29. The apparatus according to claim 28, 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.

30. The apparatus according to claim 19, wherein the processor is coupled to encode redundancy bits produced by the ECC in at least one of the first and second sections with an additional ECC.

31. The apparatus according to claim 19, wherein the memory cells comprise analog memory cells.

32. The apparatus according to claim 31, 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.

33. The apparatus according to claim 32, 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.

34. The apparatus according to claim 19, 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 section is insufficient for decoding the ECC in the presence of the distortion.

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

36. The apparatus according to claim 19, 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.

37. 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 with a first error correction capability when decoded only based on the first section, and is decodable with a second error correction capability, higher than the first error correction capability, when decoded based on both the first and the second sections, 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 with the first error correction capability; and

a second decoding level, at which both 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 with the second error correction capability.