Multi-dimensional data protection and mirroring method for micro level data

• US 20040123223A1
• Filed: 07/22/2003
• Published: 06/24/2004
• Est. Priority Date: 07/29/2002
• Status: Active Grant

• Current Assignee: Robert Halford
• Original Assignee: Robert Halford
• Inventors: Halford, Robert
• Granted Patent: US 7,103,824 B2
• Time in Patent Office: Days
• US Class Current: 714/781
• 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/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H03M 13/6306 Error control coding in combination with Automatic Repeat reQuest [ARQ] and diversity transmission, e.g. coding schemes for the multiple transmission of the same information or the transmission of incremental redundancy H03M13/3761, H03M13/3769 and H03M13/635 take precedence

Abstract

The invention discloses a data validation, mirroring and error/erasure correction method for the dispersal and protection of one and two-dimensional data at the micro level for computer, communication and storage systems. Each of 256 possible 8-bit data bytes are mirrored with a unique 8-bit ECC byte. The ECC enables 8-bit burst and 4-bit random error detection plus 2-bit random error correction for each encoded data byte. With the data byte and ECC byte configured into a 4 bit×4 bit codeword array and dispersed in either row, column or both dimensions the method can perform dual 4-bit row and column erasure recovery. It is shown that for each codeword there are 12 possible combinations of row and column elements called couplets capable of mirroring the data byte. These byte level micro-mirrors outperform conventional mirroring in that each byte and its ECC mirror can self-detect and self-correct random errors and can recover all dual erasure combinations over four elements. Encoding at the byte quanta level maximizes application flexibility. Also disclosed are fast encode, decode and reconstruction methods via boolean logic, processor instructions and software table look-up with the intent to run at line and application speeds. The new error control method can augment ARQ algorithms and bring resiliency to system fabrics including routers and links previously limited to the recovery of transient errors. Image storage and storage over arrays of static devices can benefit from the two-dimensional capabilities. Applications with critical data integrity requirements can utilize the method for end-to-end protection and validation. An extra ECC byte per codeword extends both the resiliency and dimensionality.

Claims

13. ) A method of encoding data in the form of a data byte Di=d0d1d2d3d4d5d6d7 comprising the steps of:

selecting an irreducible error correcting eighth degree polynomial;

dividing the data byte by the polynomial to produce an error correction code in the form Ei=e0e1e2e3e4e5e6e7; and

generating an encoded data word in the form d0d1d2d3d4d5d6d7e0e1e2e3e4e5e6e7.

1. ) A method of encoding a data byte, comprising the steps of:

selecting an irreducible polynomial;

generating an error control code as a function of the polynomial and the data; and

generating an encoded data matrix wherein the data and the error control code comprise the elements of the matrix dispersing an element of the encoded data matrix to a selected one of a plurality of channels based upon a position of the element in the matrix.

2. ) The method of claim 1, wherein:

the polynomial is selected as a irreducible polynomial.

3. ) The method of claim 1, wherein:

the error control code is the same length as the data byte.

4. ) The method of claim 2, wherein the data is digitally represented by eight bits and further wherein:

the polynomial is selected as an eighth degree polynomial.

5. ) The method of claim 4, wherein the polynomial is in the form of 1+x3+x4+x5+x8.

6. ) The method of claim 4, wherein the polynomial is in the form of 1+x+x2+x4+x6+x7+x8.

7. ) The method of claim 1, wherein the error control code is generated by dividing the data by the polynomial, the error control code being the remainder modulo the polynomial.

8. ) The method of claim 1, wherein six pair combinations of row elements can be equated to a data row element pair.

9. ) The method of claim 1, wherein six pair combinations of column elements can be equated to a data row element pair.

10. ) The method of claim 1, wherein pair combinations of elements can be equated to any other pair of elements.

11. ) The method of claim 1, comprising the further steps of forming a second error control code of two additional row elements, whereby further pair combination of row elements or column elements can be equated to any other pair combination of row elements or column elements.

12. ) The codeword of claim 1 wherein each codeword element is sent to a separate device.

14. ) The method of claim 13, wherein the polynomial is in the form of 1+x3+x4+x5+x8.

15. ) The method of claim 13, wherein the polynomial is in the form of 1+x+x2+x4+x6+x7+x8.

16. ) The method of claim 13, wherein the error control code is generated by dividing the data by the polynomial, the error control code being the remainder modulo the polynomial.

