Error correction coding over multiple memory pages

• US 8,495,465 B1
• Filed: 09/27/2010
• Issued: 07/23/2013
• Est. Priority Date: 10/15/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Anholt, Micha, Ordentlich, Or, Sommer, Naftali, Shalvi, Ofir
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US12/890,724
• Time in Patent Office: 1,030 Days
• Field of Search: 714/763, 714/773
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G11C 2029/1804 Manipulation of word size
• CPC Class Codes: G11C 29/00 Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes

Abstract

A method for data storage includes encoding each of multiple data items individually using a first Error Correction Code (ECC) to produce respective encoded data items. The encoded data items are stored in a memory. The multiple data items are encoded jointly using a second ECC, so as to produce a code word of the second ECC, and only a part of the code word is stored in the memory. The stored encoded data items are recalled from the memory and the first ECC is decoded in order to reconstruct the data items. Upon a failure to reconstruct a given data item from a respective given encoded data item by decoding the first ECC, the given data item is reconstructed based on the part of the code word of the second ECC and on the encoded data items other than the given encoded data item.

Claims

1. A method for data storage, comprising:

encoding each of a plurality of data items individually using a first Error Correction Code (ECC) to produce respective a plurality of encoded data items, and storing the plurality of encoded data items in a memory;

encoding the plurality of data items jointly using a second ECC, so as to produce a code word of the second ECC, and storing only a part of the code word in the memory;

recalling the stored plurality of encoded data items from the memory and decoding the first ECC in order to reconstruct the plurality of data items; and

upon a failure to reconstruct a given data item of the plurality of data items from a respective encoded data item of the plurality of encoded data items by decoding the first ECC, reconstructing the given data item of the plurality of data items based on the part of the code word of the second ECC and on a subset of the plurality of encoded data items, wherein the subset of the plurality of encoded data items does not include the respective encoded data item.

2. The method according to claim 1, wherein the code word of the second ECC comprises data bits and redundancy bits, and wherein the part of the code word comprises only the redundancy bits of the code word.

3. The method according to claim 2, wherein encoding the plurality of data items using the second ECC comprises calculating a bitwise Exclusive OR (XOR) over the plurality of data items, and applying the second ECC to the bitwise XOR.

4. The method according to claim 3, wherein reconstructing the given data item of the plurality of data items comprises calculating an interim bitwise XOR over the given data item and over the subset of the plurality of encoded data items, decoding the second ECC for an interim code word comprising the interim bitwise XOR and the stored redundancy bits, and deriving the given data item from the decoded interim code word and the subset of the plurality of encoded data items.

5. The method according to claim 1, wherein the first ECC has a first error correction capability, and wherein the second ECC has a second error correction capability that is greater than the first error correction capability.

6. The method according to claim 1, and comprising, upon failing to reconstruct two or more data items of the plurality of data items from respective encoded data items of the plurality of encoded data items by decoding the first ECC, re-attempting to reconstruct the two or more data items by decoding the first ECC using an erasure decoding process.

7. The method according to claim 1, wherein reconstructing the given data item of the plurality of data items comprises reconstructing the code word of the second ECC and decoding the reconstructed code word.

8. The method according to claim 7, wherein the second ECC is represented by a set of parity check equations, and wherein decoding the code word comprises simplifying one or more of the parity check equations in the set based on a subset of the plurality of reconstructed data items, wherein the subset of the plurality of reconstructed data items does not include the given data item, and decoding the code word using the simplified parity check equations.

9. The method according to claim 8, wherein the first ECC is represented by an additional set of parity check equations, and wherein decoding the code word comprises, after simplifying the parity check equations in the set, jointly decoding the parity check equations of the first ECC and of the second ECC.

10. The method according to claim 1, wherein the second ECC comprises a Low Density Parity Check (LDPC) code.

11. A data storage apparatus, comprising:

an interface, which is configured to communicate with a memory; and

a processing unit, which is configured to encode each of a plurality of data items individually using a first Error Correction Code (ECC) so as to produce respective plurality of encoded data items, to store the plurality of encoded data items in the memory, to encode the plurality of data items jointly using a second ECC so as to produce a code word of the second ECC, to store only a part of the code word in the memory, to recall the stored plurality of encoded data items from the memory and decode the first ECC in order to reconstruct the plurality of data items, and, upon a failure to reconstruct a given data item from a respective data item of the plurality of encoded data item by decoding the first ECC, to reconstruct the given data item based on the part of the code word of the second ECC and on a subset of the plurality of encoded data items, wherein the subset of the plurality of encoded data items does not include the given encoded data item.

12. The apparatus according to claim 11, wherein the code word of the second ECC comprises data bits and redundancy bits, and wherein the part of the code word comprises only the redundancy bits of the code word.

13. The apparatus according to claim 12, wherein the processing unit is further configured to encode the plurality of data items using the second ECC by calculating a bitwise Exclusive OR (XOR) over the plurality of data items, and applying the second ECC to the bitwise XOR.

14. The apparatus according to claim 13, wherein the processing unit is further configured to reconstruct the given data item by calculating an interim bitwise XOR over the given data item and over a subset of the decoded and reconstructed plurality of data items, wherein the subset of the decoded and reconstructed plurality of data items does not include the given data item, decoding the second ECC for an interim code word comprising the interim bitwise XOR and the stored redundancy bits, and deriving the given data item from the decoded interim code word and the subset of the decoded and reconstructed plurality of data items.

15. The apparatus according to claim 11, wherein the first ECC has a first error correction capability, and wherein the second ECC has a second error correction capability that is greater than the first error correction capability.

16. The apparatus according to claim 11, wherein, upon failing to reconstruct two or more data items from respective encoded data items of the plurality of encoded data items by decoding the first ECC, the processing unit is further configured to re-attempt to reconstruct the two or more data items by decoding the first ECC using an erasure deco ding process.

17. The apparatus according to claim 11, wherein the processing unit is further configured to reconstruct the given data item by reconstructing the code word of the second ECC and decoding the reconstructed code word.

18. The apparatus according to claim 17, wherein the second ECC is represented by a set of parity check equations, and wherein the processing unit is further configured to simplify one or more of the parity check equations in the set based on a subset of the plurality of reconstructed data items, wherein the subset of the plurality of reconstructed data items does not include the given data item, and to decode the code word using the simplified parity check equations.

19. The apparatus according to claim 18, wherein the first ECC is represented by an additional set of parity check equations, and wherein the processing unit is further configured to jointly decoding the parity check equations of the first ECC and of the second ECC after simplifying the parity check equations in the set.

20. The apparatus according to claim 11, wherein the second ECC comprises a Low Density Parity Check (LDPC) code.