Error correction system for five or more errors

• US 6,343,367 B1
• Filed: 03/29/1999
• Issued: 01/29/2002
• Est. Priority Date: 03/29/1999
• Status: Expired due to Term

• Current Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Original Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Inventors: Shen, Ba-Zhong, Weng, Lih-Jyh
• Primary Examiner(s): Chung, Phung M.
• Assistant Examiner(s): Chase, Shelly A
• Application Number:
  US09/277,785
• Time in Patent Office: 1,037 Days
• Field of Search: 708/492, 714/781, 714/782, 714/784, 714/785
• US Class Current: 714/782
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing

Abstract

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 c(x) into a polynomial t(x) in which a_t−1≈0, where a_i is the coefficient of the xⁱ term of the error locator polynomial and Tr(a_t−1)=1, where Tr(a_i) is the trace of a_i. The polynomial t(x) is factored into two factors, namely, one factor that is the greatest common divisor of t(x) and $S\left(x\right)=\sum _{i=0}^{m-1}x^{2^i},$

and a second factor that is the greatest common divisor of t(x) and S(x)+1. 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), 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\left(x\right)=\frac{t\left(x\right)}{g\left(x\right)},$

and 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. When “t” is odd, the system represents the roots r_i of the error locator polynomial as a linear combination of r_i,kβ_k for k=0,1 . . . m−1, where r_i,kεGF(2) and β_k is an element of a dual basis for GF(2^m) over GF(2), and Tr(α^jβ_k) equals one when j=k and equals zero when jk. The rootsr_i are then

r_i=r_i,0β₀+r_i,1β₁+ . . . +r_i,m−1β_m−1

and $\mathrm{Tr}\left({\alpha }^jr_i\right)=\sum _{k=0}^{m-1}r_{i,k}\mathrm{Tr}\left({\alpha }^j{\beta }_k\right)=r_{i,j}$

The system next determines the greatest common divisor of the polynomial and S(α^jx) by iteratively determining R_j(x)≡S(α^jx)mod c(x), and then determining the greatest common divisor of c(x) and R_j(x). The system next determines two factors of c(x) as g(x)=gcd(c(x), R_j(x)) and $h\left(x\right)=\frac{t\left(x\right)}{g\left(x\right)}$

and finds the roots of the two factors.

Claims

1. A method for determining which symbols in a code word contain errors based on a degree-t error locator polynomial over GF(2^m), with t even and greater than or equal to six, the method including the steps of:

A. determining if a coefficient a<sub>t−

1</sub> of x<sup>t−

1</sup> of a t-degree error locator polynomial is non-zero and if not transforming the polynomial into one in which a<sub>t−

1</sub>≠

0;

B. determining if Tr(a<sub>t−

1</sub>)=1, and if not transforming the polynomial into one which Tr(a<sub>t−

1</sub>)=1, where c₂(x) is the polynomial with Tr(a<sub>t−

1</sub>)=1;

C. factoring the polynomial into $g<br><br>\left(x\right)=\gcd <br><br>\left(S<br><br>\left(x\right)=\underset{i=0}{\overset{m-1}{\sum <br><br>}}<br><br>x^{2^{\mathrm{\prime <br><br>}}},c_2<br><br>\left(x\right)\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$$h<br><br>\left(x\right)=\gcd <br><br>\left(S<br><br>\left(x\right)+1,c_2<br><br>\left(x\right)\right);<br><br>$

D. determining roots of g(x) and h(x);

E. transforming the roots into the roots of the t-degree error locator polynomial; and

F. determining which symbols in a code word are erroneous by associating the roots of the t-degree error locator polynomial with symbols in the code word.

2. The method of claim 1 further including the step of determining if the degrees of g(x) and h(x) are greater than a predetermined maximum and if so factoring either or both of g(x) and h(x) into factors with degrees that are less than or equal to the predetermined maximum.

3. The method of claim 1 wherein the step of factoring c₂(x) includes

i. determining a residue R(x)≡ S(x)mod c₂(x),

ii. determining g(x) as the greatest common divisor of c₂(x) and R(x), and

iii. determining h(x) as $\frac{c_2<br><br>\left(x\right)}{g<br><br>\left(x\right)}.$

4. The method of claim 3 wherein the step of determining the residue includes the steps of:

a. for

5. A method for determining which symbols in a code word contain errors based on a degree-t error locator polynomial c(x) over GF(2^m), with t odd and greater than or equal to five, the method including the steps of:

A. determining residues R_i(x)≡

S(α

ⁱx)mod c(x) for i=0, 1, . . . , m−

1 and selecting a residue with degree greater than or equal to one, where $S<br><br>\left(x\right)=\underset{i=0}{\overset{m-1}{\sum <br><br>}}<br><br>x^{2^i};<br><br>$

B. determining g(x)=gcd (c(x), R_i(x)) and $h<br><br>\left(x\right)=\frac{c<br><br>\left(x\right)}{g<br><br>\left(x\right)};<br><br>$

C. determining roots of g(x) and h(x); and

D. determining which symbols in a code word are erroneous by associating the roots with symbols of the code word.

6. The method of claim 5 further including the step of determining if the degrees of g(x) and h(x) are greater than a predetermined maximum and if so factoring either or both of g(x) and h(x) into factors with degrees that are less than or equal to the predetermined maximum.

7. The method of claim 5 including in the step of determining residues the steps of:

a. for

8. The method of claim 5 including in the step of determining residues the steps of:

a. for