Systems and methods for storing variable rate product codes

• US 8,627,183 B1
• Filed: 05/04/2011
• Issued: 01/07/2014
• Est. Priority Date: 05/11/2010
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Chen, Zhengang, Yang, Xueshi
• Primary Examiner(s): Britt, Cynthia
• Application Number:
  US13/100,644
• Time in Patent Office: 979 Days
• Field of Search: 714/774, 714/758, 714/766
• US Class Current: 714/774
• 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/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/2909 Product codes

Abstract

Systems and methods for storing variable rate product codes are provided. A plurality of row code parity symbols is stored on a storage unit. Each symbol of the row code parity symbols is associated with a different one of a plurality of equal sized portions of information. A plurality of column code parity symbols is computed. Each of the plurality of column code parity symbols is computed based on (1) a respective one of the plurality of row code parity symbols and (2) the portion of information associated with the respective one of the plurality of row code parity symbols. Each of the plurality of column code parity symbols corresponds to one of at least two code rates. The plurality of column code parity symbols is stored on the storage unit.

Claims

1. A method for storing variable rate product codes, the method comprising:

storing, on a flash memory comprising a plurality of NAND storage devices, a plurality of row code parity symbols, each symbol being associated with a different one of a plurality of portions of information;

computing a plurality of column codes that includes a first column code and a second column code, wherein the first column code is computed based on

(1) a first of the plurality of row code parity symbols and

(2) the portion of information associated with the first of the plurality of row code parity symbols,

wherein the second column code is computed independently of the first of the plurality of row code parity symbols based on

(1) a second of the plurality of row code parity symbols and

(2) the portion of information associated with the second of the plurality of row code parity symbols, and wherein each of the plurality of column codes corresponds to one of at least two different code rates, and

wherein at least one of the code rates is selected based on a storage location of the respective one of the plurality of row code parity symbols in the flash memory; and

storing the plurality of column codes on the flash memory.

2. The method of claim 1, wherein the flash memory comprises a plurality of equal sized storage devices, wherein a total size of the plurality of portions of information is predetermined and corresponds to a maximum storage capacity of one of the plurality of storage devices.

3. The method of claim 1, wherein each portion of the plurality of portions of information is of equal size and corresponds to a page of data.

4. The method of claim 1, wherein the flash memory comprises a plurality of equal sized storage devices, wherein the plurality of row code parity symbols are a first plurality of row code parity symbols that are stored in a first of the plurality of storage devices, and wherein the plurality of column codes are stored in a second of the plurality of storage devices, further comprising:

storing, in a third of the plurality of storage devices, a second plurality of row code parity symbols each associated with a different one of another plurality of portions of information, wherein each of the another plurality of portions of information is of a size equal to each of the plurality of portions of information.

5. The method of claim 4, wherein:

the first column code of the plurality of column codes is computed based on a first row code parity symbol from the first plurality of row code parity symbols, the portion of information associated with the first row code parity symbol, a second row code parity symbol from the second plurality of row code parity symbols, and the portion of information associated with the second row code parity symbol;

the second column code of the plurality of column codes is computed based on a third row code parity symbol from the first plurality of row code parity symbols, the portion of information associated with the third row code parity symbol, a fourth row code parity symbol from the second plurality of row code parity symbols, and the portion of information associated with the fourth row code parity symbol; and

the first column code corresponds to a first of the at least two code rates and the second column code corresponds to a second of the at least two code rates different from the first code rate.

6. The method of claim 4, wherein some but not all of the plurality of column codes include at least two portions, and wherein a first of the at least two portions is stored in the second storage device and a second of the at least two portions is stored in a fourth of the plurality of storage devices.

7. The method of claim 1, wherein each column code that corresponds to a first of the at least two code rates is of a first size corresponding to the size of one of the plurality of portions of information, and wherein each column code that corresponds to a second of the at least two code rates is of a second size corresponding to the size of two of the plurality of portions of information.

8. The method of claim 1, wherein:

the flash memory comprises a storage device with multiple planes;

the first symbol of the plurality of row code parity symbols includes a first set of row code parity bits, each subset of the first set of row code parity bits being associated with a different equal sized segment of the portion of information that corresponds to the first symbol;

