Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-05-01
2003-12-30
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S764000, C360S048000, C708S492000
Reexamination Certificate
active
06671850
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data storage, and particularly to error correcting systems and methods employing on-the-fly algebraic error correcting codes. More specifically, this invention relates to an improved method for transforming an error locator polynomial into two polynomials whose roots are elements in a smaller subfield, in order to significantly simplify the complexity of the error location calculation implementation.
BACKGROUND OF THE INVENTION
The use of cyclic error correcting codes in connection with the storage of data in storage devices is well established and is generally recognized as a reliability requirement for the storage system. Generally, the error correcting process involves the processing of syndrome bytes to determine the location and value of each error. Non-zero syndrome bytes result from the exclusive-ORing of error characters that are generated when data is written on the storage medium.
The number of ECC check characters employed depends on the desired power of the code. As an example, in many present day ECC systems used in connection with the storage of 8-bit bytes in a storage device, two check bytes are used for each error to be corrected in a codeword having a length of at most 255 byte positions. Thus, for example, six check bytes are required to correct up to three errors in a block of data having 249 data bytes and six check bytes. Six distinctive syndrome bytes are therefore generated in such a system. If there are no errors in the data word comprising the 255 bytes read from storage, then the six syndrome bytes contain an all zero pattern. Under such a condition, no syndrome processing is required and the data word may be sent to the central processing unit. However, if one or more of the syndrome bytes are non-zero, then syndrome processing involves the process of identifying the location of the bytes in error and further identifying the error pattern for each error location.
The underlying mathematical concepts and operations involved in normal syndrome processing operations have been described in various publications. These operations and mathematical explanations generally involve first identifying the location of the errors by use of what has been referred to as the “error locator polynomial”. The overall objective of the mathematics involved employing the error locator polynomial is to define the locations of the bytes in error by using only the syndrome bytes that are generated in the system.
The error locator polynomial has been conventionally employed as the start of the mathematical analysis to express error locations in terms of syndromes, so that binary logic may be employed to decode the syndrome bytes into first identifying the locations in error, in order to enable the associated hardware to identify the error patterns in each location.
Moreover, error locations in an on-the-fly ECC used in storage or communication systems are calculated as roots of the error locator polynomial. The calculation of the roots represents a bottleneck in the implementation of the on-the-fly ECC. In certain designs, the roots calculation is done by explicit formulas whose hardware implementation becomes increasingly complex as the number of correctable errors increases.
In other designs, the roots calculation is done by an iterative search over all possible data symbol locations. The latency of these designs can be excessive, which requires several searches to be conducted in parallel over disjoint phases of symbol locations, and to be implemented in the arithmetic of the finite field that covers the complete data set.
Thus, there is still an unsatisfied need for a method that reduces the problem of searching over a large sector to searches over a smaller finite subfield for reducing the complexity and resulting latency of the hardware implementation.
SUMMARY OF THE INVENTION
In accordance with the present invention, a method is provided to transform an error locator polynomial into two new polynomials whose roots are elements in a smaller subfield, in order to significantly simplify the complexity, and to reduce the latency of the error correcting system hardware implementation.
The above and other features of the present invention are realized by an on-the-fly algebraic error correction system and corresponding method for reducing error location search. The method transforms an error locator polynomial into two transformed polynomials whose roots are elements in a smaller subfield, in order to significantly simplify the complexity, and to reduce the latency of the error correcting system hardware implementation.
More specifically, if the error locator polynomial is over a finite field of (2
2n
) elements, the transformed polynomials are over a finite subfield of (2
n
) elements. Thus, the problem of locating the roots of the error locator polynomial is reduced to locating the roots of the transformed polynomials. Assuming the error locator polynomial is of degree m, the present method requires at most (m
2
/2) evaluations of polynomials over the Galois field GF(2
2n
), along with root finding of two polynomials of degree m over the Galois subfield GF(2
n
).
REFERENCES:
patent: 4504948 (1985-03-01), Patel
patent: 4875211 (1989-10-01), Murai et al.
patent: 5001715 (1991-03-01), Weng
patent: 5377207 (1994-12-01), Perlman
patent: 5535140 (1996-07-01), Iwamura
patent: 5710782 (1998-01-01), Weng
patent: 5737343 (1998-04-01), Meyer
patent: 5768296 (1998-06-01), Langer et al.
patent: 5771246 (1998-06-01), Weng
patent: 5805617 (1998-09-01), Im
patent: 5818854 (1998-10-01), Meyer
patent: 5905740 (1999-05-01), Williamson
patent: 5942005 (1999-08-01), Hassner
patent: 5943348 (1999-08-01), Ly
patent: 5946328 (1999-08-01), Cox et al.
patent: 6092233 (2000-07-01), Yang
patent: 6122766 (2000-09-01), Fukuoka et al.
patent: 6154868 (2000-11-01), Cox et al.
patent: 6192497 (2001-02-01), Yang et al.
patent: 6199188 (2001-03-01), Shen et al.
patent: 6345376 (2002-02-01), Cox et al.
patent: 6374383 (2002-04-01), Weng
“Implementation of Reed Solomon Codes over Symbols of Size 16 Bits—Method and Apparatus,” IBM Technical Disclosure Bulletin, vol. 37, No. 02A, Feb. 1994.
“Fast Double Error Correction,” IBM Technical Disclosure Bulletin, vol. 25, No. 5, Oct. 1982.
D.S. Dummit, “Solving Solvable Quintics,” Mathematics of Computation, vol. 57, No. 195, Jul. 1991, pp. 387-401.
“Logic and Software Engineering,” International Workshop in Honor of Chih-Sung Tang, Aug. 14-15, 1995.
“Convenient Roots for a Reed Solomon Code,” IBM Technical Disclosure Bulletin, vol. 27, No. 2, Jul. 1984.
Carl Bender et al., “Quasi-Exactly Solvable Quartic Potential,” Journal of Physics A Mathematical and General, vol. 31, No. 14, Apr. 10, 1998.
Cox Charles Edwin
Hassner Martin Aureliano
Trager Barry Marshall
Winograd Shmuel
Baker Stephen M.
Kassatly Samuel A.
Whittington Anthony T.
LandOfFree
On-the-fly algebraic error correction system and method for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with On-the-fly algebraic error correction system and method for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-the-fly algebraic error correction system and method for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3149404