Generalized concatenated error correction coding scheme with locality

Patent metadata

Field	Value
Publication number	US-11031956-B2
Application number	US-201916452240-A
Country	US
Kind code	B2
Filing date	Jun 25, 2019
Priority date	Jun 25, 2019
Publication date	Jun 8, 2021
Grant date	Jun 8, 2021

Abstract

A method for storing data within a memory device includes receiving data to be stored. The received data is encoded. The encoded data is stored within the memory device. Encoding the received data includes encoding the data into two or more sub-codewords. Each of the two or more sub-codewords includes a plurality of outer codewords. Two or more of the plurality of outer codewords are grouped to form a larger codeword that is larger than each of the plurality of outer codewords and the larger codeword is constructed to correct errors and/or erasures that are not correctable by the plurality of outer codewords, individually.

First claim

What is claimed is:

1. A method for storing data within a memory device, comprising:
receiving data to be stored;
encoding the received data; and
storing the encoded data within the memory device,
wherein encoding the received data comprises encoding the data into two or more sub-codewords that are each independently decodable to reconstruct the received data with a first level of error correction,
wherein each of the two or more sub-codewords comprises a plurality of outer codewords, and
wherein two or more of the plurality of outer codewords are grouped to form a larger codeword that is larger than each of the plurality of outer codewords and the larger codeword is independently decodable to reconstruct the received data with a second level of error correction that is more robust than the first level of error correction.

2. The method of claim 1 , wherein the larger codeword includes more redundancy of the data than do the plurality of outer codewords, individually.

3. The method of claim 1 , wherein the larger codeword that includes the two or more of the plurality of outer codewords is a generalized concatenated code (GCC) codeword.

4. The method of claim 1 , wherein each of the two or more sub-codewords is a generalized concatenated code (GCC) codeword and each of the plurality of outer codewords and the larger codeword is a Reed-Solomon codeword.

5. The method of claim 1 , wherein each of the two or more sub-codewords represents a first layer of encoding, each of the plurality of outer codewords represents a second layer of encoding, and the larger codeword represents a third layer of encoding.

6. The method of claim 1 , wherein the larger codeword is independently decodable using a matrix comprised by a first several rows of a parity-check matrix of the larger codeword that is formed by cascading parity check matrices of each of the plurality of codewords.

7. The method of claim 1 , wherein each of the two or more sub-codewords comprises multiple layers of outer codewords of the plurality of outer codewords and at each of the multiple layers, grouping together corresponding outer codewords of the plurality of outer codewords constitutes a generalized concatenated code (GCC) codeword.

8. A method for retrieving data within a memory device, comprising:
reading stored data from a memory device; and
decoding the read data,
wherein decoding the read data comprises individually decoding sub-codewords of the read data to reconstruct original data, and
wherein when a sub-codeword of the read data cannot be decoded, decoding the read data comprises decoding a plurality of outer codewords, each of which includes two car more sub-codewords including the sub-codeword that could not be individually encoded to reconstruct the original data, without individually decoding the sub-codewords of the read data.

9. The method of claim 8 , wherein the plurality of outer codewords constitutes a larger codeword that is larger than each of the plurality of outer codewords.

10. The method of claim 9 , wherein the larger codeword includes more redundancy of the stored data than do the plurality of outer codewords, individually.

11. The method of claim 9 , wherein the larger codeword that includes the plurality of outer codewords is a generalized concatenated code (GCC) codeword.

12. The method of claim 9 , wherein each of the two or more sub-codewords is a generalized concatenated code (GCC) codeword and each of the plurality of outer codewords and the larger codeword is a Reed-Solomon on codeword.

13. The method of claim 9 , wherein each of the two or more sub-codewords represents a first layer of encoding, each of the plurality of outer codewords represents a second layer of encoding, and the larger codeword represents a third layer of encoding.

14. The method of claim 9 , wherein when the sub-codeword of the read data cannot be decoded, decoding the read data includes using a matrix comprised by a first several rows of a parity-check matrix of the larger codeword that is formed by cascading parity check matrices of each of the plurality of codewords.

15. The method of claim 9 , wherein each of the two or more sub-codewords comprises multiple layers of outer codewords of the plurality of outer codewords and at each of the multiple layers, grouping together corresponding outer codewords of the plurality of outer codewords constitutes a generalized concatenated code (GCC) codeword.

16. A method for storing data within a memory device, comprising:
receiving data to be stored;
encoding the received data; and
storing the encoded data within the memory device,
wherein encoding the received data comprises:
encoding the data into a plurality of sub-codewords that are each independently decodable to reconstruct the received data with a first level of error correction within a first layer of encoding;
grouping the plurality of sub-codewords into a plurality of outer codewords independently decodable to reconstruct the received data with a second level of error correction that is more robust than the first level of error correction within a second layer of encoding; and
grouping the plurality of outer codewords into at least one larger codeword that is larger than each of the plurality of outer codewords, the larger codeword being independently decodable to reconstruct the received data with a third level of error correction that is more robust than the second level of error correction.

17. The method of claim 16 , wherein the at least one larger codeword includes more redundancy of the data than do the plurality of outer codewords, individually.

18. The method of claim 16 , wherein the larger codeword is independently decodable using a matrix comprised by a first several rows of a parity-check matrix of the larger codeword that is formed by cascading parity check matrices of each of the plurality of codewords.

19. The method of claim 16 , wherein each of the sub-codewords comprises multiple layers of the outer codewords and at each of the multiple layers, corresponding outer codewords are grouped together as a generalized concatenated code (GCC) codeword.

20. The method of claim 16 , further comprising:
reading the stored data from the memory device; and
decoding the read data,
wherein decoding the read data comprises individually decoding the sub-codewords of the read data,
wherein when one of the sub-codewords of the read data cannot be decoded, decoding the read data comprises decoding the plurality of outer codewords including the sub-codeword that could not be individually encoded.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Berman Amit
• Doubchak Ariel
• Dor Avner

Classifications

• H03M13/2906 Primary

  using block codes (H03M13/2957 takes precedence) · CPC title

• H03M13/1515

  Reed-Solomon codes · CPC title

• G06F11/1458

  Management of the backup or restore process · CPC title

• G06F11/1048

  using arrangements adapted for a specific error detection or correction feature · CPC title

• G06F3/0614

  Improving the reliability of storage systems · CPC title