Multi-dimensional data protection and mirroring method for micro level data
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
1492 Citations
34 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. 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 ; andgenerating an encoded data word in the form d0d1d2d3d4d5d6d7e0e1e2e3e4e5e6e7. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33)
-
-
34. 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.
-
Specification
-
- Resources
-
Current AssigneeRobert Halford
-
Original AssigneeRobert Halford
-
InventorsHalford, Robert
-
Primary Examiner(s)DILDINE JR, R STEPHEN
-
Application NumberUS10/624,208Publication NumberTime in Patent Office1,141 DaysField of Search714/759, 714/781US Class Current714/759CPC Class CodesG06F 11/1076 Parity data used in redunda...G06F 2211/1057 Parity-multiple bits-RAID6,...G06F 2211/109 Sector level checksum or EC...H03M 13/15 Cyclic codes, i.e. cyclic s...H03M 13/373 with erasure correction and...H03M 13/3761 using code combining, i.e. ...H03M 13/6306 Error control coding in com...
