Method and apparatus for improved data recovery in data storage systems

1. A method for data storage and retrieval, comprising:

generating a plurality of data blocks from a quantity of unencoded data;

receiving, by a plurality of encoders, a respective one of the plurality of data blocks;

encoding the plurality of data blocks by the plurality of encoders, respectively, to generate a plurality of codewords;

logically combining the plurality of codewords to generate an encoded parity block;

storing the plurality of codewords and the encoded parity block in a plurality of data storage media, respectively;

retrieving the plurality of codewords and the encoded parity block from the data storage media;

decoding each of the plurality of codewords;

when at least two of the codewords cannot be decoded correctly:

generating a long vector from the plurality of codewords and the encoded parity block; and

decoding the long vector using a long parity check matrix to re-create the data blocks.

2. The method of claim 1 , wherein generating the long vector comprises:

concatenating the plurality of codewords and the encoded parity block.

3. The method of claim 1 , wherein generating the long vector comprises:

applying a long generator matrix G L to the plurality of data blocks.

4. The method of claim 3 , wherein the long generator matrix comprises a matrix having a number of rows equal to a number of the plurality of data storage media multiplied by a length of each of the plurality of data blocks, and a number of columns equal to the number of the plurality of data storage media plus one, multiplied by a length of each of the plurality of codewords.

5. The method of claim 3 , wherein the long generator matrix comprises a tensor product of a) a matrix comprising an identity matrix and a column vector of all 1's, and b) a generator matrix G used to encode the data blocks by the encoders.

6. The method of claim 3 , wherein encoding the plurality of data blocks by the plurality of encoders comprises:

encoding each of the plurality of data blocks by a respective encoder, each encoder applying a generator matrix G to a respective data block;

wherein the long generator matrix G L comprises a tensor product of a) a matrix comprising an identity matrix augmented with a column vector comprising all 1's, and b) the generator matrix G.

7. The method of claim 1 , wherein decoding each of the codewords comprises:

decoding each of the plurality of codewords by a plurality of decoders, respectively.

8. The method of claim 1 , wherein decoding each of the plurality of codewords by a plurality of decoders, respectively, comprises:

applying a same parity check matrix by the plurality of encoders to the plurality of codewords, respectively.

9. The method of claim 1 , wherein the long parity check matrix comprises:

a matrix comprising a tensor product of a) an identity matrix augmented with a column vector comprising all 0's, and b)a parity check matrix H used to decode the codewords; and

a second tensor product of a) a transpose of a column vector comprising all 1's, and b) a second identity matrix.

10. The method of claim 1 , wherein the long vector comprises a long systematic vector comprising information bits, from the plurality of data blocks, and parity bits, the method further comprising:

forming the long systematic vector by re-arranging the information bits to occupy two or more least or most significant bits of the long systematic vector;

wherein the long parity check matrix comprises a systematic matrix.

11. The method of claim 10 , wherein the systematic matrix comprises I n(m+1)−km |Q′, where n is a number of bits in the long vector, m is a number of the plurality of codewords, k is a number of bits of each of the plurality of data blocks and Q′ comprises a transpose of a tensor product of a) a matrix comprising I m augmented with a column vector of all 1's of length m, and b) a matrix comprising P k(n−k) augmented with a tensor product of the column vector of all 1's of length m and an identity matrix having k×m rows and columns.

12. A data retrieval system, comprising:

a plurality of decoders;

a memory for storing processor-executable instructions and a long parity check matrix; and

a processor coupled to the plurality of decoders and the memory for executing the processor-executable instructions that causes the data retrieval system to:

retrieve, by the plurality of decoders, a plurality of codewords from a plurality of data storage media, respectively;

decode each of the plurality of codewords by the plurality of decoders;

when at least two of the codewords cannot be decoded correctly:

retrieve an encoded parity block from a first data storage media;

generate, by the processor, a long vector from the plurality of codewords and the encoded parity block; and

decode the long vector using the long parity check matrix to re-create a plurality of data blocks that were stored by the data retrieval system.

13. The data retrieval system of claim 12 , wherein the processor-executable instructions for decoding each of the plurality of codewords comprises instructions that cause the data retrieval system to:

apply a same parity check matrix by the plurality of encoders to the plurality of codewords, respectively.

14. The data retrieval system of claim 12 , wherein the processor-executable instructions for generating the long vector comprises instructions that causes the data retrieval system to:

concatenate the plurality of codewords and the encoded parity block.

15. The data retrieval system of claim 12 , wherein the long parity check matrix comprises:

a matrix comprising a tensor product of a) an identity matrix augmented with a column vector comprising all 0's, and b)a parity check matrix H used to decode the codewords; and

a second tensor product of a) a transpose of a column vector comprising all 1's, and b) a second identity matrix.

16. The data retrieval system of claim 12 , wherein the long vector comprises a long systematic vector comprising information bits, from the plurality of data blocks, and parity bits, wherein the processor-executable instructions further comprise instructions that cause the data retrieval system to:

form, by the processor, the long systematic vector by re-arranging the information bits to occupy two or more least or most significant bits of the long systematic vector;

wherein the long parity check matrix comprises a long systematic matrix.

17. The data retrieval system of claim 16 , wherein the long systematic matrix comprises I n(m+1)−km |Q′, where n is a number of bits in the long vector, m is a number of the plurality of codewords, k is a number of bits of each of the plurality of data blocks and Q′ comprises a transpose of a tensor product of a) a matrix comprising I m augmented with a column vector of all 1's of length m, and b) a matrix comprising P k(n−k) augmented with a tensor product of the column vector of all 1's of length m and an identity matrix having k×m rows and columns.