the second symbol of the plurality of row code parity symbols includes a second set of row code parity bits, each subset of the second set of row code parity bits being associated with a different equal sized segment of the portion of information that corresponds to the second symbol;

the first and second row code parity symbols are stored in each of the multiple planes; and

the first of the plurality of column codes is stored only in one of the multiple planes and the second of the plurality of column codes is stored in each of the multiple planes.

9. A system for storing variable rate product codes, the system comprising:

a flash memory comprising a plurality of NAND storage devices; and

control circuitry configured to;

store, on the flash memory, a plurality of row code parity symbols, each symbol being associated with a different one of a plurality of portions of information;

compute a plurality of column codes that includes a first column code and a second column code, wherein the first column code is computed based on

(1) a first of the plurality of row code parity symbols and

(2) the portion of information associated with the first of the plurality of row code parity symbols,

wherein the second column code is computed independently of the first of the plurality of row code parity symbols based on

(1) a second of the plurality of row code parity symbols and

(2) the portion of information associated with the second of the plurality of row code parity symbols,

wherein each of the plurality of column codes corresponds to one of at least two code rates, and wherein at least one of the code rates is selected based on a storage location of the respective one of the plurality of row code parity symbols in the flash memory; and

store the plurality of column codes on the flash memory.

10. The system of claim 9, wherein the flash memory comprises a plurality of equal sized storage devices, wherein a total size of the plurality of portions of information is predetermined and corresponds to a maximum storage capacity of one of the plurality of storage devices.

11. The system of claim 9, wherein each portion of the plurality of is of equal size portions of information and corresponds to a page of data.

12. The system of claim 9, wherein the flash memory comprises a plurality of equal sized storage devices, wherein the plurality of row code parity symbols are a first plurality of row code parity symbols that are stored in a first of the plurality of storage devices, wherein the plurality of column codes are stored in a second of the plurality of storage devices, and wherein the control circuitry is further configured to:

store, in a third of the plurality of storage devices, a second plurality of row code parity symbols each associated with a different one of another plurality of portions of information, wherein each of the another plurality of portions of information is of a size equal to each of the plurality of portions of information.

13. The system of claim 12, wherein:

the first column code of the plurality of column codes is computed based on a first row code parity symbol from the first plurality of row code parity symbols, the portion of information associated with the first row code parity symbol, a second row code parity symbol from the second plurality of row code parity symbols, and the portion of information associated with the second row code parity symbol;

the second column code of the plurality of column codes is computed based on a third row code parity symbol from the first plurality of row code parity symbols, the portion of information associated with the third row code parity symbol, a fourth row code parity symbol from the second plurality of row code parity symbols, and the portion of information associated with the fourth row code parity symbol; and

the first column code corresponds to a first of the at least two code rates and the second column code corresponds to a second of the at least two code rates different from the first code rate.

14. The system of claim 12, wherein some but not all of the plurality of column codes include at least two portions, and wherein a first of the at least two portions is stored in the second storage device and a second of the at least two portions is stored in a fourth of the plurality of storage devices.

15. The system of claim 9, wherein each column code that corresponds to a first of the at least two code rates is of a first size corresponding to the size of one of the plurality of portions of information, and wherein each column code that corresponds to a second of the at least two code rates is of a second size corresponding to the size of two of the plurality of portions of information.

16. The system of claim 9, wherein:

the flash memory comprises a storage device with multiple planes;

the first symbol of the plurality of row code parity symbols includes a first set of row code parity bits, each subset of the first set of row code parity bits being associated with a different equal sized segment of the portion of information that corresponds to the first symbol;

the second symbol of the plurality of row code parity symbols includes a second set of row code parity bits, each subset of the second set of row code parity bits being associated with a different equal sized segment of the portion of information that corresponds to the second symbol;

the first and second row code parity symbols are stored in each of the multiple planes; and

the first of the plurality of column codes is stored only in one of the multiple planes and the second of the plurality of column codes is stored in each of the multiple planes.

17. The system of claim 9 further comprising selection circuitry configured to select one of the at least two code rates, wherein the control circuitry is coupled to the selection circuitry and is further configured to compute each of the column codes based on the code rate selected by the selection circuitry.