System and method for correcting errors in data using a compound code

• US 8,832,524 B2
• Filed: 09/21/2012
• Issued: 09/09/2014
• Est. Priority Date: 09/22/2011
• Status: Active Grant

• Current Assignee: Innovations In Memory LLC
• Original Assignee: Violin Memory Incorporated
• Inventors: Bennett, Jon C. R.
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Knapp, Justin R
• Application Number:
  US13/624,282
• Publication Number:
  US 20130080862A1
• Time in Patent Office: 718 Days
• Field of Search: 714/773, 714/782
• US Class Current: 714/755
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1072 in multilevel memories
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2942 wherein a block of parity bits is computed only from combined information bits or only from parity bits, e.g. a second block of parity bits is computed from a first block of parity bits obtained by systematic encoding of a block of information bits, or a block of parity bits is obtained by an XOR combination of sub-blocks of information bits

Abstract

Storage of digital data in non-volatile media such as NAND FLASH needs to take account of the errors in data retrieved from the memory. The error rate tends to increase with the number of write/erase cycles of a cell of memory and with the time that the data has been stored. To achieve a very low uncorrected bit error rate (UBER) a substantial amount of redundancy data needs to be stored for error correction purposes. A method and apparatus is disclosed where a first redundancy data is represented by a second redundancy data computed from the first redundancy data. The first redundancy data may not be stored and is reconstructed from the stored data using a same generation procedure as previously used. The reconstructed estimate of the first redundancy data is corrected by the second redundancy data, and is used to correct the underlying data.

Claims

1. A method of storing data, the method comprising:

dividing a chunk of data into a plurality of segments;

computing redundant data for each of the plurality of segments using a first code type;

computing redundant data for the chunk of data using a second code type;

computing redundant data for the redundant data of the chunk of data using a third code type; and

,

storing the plurality of segments, the redundant data of each of the plurality of segments, and the redundant data for the redundant data of the chunk of data,

wherein the computed redundant data for the chunk of data is not stored.

2. The method of claim 1, wherein the first, the second and the third code types are a same code type.

3. The method of claim 1, wherein at least two of the code types are a same code type.

4. The method of claim 1, wherein at least one of the first, the second or the third code type is a Bose-Chaudhuri-Hocquenghem (BCH) code.

5. The method of claim 1, wherein at least one of the first, the second or the third code type is a low density parity code (LDPC).

6. A method of retrieving data, the method comprising:

receiving a chunk of data, the chunk of data comprising a plurality of segments of data, each segment of data having associated redundant data, and redundant data for redundant data for the chunk of data, but not including the redundant data for the chunk of data;

correcting the segments of data using the associated redundant data for each segment;

determining if all errors in the chunk of data have been corrected; and

;

if all of the errors in the chunk of data have been corrected, output the data of the chunk of data;

else;

computing an estimate of the redundant data for the chunk of received data using a same procedure as was used to previously compute the redundant data for the chunk of data;

correcting the estimate of the redundant data using the redundant data for the redundant data of the chunk of data;

using the same procedure used to compute the redundant data of the chunk of data and the estimate of the redundant data to correct the chunk of data;

correcting the segments of data using the associated redundant data for each segment; and

,

repeating until no errors remain in the segments of data.

7. The method of claim 6, wherein the step of receiving the data includes receiving the chunk of data by reading the data from a memory circuit.

8. The method of claim 6, wherein the step of receiving the data includes accepting data from a receiving circuit.

9. A memory system, comprising:

a memory module having an interface and a memory circuit;

a first data redundancy computation unit, configured to compute redundant data for each one of a plurality of data segments of a chunk of data;

a second data redundancy computation unit, configured to compute redundant data for the chunk of data; and

,

a third data redundancy computation unit configured to compute redundant data for the redundant data of the chunk of data,

wherein the chunk of data, the redundant data for the data segments of the chunk of data and the redundant data for the redundant data of the chunk of data are stored in the memory circuit, and the redundant data for the chunk of data is not stored in the memory circuit.

10. The memory system of claim 9, wherein the chunk of data, the redundant data for the data segments of the chunk of data, and the redundant data for the redundant data of the chunk of data are read from the memory circuit, further comprising:

an error correcting unit configured to correct errors in the data read from the memory circuit using the redundant data for the data segments and the redundant data for the redundant data of the chunk of data.

11. The memory system of claim 10, wherein the redundant data for the data segments is used to correct errors in each segment of the chunk of data.

12. The memory system of claim 11, wherein the second redundancy computation unit is used to compute an estimate of the redundant data of the chunk of data using the data of each segment.

13. The memory system of claim 11, wherein the estimate of the redundant data of the chunk of data is corrected using the redundant data of the redundant data of the chunk of data.

14. The memory system of claim 13, wherein the corrected redundant data of the redundant data of the chunk of data is used to correct the data of the chunk of data.

15. A computer program product stored on a non-volatile computer readable medium, comprising:

instructions to be executed by a processor for;

dividing a chunk of data into a plurality of segments;

computing redundant data for each of the plurality of segments using a first code type;

computing redundant data for the chunk of data using a second code type;

computing redundant data for the redundant data of the chunk of data using a third code type; and

,

storing or transmitting the plurality of segments, the redundant data of each of the plurality of segments, and the redundant data for the redundant data of the chunk of data,

wherein the redundant data for the chunk of data is not stored or transmitted.

16. A computer program product stored on a non-volatile computer readable medium, comprising:

instructions to be executed by a processor for;

receiving a chunk of data, the chunk of data comprising a plurality of segments of data, each segment of data having associated redundant data, and redundant data for redundant data for the chunk of data, but not including the redundant data for the chunk of data;

correcting the segments of data using the associated redundant data for each segment;

determining if all errors in the chunk of data have been corrected; and

;

if all of the errors in the chunk of data have been corrected, output the data of the chunk of data;

else;

computing an estimate of the redundant data for the chunk of received data using a same procedure as was used to previously compute the redundant data for the chunk of data;

correcting the estimate of the redundant data using the redundant data for the redundant data of the chunk of data;

using the same procedure used to compute the redundant data of the chunk of data and the estimate of the redundant data to correct the chunk of data;

correcting the segments of data using the associated redundant data for each segment; and

,

repeating until no errors remain in the segments of data.

17. A method of storing data, the method comprising:

dividing a chunk of data into a plurality of segments;

computing redundant data for each of the plurality of segments using a first code type;

computing redundant data for the chunk of data using a second code type;

computing redundant data for the redundant data of the chunk of data using a third code type; and

,

transmitting the plurality of segments, the redundant data of each of the plurality of segments, and the redundant data for the redundant data of the chunk of data,

wherein the computed redundant data for the chunk of data is not transmitted.

18. The method of claim 17, wherein the first, the second and the third code types are a same code type.

19. The method of claim 17, wherein at least two of the code types are a same code type.

20. The method of claim 17, wherein at least one of the first, the second or the third code type is a Bose-Chaudhuri-Hocquenghem (BCH) code.

21. The method of claim 17, wherein at least one of the first, the second or the third code type is a low density parity code (LDPC).