Systems and methods for providing improved encoding and reconstruction of data

• US 7,581,156 B2
• Filed: 12/16/2002
• Issued: 08/25/2009
• Est. Priority Date: 12/16/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Manasse, Mark Steven
• Primary Examiner(s): Abraham; Esaw T
• Application Number:
  US10/321,159
• Publication Number:
  US 20040117718A1
• Time in Patent Office: 2,444 Days
• Field of Search: 714/781, 714/786
• US Class Current: 714/781
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes

Abstract

Systems and methods for constructing Reed-Solomon encoding matrices are provided that are simpler and more regular than existing techniques, and which allow for the coding to be applied to more data disks than previous techniques. More particularly, systems and methods for simplifying the construction of Reed-Solomon based erasure codes, or coding matrices, over GF(2^n) in connection with circumstances wherein the number of errors to be corrected is less than or equal to three are provided.

Claims

1. A method for efficient transmission of a data field when, prior to transmission, the data field includes a number of failures less than or equal to three, comprising:

generating by at least one computer processor data representing a Vandermonde matrix over GF(2ⁿ) by;

generating an identity matrix portion;

generating an erasure coding portion comprising data values corresponding to a set of three rows having a property that each minor of the set of three rows is invertible; and

computing a determinant of a submatrix of the erasure coding portion, wherein said computing includes ignoring columns from the identity matrix portion, wherein said computing results in one of a 0 by 0, 1 by 1, 2 by 2 and 3 by 3 minor of the erasure coding portion remaining;

using by the at least one computer processor the generated data representing the Vandermonde matrix to correct the failures in the data field; and

in response to correcting the failures in the data field, transmitting by the at least one computer processor the data field to a recipient, the transmitting being made more efficient by correcting the failures in the data field prior to performing the transmitting.

2. The method according to claim 1, wherein each minor is a transposed extended Vandermonde matrix and has a non-zero determinant.

3. The method according to claim 1, wherein said submatrix of the erasure coding portion is an arbitrary m by m submatrix.

4. The method according to claim 1, wherein said generating steps increase the range of values for coding matrices.

5. A computing system operable to efficiently transmitting a data field when, prior to transmission, the data field includes a number of failures less than or equal to three, comprising:

a processor; and

a memory having stored therein computer executable instructions for performing steps comprising;

generating data representing a Vandermonde matrix over GF(2ⁿ) by;

generating an identity matrix portion;

generating an erasure coding portion comprising data values corresponding to a set of three rows having a property that each minor of the set of three rows is invertible; and

computing a determinant of a submatrix of the erasure coding portion, wherein said computing includes ignoring columns from the identity matrix portion, wherein said computing results in one of a 0 by 0, 1 by 1, 2 by 2 and 3 by 3 minor of the erasure coding portion remaining;

using the generated data representing the Vandermonde matrix to correct the failures in the data field; and

in response to correcting the failures in the data field, transmitting by the at least one computer processor the data field to a recipient, the transmitting being made more efficient by correcting the failures in the data field prior to performing the transmitting.

6. A computing system according to claim 5, wherein each minor is a transposed extended Vandermonde matrix and has a non-zero determinant.

7. A computing system according to claim 5, wherein said submatrix of the erasure coding portion is an arbitrary m by m submatrix.

8. A computing system according to claim 5, wherein generating an erasure coding portion increases the range of values for a coding matrice.

9. A computer readable storage medium readable by a machine and having stored thereon computer executable instructions being executable by the machine to perform a method of efficiently transmitting a data field when, prior to transmission, the data field includes a number of failures less than or equal to three, the computer executable instructions comprising:

generating data representing a Vandermonde matrix over GF(2ⁿ) by;

generating an identity matrix portion;

generating an erasure coding portion comprising data values corresponding to a set of three rows having a property that each minor of the set of three rows is invertible; and

computing a determinant of a submatrix of the erasure coding portion, wherein said computing includes ignoring columns from the identity matrix portion, wherein said computing results in one of a 0 by 0, 1 by 1, 2 by 2 and 3 by 3 minor of the erasure coding portion remaining;

using the generated data representing the Vandermonde matrix to correct the failures in the data field; and

in response to correcting the failures in the data field, transmitting by the at least one computer processor the data field to a recipient, the transmitting being made more efficient by correcting the failures in the data field prior to performing the transmitting.

10. The computer readable storage medium of claim 9, wherein each minor is a transposed extended Vandermonde matrix and has a non-zero determinant.

11. The computer readable storage medium of claim 9, wherein said submatrix of the erasure coding portion is an arbitrary m by m submatrix.

12. The computer readable storage medium according to claim 9, wherein said generating steps increase the range of values for coding matrices.