REDUNDANCY OF ERROR CORRECTION ENCODED DATA IN A STORAGE SYSTEM

• US 20170262332A1
• Filed: 03/11/2016
• Published: 09/14/2017
• Est. Priority Date: 03/11/2016
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: HGST Netherlands B.V. (Western Digital Corporation)
• Inventors: BARNDT, Richard David, ANARAKI, Majid Nemati
• Granted Patent: US 10,198,313 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence

Abstract

A device that provides for redundancy of error correction encoded data includes at least one processor circuit. The at least one processor circuit is configured to perform error correction encoding on data items to generate corresponding codewords, where at least one of the data items may have a different length than at least one other of the data items and each of the codewords is the same length. The at least one processor circuit is further configured to generate a redundancy data item based at least in part on the codewords. The at least one processor circuit is further configured to write the codewords and the redundancy data item to separate blocks of at least one flash memory circuit.

Claims

1. A device comprising:

at least one processor circuit configured to;

perform error correction encoding on a plurality of data items to generate a plurality of codewords, wherein at least one of the plurality of data items comprises a different length than at least one other of the plurality of data items and each of the plurality of codewords comprises a same codeword length;

generate a redundancy data item based at least in part on the plurality of codewords; and

write the plurality of codewords and the redundancy data item to a plurality of separate blocks of at least one flash memory circuit.

2. The device of claim 1, wherein the plurality of data items are encoded at a plurality of code rates and at least one of the plurality of data items is encoded at a different code rate than at least one other of the plurality of data items.

3. The device of claim 2, wherein the at least one processor circuit is further configured to:

determine the plurality of code rates for encoding the plurality of data items based at least in part on integrities of the plurality of separate blocks.

4. The device of claim 2, wherein the at least one processor circuit is further configured to:

receive a data stream from a host device; and

parse the data stream into the plurality of data items based at least in part on the plurality of code rates.

5. The device of claim 1, wherein at least one of the plurality of codewords is recoverable using the redundancy data item in conjunction with other codewords of the plurality of codewords.

6. The device of claim 1, wherein the at least one processor circuit is further configured to generate the redundancy data item based at least in part on performing a bitwise exclusive-or operation on the plurality of codewords.

7. The device of claim 1, wherein an integrity of one of the plurality of separate blocks to which the redundancy data item is written is greater than a highest integrity any others of the plurality of separate blocks.

8. A computer program product comprising instructions stored in a tangible computer-readable storage medium, the instructions comprising:

instructions to retrieve, from each of a plurality of blocks, an associated codeword of a plurality of codewords, wherein at least one of the plurality of codewords is encoded at a different code rate than at least one other of the plurality of codewords and each of the plurality of codewords comprises a same codeword length;

instructions to perform error correction decoding on each of the plurality of codewords to generate a plurality of corrected codewords;

instructions to identify at least one of the plurality of codewords that cannot be properly decoded;

instructions to retrieve, from another block, a redundancy data item; and

instructions to recover the at least one of the plurality of codewords that cannot be properly decoded based at least in part on the plurality of corrected codewords and the redundancy data item.

9. The computer program product of claim 8, wherein the instructions further comprise:

instructions to retrieve a plurality of data items from both the recovered at least one of the plurality of codewords and the plurality of corrected codewords; and

instructions to provide the plurality of data items to a host device.

10. The computer program product of claim 9, wherein at least one of the plurality of data items comprises a different length than at least one other of the plurality of data items.

11. The computer program product of claim 8, wherein the redundancy data item is not a valid codeword.

12. The computer program product of claim 8, wherein the error correction decoding comprises low-density parity check error correction decoding.

13. A method comprising:

determining, for each block of a plurality of blocks, an associated code rate of a plurality of code rates;

identifying, for each block of the plurality of blocks, a data item of a plurality of data items, the data item having a length that is determined based at least in part on the associated code rate of the plurality of code rates;

performing, on each data item of the plurality of data items, error correction encoding to generate, for each block of the plurality of blocks, an associated codeword of a plurality of codewords;

generating a redundancy data item based at least in part on each of the plurality of codewords;

writing, to each block of the plurality of blocks, the associated codeword; and

writing, to at least one additional block, the redundancy data item without performing error correction encoding on the redundancy data item.

14. The method of claim 13, wherein a first code rate of the plurality of code rates associated with a first block of the plurality of blocks is different than a second code rate of the plurality of code rates associated with a second block of the plurality of blocks.

15. The method of claim 14, wherein each of the plurality of codewords has a same codeword length.

16. The method of claim 13, wherein determining, for each block of the plurality of blocks, the associated code rate of the plurality of code rates further comprises:

determining, for each block of the plurality of blocks, the associated code rate of the plurality of code rates based at least in part on an integrity of each block of the plurality of blocks.

17. The method of claim 13, wherein at least one of the plurality of codewords is recoverable from other codewords of the plurality of codewords and the redundancy data item.

18. The method of claim 13, wherein generating the redundancy data item based at least in part on each of the plurality of codewords further comprises generating the redundancy data item based at least in part on performing a bitwise exclusive-or operation on each of the plurality of codewords.

19. The method of claim 13, wherein an integrity of the at least one additional block is greater than a highest integrity of the plurality of blocks.

20. The method of claim 13, further comprising:

receiving a data stream from a host device; and

parsing the data stream into the plurality of data items.