Systems and methods for providing improved encoding and reconstruction of data

• US 20040117718A1
• Filed: 12/16/2002
• Published: 06/17/2004
• Est. Priority Date: 12/16/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Manasse, Mark Steven
• Granted Patent: US 7,581,156 B2
• Time in Patent Office: Days
• 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{circumflex over ( )}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 of generating data representing a Vandermonde matrix over GF(2{circumflex over ( 

)}n) when the number of failures to be corrected is less than or equal to three, comprising;

generating an identity matrix portion; and

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

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

3. A method according to claim 1, further comprising computing the determinant of an arbitrary m by m submatrix of the identity matrix portion, wherein said computing includes ignoring the columns from the identity matrix portion.

4. A method according to claim 2, 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.

5. A method according to claim 1, wherein the range of values for coding matrices is increased relative to a standard data structure for storing a Vandermonde matrix.

6. At least one of an operating system, driver code, an application programming interface, a tool kit and a processing device for providing the method of representing data of claim 1.

7. A modulated data signal carrying computer executable instructions for performing the method of claim 1.

8. A computer readable medium comprising computer executable instructions for performing the method of claim 1.

9. A method of encoding data with a data structure, the data structure representing a Vandermonde matrix over GF(2{circumflex over ( 

)}n) when the number of failures to be corrected is less than or equal to three, the data structure comprising an identity matrix portion and an erasure coding portion comprising data values corresponding to a set of three rows having the property that each minor of the set of three rows is invertible, the method comprising multiplying said data structure and said data, wherein said multiplying includes multiplying utilizing a logarithm table having logarithms.

10. A method according to claim 9, wherein the logarithms in encoding columns of the logarithm table corresponding to the set of three rows, respectively, are zero, the consecutive integers starting from zero and integers increasing by two starting from zero.

11. A method according to claim 9, wherein said multiplying further includes multiplying using an antilog table, wherein multiplication of two elements of GF(2{circumflex over ( 

)}n) includes;

looking up the corresponding logarithms in the logarithm table;

adding the logarithms; and

utilizing the antilog table to take the antilog of the result.

12. A method according to claim 9, wherein said multiplying eliminates the cost of looking up an entry in the logarithm table compared to conventional techniques.

13. A computer readable medium comprising computer executable instructions for performing the method of claim 9.

14. A method of reconstructing data with a data structure, the data structure representing a Vandermonde matrix over GF(2{circumflex over ( 

)}n) when the number of failures to be corrected is less than or equal to three, the data structure comprising an identity matrix portion and an erasure coding portion comprising data values corresponding to a set of three rows having the property that each minor of the set of three rows is invertible, the method comprising;

performing a parity check function, if only one erasure is being corrected; and

inverting said Vandermonde matrix, if two or three errors are being corrected.

15. A method according to claim 14, further comprising:

reconstructing further data by linearly combining elements of the Vandermonde matrix and corresponding check element multipliers.

16. A computer readable medium comprising computer executable instructions for performing the method of claim 14.

17. A data structure for storing a Vandermonde matrix over GF(2{circumflex over ( 

)}n) when the number of failures to be corrected is less than or equal to three, comprising;

an identity matrix portion; and

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

18. A data structure according to claim 17, wherein each minor is a transposed extended Vandermonde matrix and has a non-zero determinant.

19. A data structure according to claim 17, having the property that when computing the determinant of an arbitrary m by m submatrix of the erasure coding portion, the columns from the identity-portion of the matrix are ignored.

20. A data structure according to claim 18, wherein said computing of the determinant leaves one of a 0 by 0, 1 by 1, 2 by 2 and 3 by 3 minor of the erasure coding portion.

21. A data structure according to claim 17, wherein the range of values for coding matrices is increased relative to a standard data structure for storing a Vandermonde matrix.

22. A data structure according to claim 17, wherein the Vandermonde matrix is a matrix having columns of consecutive powers of distinct elements of the ground field of the working domain.