Extended row diagonal parity with optimal decoding procedure

1. A method of recovering a plurality of data columns in a data matrix comprising n rows numbered 0 through n−1, and a pair of parity columns, comprising:

selecting a column i and a column j to recover;

calculating, as an accelerator, an implied but missing chain parity from the available data columns and parity columns;

setting a starting point k=n−1 for a chain i and a starting point k for a chain j; and

repeating (n−1)/2 times:

setting k=k−(j−i) as the starting point in the column i;

setting k=k−(n−(j−i)) as the starting point in the column j;

calculating a recovered value for the point (k, j) on the basis of at least a chain with a slope of 1 and the accelerator;

calculating a recovered value for the point (n−1−(j−i), i) on the basis of a chain with a slope of 0 and the accelerator; and

storing the recovered value in the data matrix.

2. The method of claim 1 , wherein the accelerator is calculated according to the equation

c

n

-

1

,

1

=

⊕

i

=

0

n

-

2

⁢

c

i

,

1

,

where c represents an accelerator value corresponding to a cell.

3. The method of claim 1 , wherein the parity value is calculated using the XOR function.

4. The method of claim 1 , wherein the column i and the column j are failed prior to recovery.

5. A non-transitory computer readable medium comprising machine instructions for controlling a programmable processor to recover two data columns in a data matrix comprising at least four data columns and at least two parity columns, comprising instructions for:

calculating as an accelerator row a missing chain parity based on available data columns and the at least two parity columns;

defining a recoverable data cell in each of the two columns to be recovered;

iteratively calculating a value for each recoverable data cell based on the available columns, parity information, previously recovered data cells, and the accelerator row and storing the calculated value in the data matrix; and

providing the recovered data matrix.

6. The medium of claim 5 , wherein the instructions for calculating the accelerator row comprise applying the equation

c

n

-

1

,

1

=

⊕

i

=

0

n

-

2

⁢

c

i

,

1

,

where c represents an accelerator value corresponding to a cell, n represents the number of rows in the matrix, and i represents a row counter.

7. The medium of claim 5 , wherein the parity columns are derived using the XOR function.

8. The medium according to claim 5 , wherein said iteratively calculating comprises:

repeating, until sufficient data is recovered:

setting a data cell in each lost column in a different row which is recoverable based on the available data column, parity columns, and the accelerator;

calculating a recovered value for a first recoverable data cell on the basis of at least a chain with a slope of 1 and the accelerator;

calculating a recovered value for a second recoverable data cell on the basis of a chain with a slope of 0 and the accelerator; and

saving the recovered values in the data matrix.

9. The medium of claim 8 , wherein the accelerator is calculated according to the equation

c

n

-

1

,

1

=

⊕

i

=

0

n

-

2

⁢

c

i

,

1

,

where c represents an accelerator value corresponding to a cell, n is the number of rows numbered 0 through n−1, and i identifier of a column to recover.

10. The medium of claim 8 , wherein the parity value is calculated using the XOR function.

11. The medium of claim 8 , wherein the column i and the column j are failed prior to recovery.

12. A method of recovering at least two data columns in a data matrix comprising at least four data columns and at least two parity columns, comprising:

calculating as an accelerator row, a missing chain parity, based on available data columns and the at least two parity columns;

defining a recoverable data cell in each of the at least two columns to be recovered;

iteratively calculating a value for each recoverable data cell based on the available columns, parity information, previously recovered data cells, and the accelerator row and storing the calculated value in the data matrix; and

providing the recovered data matrix.

13. The method of claim 12 , wherein the accelerator row is calculated according to the equation

c

n

-

1

,

1

=

⊕

i

=

0

n

-

2

⁢

c

i

,

1

,

where c represents an accelerator value corresponding to a cell, n represents the number of rows in the matrix, and i represents a row counter.

14. The method of claim 12 , wherein the parity columns are derived using the XOR function.

15. A processor configured to recover at least two data columns in a data matrix comprising at least four data columns and at least two parity columns, comprising:

a memory configured to store a calculated accelerator row representing an absent chain parity, based on available data columns and the at least two parity columns;

a processing unit configured to define a recoverable data cell in each of the at least two columns to be recovered, and to iteratively calculate a value for each recoverable data cell based on the then available columns, parity information, previously recovered data cells, and the accelerator row; and

a memory configured to store the calculated value representing a portion of the recovered data matrix.

16. The processor of claim 15 , wherein the instructions for calculating the accelerator row comprise applying the equation

c

n

-

1

,

1

=

⊕

i

=

0

n

-

2

⁢

c

i

,

1

,

where c represents an accelerator value corresponding to a cell, n represents the number of rows in the matrix, and i represents a row counter.

17. The processor of claim 15 , wherein the processing unit is configured to employ the at least two parity columns which are derived using the XOR function.

18. The processor of claim 15 , wherein the missing chain parity is calculated in a non-iterative process.