Nested coding techniques for data storage
AssigneeGoogle Inc.
InventorRobert Cypher
Life of this patent
Estimating the term…
Abstract
Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for skewed orthogonal coding techniques. In one aspect, a method includes receiving a block of data comprising a plurality of data chunks. One or more rows of word code chunks are generated using a first linear error-correcting code in systematic form and the data chunks. For each of m rows of the data chunks, one or more split row code chunks are generated using the data chunks of the row, wherein the split row code chunks are generated so that a linear combination of m split row code chunks from different rows forms a first word code chunk of a first codeword including the data chunks and the word code chunks. The rows of data chunks and the split row code chunks and the word code chunks are stored.
Claims42
A method performed by one or more computers, the method comprising:
- receiving a block of data comprising a plurality of data chunks, the plurality of data chunks comprising m rows of data chunks, m being an integer greater than one;
- generating one or more rows of word code chunks using a first linear error-correcting code in systematic form and the data chunks, wherein each of the word code chunks is generated based on the plurality of data chunks;
- for each of the m rows of data chunks, generating one or more split row code chunks using the data chunks of the row, wherein each of the split row code chunks is generated based on the data chunks of the row, and wherein the split row code chunks are generated so that a linear combination of m split row code chunks from different rows forms a first word code chunk of a first codeword including the data chunks and the word code chunks;
- and
- storing the rows of data chunks and the split row code chunks and the word code chunks.
A system comprising one or more computers configured to perform operations comprising:
- receiving a block of data comprising a plurality of data chunks, the plurality of data chunks comprising m rows of data chunks, m being an integer greater than one;
- generating one or more rows of word code chunks using a first linear error-correcting code in systematic form and the data chunks, wherein each of the word code chunks is generated based on the plurality of data chunks;
- for each of the m rows of data chunks, generating one or more split row code chunks using the data chunks of the row, wherein each of the split row code chunks is generated based on the data chunks of the row, and wherein the split row code chunks are generated so that a linear combination of m split row code chunks from different rows forms a first word code chunk of a first codeword including the data chunks and the word code chunks;
- and
- storing the rows of data chunks and the split row code chunks and the word code chunks.
A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the computers to perform operations comprising:
- receiving a block of data comprising a plurality of data chunks, the plurality of data chunks comprising m rows of data chunks, m being an integer greater than one;
- generating one or more rows of word code chunks using a first linear error-correcting code in systematic form and the data chunks, wherein each of the word code chunks is generated based on the plurality of data chunks;
- for each of the m rows of data chunks, generating one or more split row code chunks using the data chunks of the row, wherein each of the split row code chunks is generated based on the data chunks of the row, and wherein the split row code chunks are generated so that a linear combination of m split row code chunks from different rows forms a first word code chunk of a first codeword including the data chunks and the word code chunks;
- and
- storing the rows of data chunks and the split row code chunks and the word code chunks.
Dependencies are inferred from the claim text.