Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-03-17
2003-06-17
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06581180
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to data processing systems and, more particularly, to a system for locating and correcting errors in data using an error correction code.
2. Background Information
Data stored on magnetic media, such as magnetic disks, are typically stored in encoded form, so that errors in the stored data can possibly be corrected. The errors may occur, for example, because of inter-symbol interference, a defect in the disk, or noise. As the density of the data stored on the disk increases, more errors are likely, and the system is required to correct greater numbers of errors. The speed with which the system corrects the errors is important to the overall speed with which the system processes the data.
Prior to recording, multiple-bit data symbols are encoded using an error correction code (ECC). When the data symbols are retrieved from the disk and demodulated, the ECC is employed to, as the name implies, correct the erroneous data.
Specifically, before a string of k data symbols is written to a disk, it is mathematically encoded using an (n, k) ECC to form n-k ECC symbols. The ECC symbols are then appended to the data string to form an n-symbol error correction code word, which is then written to, or stored, on the disk. When the data are read from the disk, the code words containing the data symbols and ECC symbols are retrieved and mathematically decoded. During decoding, errors in the data are detected and, if possible, corrected through manipulation of the ECC symbols [for a detailed description of decoding see, Peterson and Weldon,
Error Correction Codes,
2nd Ed. MIT Press, 1972].
To correct multiple errors in strings of data symbols, the system typically uses an ECC that efficiently and effectively utilizes the various mathematical properties of sets of symbols known as Galois fields. Galois fields are represented “GF (S
P
)”, where “S” is a prime number and “P” can be thought of as the number of digits, base “S”, in each element or symbol in the field. S usually has the value 2 in digital computer and disk drive applications and, therefore, P is the number of bits in each symbol. The ECC's commonly used with the Galois Fields are Reed Solomon codes or BCH codes.
There are essentially four major steps in decoding a corrupted code word of a Reed-Solomon code or a BCH code. The system first determines error syndromes that are based on the results of a manipulation of the ECC symbols. Next, using the error syndromes, the system determines an error locator polynomial, which is a polynomial that has the same degree as the number of errors. The system then finds the roots of the error locator polynomial and from each root determines the location of an associated error in the code word. Finally, the system finds error values for the error locations. In binary codes, there is only one possible error value for an error location, and thus, the step of determine g error values is trivial.
The steps of determining the syndromes and finding the error locations are the most time consuming in the error correction process. The invention described herein reduces the time it takes the error correction system to find the error locations, which involves finding the roots of degree-t error locator polynomials
In many systems the roots of the error locator polynomials are determined by trial and error. The trial and error method is performed by substituting into the polynomial every possible value, i.e., every element of the applicable GF(2
P
) that is associated with a code word location, and for each value evaluating the polynomial. If the polynomial equals zero for a given value, the value is a root. The system continues the trial and error process by substituting a next possible value into the polynomial and determining if that value is a root; and so forth, until either all possible values have been tried or all t roots are determined. This trial and error process, which in an optimized form is commonly known as a Chien search, is time consuming. The time taken to perform the Chien search slows the error correction operations, and thus, the data processing operations of the system.
One way to speed up the Chien search is to test multiple elements simultaneously. However, as discussed with reference to
FIG. 1
below, this requires including in the conventional system t−1 additional GF(2
P
) multipliers for each additional element tested. To test “j” elements simultaneously, the system requires j(t−1) GF(2
p
) multipliers, and the system thus readily becomes complex.
SUMMARY OF THE INVENTION
A system for performing a Chien search simultaneously tests multiple elements of GF(2
P
) as possible roots of a degree-t error locator polynomial &sgr;(x) using in one embodiment t−1 simplified multipliers that each simultaneously produce the corresponding terms of &sgr;(x) to test as possible roots &agr;
2
, (&agr;
2
)
2
, (&agr;
2
)
3
. . . &agr;
2j
. Each multiplier includes a plurality of adders that are set up in accordance with precomputed terms that are based on combinations of the weight-one elements of GF(2
P
). A summing circuit adds together the associated terms produced by the multipliers and produces j multiple sums, which are then evaluated to test the j individual elements as possible roots. The coefficients of &sgr;(&agr;
2
)
j
are then fed back to the multipliers, and the multipliers test, during a next clock cycle, the elements &agr;
2
*(&agr;
2
)
j
, (&agr;
2
)
2
*(&agr;
2
)
j
. . . , (&agr;
2
)
2j
and so forth. The same operations are also performed for &sgr;′(x)=&sgr;(&agr;x) to test as possible roots &agr;
3
, &agr;
5
, &agr;
7
. . . &agr;
2j+1
.
If P=mn, that is, if P is not prime, the system may be implemented using a plurality of GF(2
m
) multipliers. The field GF(2
m
) is a subfield of GF(2
P
), and the elements of GF(2
P
) can each be represented by a combination of n elements of GF(2
m
). The error locator polynomial &sgr;(x) can thus be represented by a combination of n expressions &sgr;
0
(x), &sgr;
2
(x) . . . &sgr;
n−1
(x), each with coefficients that are elements of GF(2
m
). Each of the n expressions has 2
m
−1 coefficients for the terms x
0
, x
1
, x
2
. . . x
2m−1
. Thus, n(2
m
−2) constant GF(2
m
) multipliers are used to test each element of GF(2
P
) as a possible root, as discussed in more detail below.
The number of GF(2
m
) multipliers in the system is independent of the degree of the error locator polynomial, and each multiplier operates over a subfield of GF(2
P
). Accordingly, the system can simultaneously tests j elements using j sets of n(2
m
−2) multipliers over GF(2
m
). This is in contrast to conventional Chien search systems that require j(t−1) multipliers over GF(2
P
) to simultaneously test j elements.
REFERENCES:
patent: 5001715 (1991-03-01), Weng
patent: 6199188 (2001-03-01), Shen et al.
patent: 6260173 (2001-07-01), Weng et al.
Cesari and McKenna LLP
Chung Phung M.
Maxtor Corporation
LandOfFree
System and method for performing a Chien search using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for performing a Chien search using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing a Chien search using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3152537