Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-03-08
2001-03-06
De Cady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000
Reexamination Certificate
active
06199188
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to data processing systems and, more particularly, to a system for decoding and correcting errors in data using an error correction code.
BACKGROUND OF THE INVENTION
Data stored on magnetic media, such as a 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 members 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 sting 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. MrT 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 (P
m
)”, where “P” is a prime number and “m” can be thought of as the number of digits, base “P”, in each element or symbol in the field. P usually has the value 2 in digital computer and disk drive applications and, therefore, m 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 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 systems, such as digital computers, there is only one possible error value for an error location, and thus, the step of determining 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 locations of either three or four errors. This involves finding the roots of third and fourth degree error locator polynomials.
In prior systems, the roots of degree-four polynomials are determined by trial and error, or by matrix manipulation or look-up table. The trial and error method is performed by substituting into the polynomial every possible value, i.e., every element of the applicable GF(2
2m
) 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 four roots are determined. This trial and error process, which in an optimized form is commonly known as a Chien Search, is time consuming. Further, the time is unpredictable, since it varies with the locations of the errors in the code words.
The matrix manipulation and look-up table methods involve transforming a general degree-four polynomial of the form:
&sgr;
4
x
4
+&sgr;
3
x
3
+&sgr;
2
x
2
+&sgr;
1
x+&sgr;
0
into a polynomial of the form:
x
4
+x
2
+ax+b.
If a look-up table is used, the table contains a set of solutions for every possible set of values of a and b. For the ECCs used today, typically over GF(2
8
), the table has 2
16
entries, each with 32 bits, i.e., four 8-bit elements. Thus, the table takes up a great deal of storage space and requires a relatively complex addressing scheme.
A system using the matrix manipulation method produces an 2
m
-by-2
m
matrix, by determining f(&agr;), f(&agr;
1
), f(&agr;
2
) . . . fa(.&agr;
(2
m
−1)
), where f(x)=x
4
+x
2
+ax+b. It next manipulates the matrix to determine the null space of the space spanned by the matrix. The roots of the polynomial can then be obtained from the vectors that span the null space. [For a more detailed description see, E. R Berlekamp,
Algebraic Coding Theory,
McGraw Hill Book Company, 1968]. This method requires bit-by-bit manipulation of an 2m-by-2m matrix and typically requires numerous manipulation operations to transform the matrix. Thus, it is time consuming and computation intensive.
The inventive system described herein uses the invention discussed in patent application Ser. No. 08/580,294 filed Dec. 28, 1995, now U.S. Pat. No. 5,761,102, which is assigned to a common assignee and incorporated herein by reference. The system determines the roots of the degree-four polynomial by solving two quadradic equations. The system makes use of a well known method of deter the roots of a degree-two polynomial, as descried by Berlekamp in
Algebraic Coding Theory.
Further, the system makes use of a method of determining the roots of a degree-three polynomial that is described by Van der Horst and Berger in
Complete Decoding of Triple
-
Error
-
Correcting Binary BCH Codes
, IEEE Transactions on Information Theory, Vol. IT-22, pp. 138-147, 1976. Van der Horst and Berger have established that the method works for even-bit fields GF(2
2m
) for m=2 and 3. In the above-referenced application it was determined that the method works for at least even-bit fields GF(2
2m
) for m=4, 5 and 6. We have determined that the method works for any GF(2
2m
), as discussed below. We also provide herein a method to determine the roots of a degree-four polynomial in any odd-bit field GF (2
2m+1
), as discussed in more detail below.
Finding the roots of the degree-three polynomial in accordance with the teachings of Van der Horst and Berger and in accordance with our methods discussed herein requires determining a cubic root of a Galois field element over GF(2
2m
) or GF(2
2m+1
). We have developed an inventive circuit for relatively quickly and easily finding the cubic roots in the even-bit field GF(2
m
), and in the odd-bit field GF(2
2m+1
).
SUMMARY OF THE INVENTION
The invention is a system that determines the error locations of four errors in GF(2
m
), for any m, by transforming a degree-four error locator polynomial ultimately into two quadratic equations, finding the solutions of these equations, and from these solutions determining the roots of the error locator polynomial.
More specifically, the system first manipulates the degree-four polynomial:
&sgr;(
x
)=&sgr;
4
x
4
+&sgr;
3
x
3
+&sgr;
2
x
2
+&sgr;
1
x
+&sgr;
0
[1]
into the form:
&thgr;(
y
)=
y
4
+&thgr;
2
y
2
+&thgr;
1
y
+&thgr;
0
[2]
where the &thgr;
i
's are combinations of the coefficients of the terms of the error locator polynomial. Note that the coefficient of the y
3
term is zero. The system
Shen Ba-Zhong
Weng Lih-Jyh
Cady Albert De
Cesari & McKenna
Quantum Corporation
Ton David
LandOfFree
System for finding roots of degree three and degree four... 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 for finding roots of degree three and degree four..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for finding roots of degree three and degree four... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2468648