Extended row diagonal parity with optimal decoding procedure

• US 8,595,606 B1
• Filed: 07/14/2011
• Issued: 11/26/2013
• Est. Priority Date: 07/16/2010
• Status: Expired due to Fees

• Current Assignee: Jolly Seven, Series 70 of Allied Security Trust I (Allied Security Trust)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Feng, Jun, Chen, Yu
• Primary Examiner(s): Merant, Guerrier
• Application Number:
  US13/182,665
• Time in Patent Office: 866 Days
• Field of Search: None
• US Class Current: 714/800
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1059 Parity-single bit-RAID5, i.e. RAID 5 implementations
• CPC Class Codes: H03M 13/2909 Product codes
• CPC Class Codes: H03M 13/293 with erasure setting

Abstract

A method of recovering two data columns in a row diagonal parity redundant array comprising at least four data columns and two parity columns, comprising: (1) calculating as an accelerator row, a missing chain parity based on available data columns and the two parity columns; (2) defining a recoverable data cell in each of the two columns to be recovered; and (3) 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.

Claims

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

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

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

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

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

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.