Hybrid root-finding technique

Details Hybrid root-finding technique Hybrid root-finding technique

2000-01-26

2003-11-04

Tu, Christine T. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S784000

Reexamination Certificate

active

06643819

ABSTRACT:

BACKGROUND OF THE INVENTION
The invention relates generally to error correction code decoding mechanisms and, more particularly, to the decoding of Reed-Solomon error correction codes.
The use of increasingly higher density storage media in digital computer systems has caused an increase in the potential for defect-related data errors. To reduce data loss as a result of such data corruption, error correction codes are employed to correct the erroneous data.
Prior to storing data on a storage device, such as a magnetic disk or tape, it is encoded to form redundancy symbols. The redundancy symbols are appended to the data symbols to form code words, which are then stored on the storage device. When the stored data is retrieved from the storage device for decoding, the redundancy symbols provide information that allows the decoder to recognize errors and, if possible, reconstruct the original code word. For a detailed description of decoding, see “Error-Correcting Codes,” Second Edition, by W. Wesley Peterson and E. J. Weldon, Jr. (MIT Press, 1972). One widely-used error correction code is the Reed-Solomon code.
To correct errors, a Reed-Solomon decoder must determine the locations and values (or magnitudes) of the detected errors. The decoder first computes error syndromes, which it then uses to generate an error locator polynomial. Once the error locator polynomial has been generated, each error location and value may be determined.
Error locations are determined by solving for the roots of the error locator polynomial &sgr;(x) of degree t or less, where t is the number of errors that can be corrected. The solution or roots of the equation &sgr;(x)=0 correspond to the locations of the errors. These roots are of the form x=&agr;
i
, where &agr; is the primitive element of the Galois Field GF(p
q
) used to encode the data. Once all of the roots have been found, the corresponding error values are calculated using the well-known Forney algorithm. The data can then be corrected to produce an error-free data symbol.
Typically, the root-finding is the most time-consuming procedure in the decoding process. Presently, it is possible to solve for roots of low degree error locator polynomials in an efficient, direct manner. One such approach, which solves for four or less errors directly, is described in U.S. Pat. No. 5,710,782, in the name of Lih-Jyh Weng, incorporated herein by reference. The least complicated approach for solving for error locator polynomials of degree 5 to degree m−1 (where m is the symbol size) remains the Chien search, which examines each possible error location to determine if the error location is indeed an actual error location (or root) of the error locator polynomial. The decoding speed of the Chien search may be optimized by increasing the number of root-finding circuits that are used.
SUMMARY OF THE INVENTION
In one aspect of the invention, processing an erroneous code word includes finding field elements for generating roots of a least multiple of an error locator polynomial associated with the erroneous code word, using a binary code to select a linear combination of one or more of the field elements for each of the roots to be generated and generating each of the roots from each selected linear combination.
Embodiments of the invention may include one or more of the following features.
Locations of errors in the erroneous code word are determined from the generated roots. Determining the error locations from the generated roots includes determining which of the generated roots are true roots of the error locator polynomial, the true roots of the error locator polynomial corresponding to the locations of errors.
The binary code is a Gray code.
The root generation includes performing an Exclusive-OR operation on the selected linear combination. Using a binary code includes choosing one of the field elements to be Exclusive-ORed with a previously generated root for each root generation.
In another aspect of the invention, processing an erroneous code word includes generating an error locator polynomial from the erroneous code word and using a binary code to generate possible root values of the error locator polynomial.
Embodiments of the invention may include one or more of the following features.
The possible root values are evaluated as true roots of the error locator polynomial, the true roots of the error locator polynomial corresponding to locations of errors. The binary code is a Gray code.
Among the advantages of the hybrid root finding mechanism of the present invention are the following. Typically, the set of roots of the least multiple of the error locator polynomial (or “affine polynomial”) is a small subset of all possible error locations. Therefore, the search speed can be increased significantly by examining only the roots of the affine polynomial. Additionally, the property of Gray code allows a root of the affine polynomial to be constructed by using only one logic XOR operation, which adds to a previously constructed root.
Other features and advantages of the invention will be apparent from the following detailed description and from the claims.


REFERENCES:
patent: 4099160 (1978-07-01), Flagg
patent: 4162480 (1979-07-01), Berlekamp
patent: 5107503 (1992-04-01), Riggle et al.
patent: 5268908 (1993-12-01), Glover et al.
patent: 5771246 (1998-06-01), Weng
patent: 5974582 (1999-10-01), Ly
patent: 6343367 (2002-01-01), Shen et al.
Elwyn R. Berlekamp, “Algebraic Coding theory”, McGraw-Hill, Inc., 1968.

Affiliated with

Also associated with

Rating

Hybrid root-finding technique does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hybrid root-finding technique, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid root-finding technique will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3141273