Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-03-29
2002-01-29
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06343367
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 thus required to correct greater numbers of errors, which include greater numbers of burst 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 (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 high rate 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.
The steps of determining the syndromes and finding the error locations are the most time consuming in the error correction process. This invention relates to the step of finding the error locations.
“Fast” methods for finding four or fewer errors are known, and we have developed a system for finding 5 errors with the aid of a relatively small lookup table that is discussed in co-pending patent application IMPROVED FIVE-ERROR CORRECTION SYSTEM, Ser. No. 08/984,698 now U.S. Pat. No. 5,978,956. However, prior known systems that find the error locations for error locator polynomials of degree 6 or more perform time consuming Chien searches. A Chien search is a systematic trial and error approach that involves tying each element of the applicable Galois field as a root of the error locator equation. If the Galois Field is relatively large, the Chien search takes a long time, and thus, slows the error correction operation. An alternative to the Chien search is to use a lookup table that is entered with the 6 or more coefficients of the error locator polynomial. To correct even six errors, the associated lookup table is prohibitively large since it must include all possible distinct roots for the degree-six error locator polynomials. In GF(2
M
) the lookup table has (2
M
)
6
entries. For systems that use 8-bit symbols, the lookup table has (2
8
)
6
or 2
48
entries, with each entry including six 8-bit roots of the error locator polynomial. For many systems, the lookup table takes up too much storage space. This is particularly true as larger Galois Fields are used to protect more data. Indeed, some systems may require that no lookup table is used.
SUMMARY OF THE INVENTION
An error correcting system for correcting “t” errors over GF(2
m
), where t is even and preferably greater than or equal to six, transforms the t-degree error locator polynomial into a polynomial in which a
t−1
≠0, where a
i
is the coefficient of the x
i
term of the error locator polynomial. As necessary, the system further transforms the polynomial into one in which Tr(a
t−1
)≠0, where Tr(a
i
) is the trace of a
i
or a mapping of a
i
to an element of GF(2). Based on the non-zero trace of a
t−1
, there are an odd number of roots that have traces equal to 1 and an odd number of roots that have traces equal to 0, since the sum of the roots of the polynomial is equal to a
t−1
and the sum of the traces of the roots is equal to the trace of the sum.
The roots of the polynomial are elements of GF(2
m
), and all elements of GF(2
m
) with traces equal to 0 are roots of
S
(
x
)
=
∑
i
=
0
m
-
1
x
2
i
,
and all elements with traces equal to 1 are roots of S(x)+1. Accordingly, the polynomial can be factored into two factors, namely, one factor that is the greatest common divisor of the polynomial and S(x) and a second factor that is the greatest common divisor of the polynomial and S(x)+1. If the two factors each have degrees less than or equal four, the system uses a fast method to determine the roots of each of the factors. The system then, as necessary, transforms these roots into the roots of the error locator polynomial. Otherwise, the system continues factoring until the degrees of the factors are less than or equal to some desired degree before it determines the roots of the factors.
Preferably, the system determines the greatest common divisor of the polynomial and S(x) in two steps, first iteratively determining a residue R(x)≡S(x)mod t(x), where t(x) is the polynomial that has the term a
t−1
with a trace of zero, and then calculating the greatest common divisor of t(x) and the lower-degree R(x). The system produces two factors of t(x), namely, g(x)=gcd(t(x), R(x)) and
h
(
x
)
=
t
(
x
)
g
(
x
)
.
The system then determines the roots of the factors and transforms these roots into the roots of the error locator polynomial or, as necessary, continues factoring into factors of lower degree before determining the roots. We discuss the iterative technique for determining R(x) in more detail below.
When the degree of the error locator polynomial is odd, the system represents the roots r
i
of the error locator polynomial as a linear combination of r
i,k
&bgr;
k
for k=0,1 . . . m−1, where r
i,k
&egr;GF(2) and &bgr;
k
is an element of a dual basis for GF(2
m
) over GF(2). Using the dual basis, Tr(&agr;
j
&bgr;
k
)=1 when j=k and equals 0 otherwise. The roots r
i
are then
r
i
=r
i,0
&bgr;
0
+r
i,1
&bgr;
1
+ . . . +r
i,m−1
&bgr;
m−1
and
Tr
(
α
j
r
i
)
=
∑
k
=
0
m
-
1
r
i
,
k
Tr
(
α
j
β
k
)
=
r
i
,
j
The system determines a value for j for which the traces of the roots are not all zero or all one. The greatest common divisor of the error locator polynomial and S(&agr;
j
x) then has a degree less than t, as does the greatest common divisor of the error locator polynomial and S(&agr;
j
x)+1. The system next determines the greatest common divisor of the polynomial and S(&agr;
i
x) by iteratively determining R
j
(x)≡S(&agr;
j
x)mod c(x), where c
Shen Ba-Zhong
Weng Lih-Jyh
Cesari and McKenna LLP
Chase Shelly A
Chung Phung M.
Maxtor Corporation
LandOfFree
Error correction system for five or more errors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Error correction system for five or more errors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correction system for five or more errors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2866374