Determining error locations using error correction codes

Details Determining error locations using error correction codes Determining error locations using error correction codes

1999-06-07

2002-04-16

Tu, Christine T. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S793000

Reexamination Certificate

active

06374383

ABSTRACT:

BACKGROUND OF THE INVENTION
The invention relates generally to error correction code decoding mechanisms and more particularly to the decoding of Bose-Chaudhuri-Hocquenghem (BCH) correction codes, including 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, 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 which allows the decoder to recognize errors and, if possible, reconstruct the original code word. For a detailed description of decoding, see Peterson and Weldon, Error Correction Codes, 2d Edition, MIT Press, 1972.
One widely-used error correction code is the Reed-Solomon code. Error detection and correction techniques for Reed-Solomon codes are well known.
To correct detected errors, a 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”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
60
is the primitive element of the Galois Field GF(p
q
) used to encode the data. Once all t 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.
One of the most efficient techniques for root finding is the so-called Chien search, which is a systematic trial-and-error root finding technique widely employed in error correcting systems. The Chien search systematically tries each element x=&agr;
i
of GF(p
q
) as a possible solution to the error locator polynomial equation &sgr;(x)=0. Each time a new value of x is evaluated, t Galois Field multiplication operations and t Galois Field addition operations are performed to determine if x is a solution. Because the Chien search evaluates one element (or location value) at a time, the time to complete the entire search is independent of the degree t of the error locator polynomial &sgr;(x) under investigation.
SUMMARY OF THE INVENTION
In one aspect of the invention, a computation circuit in a decoder is operated in a first mode to compute syndrome values in response to a first set of inputs. When used in a second mode, the computation circuit computes location values in response to a second set of inputs.
Embodiments of the invention may include one or more of the following features.
The first set of inputs may correspond to code word polynomial coefficients. The second set of inputs may correspond to error locator polynomial coefficients of an error locator a polynomial.
The computation circuit may include r parallel computation stages. In the first mode, the computation circuit can compute r syndromes for the first set of inputs. In the second mode, the computation circuit can compute greater than r location values.
For an error locator polynomial of a degree t, operating the computation circuit in the second mode can further include computing a different one of the r location values in a corresponding one of the r parallel computation stages during t+1 clock cycles.
The computation circuit may be operated in the second mode of operation to compute a number of location values greater than r by scaling the second set of inputs. The second set of inputs may be scaled by multiplying each error locator polynomial coefficient in the second set of inputs by a Galois Field element so that location values are computed for Galois Field elements of a power greater than r.
The power of the Galois Field element by which the error locator polynomial coefficients can be multiplied may be a multiple of r.
A zero or non-zero condition may be determined for each of the computed location values. The computed location values which are determined to be equal to zero are roots of the error locator polynomial and may be used to obtain error positions.
The computational scheme of the present invention offers several advantages. It reduces the amount of circuitry required to implement a decoder by allowing the error location polynomial root search to share syndrome computation circuitry with the syndrome generator of the decoder. Also, the root search is faster that the conventional Chien search. Moreover, the search speed increases as the degree of the polynomial becomes smaller, a property of particular importance when the number of errors to be corrected is smaller than the code error-correction capability of the decoder.
Other features and advantages of the invention will be apparent from the following detailed description and from the claims.


REFERENCES:
patent: 4841300 (1989-06-01), Yoshida et al.
patent: 5446753 (1995-08-01), Zook
patent: 6031875 (2000-02-01), Im

Affiliated with

Also associated with

Rating

Determining error locations using error correction codes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Determining error locations using error correction codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining error locations using error correction codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2910945