17. ) The method of claim 13, comprising the further step of:

forming the encoded data word as an array.

18. ) The method of claim 17, wherein multiple data bytes are encoded and formed as encoded data words, the encoded data words being formed into an array of arrays.

19. ) The method of claim 18, further comprising:

forming a error detection code for every element in the rows and columns of the array of arrays.

20. ) The method of claim 19, wherein error recovery is desired and is accomplished by the further steps of:

counting errors in a codeword in a column;

counting errors in a codeword in a row;

using row equations to correct errors if the number of row errors is less than row errors;

using column equations otherwise.

21. ) The method of claim 19, wherein error recovery is desired and is accomplished by the further steps of:

counting errors in a codeword in a column;

counting errors in a codeword in a row;

using row equations to correct errors if the number of row errors is less than or equal to column errors;

using column equations otherwise.

22. ) The method of claim 17, comprising the forming the encoded data word as a 4×

4 array.

23. ) The method of claim 17, comprising the further step of:

forming the encoded data word as a 3×

4 array.

24. ) The method of claim 17, comprising the further step of:

forming the encoded data word as a 4×

3 array.

25. ) The method of claim 17, comprising the further step of:

arranging the matrix so that each element of the data byte is horizontally or vertically adjacent to at least three other elements of the data byte.

26. ) The method of claim 17, comprising the further step of:

arranging the matrix so that each element of the data byte and the error control byte is a row of the matrix.

27. ) The method of claim 17, comprising the further step of:

forming the encoded data matrix as

d0d1d2d3

d4d5d6d7

e0e1e2e3

e4e5e6e7.

28. ) The method of claim 27, comprising the further steps of:

dispersing the first row of the matrix to a first device;

dispersing the second row of the matrix to a second device;

dispersing the third row of the matrix to a third device;

dispersing the fourth row of the matrix to a fourth device; and

dispersing each column of the matrix to one of the first through fourth devices such that only one column from the matrix is stored on any of the first through fourth storage devices.

29. ) The method of claim 28, wherein in the event that up to two of the devices fails, a method of recovering lost data includes the step of:

determining which of the first through fourth devices that has not failed and contains error correction codes for data on a drive that has failed;

retrieving the dispersed combination of error correction codes and data from the device so selected;

recreating data dispersed to a failed device using the known data and error correction codes in the equations below to recreate lost data

e0=d0+d3+d4+d5+d6e1=d1+d4+d5+d6+d7e2=d2+d5+d6+d7e3=d0+d4+d5+d7e4=d0+d1+d3+d4e5=d0+d1+d2+d3+d6e6=d1+d2+d3+d4+d7e7=d2+d3+d4+d5.

30. ) The method of claim 29, wherein in the event that up to two of the devices fails, a method of recovering lost data includes the step of:

determining which of the first through fourth devices that has not failed and contains error correction codes for data on a drive that has failed;

retrieving the dispersed combination of error correction codes and data from the device so selected;

recreating data dispersed to a failed device using the known data and error correction codes in the equations below to recreate lost data

e0=d0+d1+d3+d6e1=d0+d2+d3+d4+d6+d7e2=d0+d4+d5+d6+d7e3=d1+d5+d6+d7e4=d0+d1+d2+d3+d7e5=d1+d2+d3+d4e6=d0+d1+d2+d4+d5+d6e7=d0+d2+d5+d7.

28-1. ) The method of encoding a data byte of claim 27, wherein multiple databytes are encoded as codewords and the codewords are

31. ) A method of encoding a data byte, comprising the steps of:

selecting an irreducible polynomial;

generating a first error control code as a function of the polynomial and the data;

generating a second error control code as a function of the polynomial and the data;

generating an encoded first data matrix wherein the data and the first error control codes comprise the elements of the matrix;

generating an encoded second data matrix wherein the data and the first and second error control codes comprise elements of the matrix; and

dispersing an element of the encoded data matrix to a selected one of a plurality of channels based upon a position of the element in the matrix.

32. ) A method of encoding a data byte, comprising the steps of:

selecting an irreducible polynomial;

generating an error control code as a function of the polynomial and the data;

generating an encoded data matrix wherein the data and the error control code comprise the elements of the matrix; and

dispersing an element of the encoded data matrix to a selected one of a plurality of channels based upon a position of the element in the matrix.