US 5,710,782 A · System for correction of three and four errors

Abstract

A system determines the error locations of four errors in GF(2.sup.2m) 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 an error locator polynomial. The system first manipulates the error locator polynomial, which is of the form: .sigma.(x)=.sigma..sub.4 x.sup.4 +.sigma..sub.3 x.sup.3 .sigma..sub.2 x.sup.2 +.sigma..sub.1 x+.sigma..sub.0 1! into the form: .theta.(y)=y.sup.4 +.theta..sub.2 y.sup.2 +.theta..sub.1 y+.theta..sub.0 2 ! where the .theta..sub.i 's are combinations of the coefficients of the terms of the error locator polynomial. The system has thus produced an equation in which the coefficient of the y.sup.3 term is 0. The system then factors .theta.(y), to produce .theta.(y)=(y.sup.2 +t*y+u)*(y.sup.2 +v*y+w), 3! where "*" represents multiplication. It then determines the values of t, u, v and w by equating the coefficients of the two expressions for .theta.(y) and solving first for the variable t, which is equal to v, and then for the variables w and u. Once the values of the variables are determined, the system solves two quadratic equations, one for each of the factors of equation 3. Based on these solutions, the system determines the four error locations associated with the degree-four error locator polynomial.

Claims6

Dependent claims

A method of determining locations of four errors in a code word of a Reed-Solomon or BCH code, the method including the steps of:

a. manipulating a degree-four error locator polynomial
.sigma.(x)=.sigma..sub.4 x.sup.4 +.sigma..sub.3 x.sup.3 +.sigma..sub.2 x.sup.2 +.sigma..sub.1 x.sup.1 +.sigma..sub.0
to produce a polynomial of the form:
.theta.(y)=y.sup.4 +.theta..sub.2 y.sup.2 +.theta..sub.1 y+.theta..sub.0 ;
b. factoring the polynomial into
.theta.(y)=(y.sup.2 +t*y+u)*(y.sup.2 +v*y+w);
c. equating the coefficients of the polynomials of steps a and b
t+v=0
t*v+u+w=.theta..sub.2
t*w+v*u=.theta..sub.1
u*w=.theta..sub.0 ;
h. determining an equation with t as the only unknown:
t.sup.3 +.theta..sub.2 t+.theta..sub.1 =0
e. solving for a root t.sub.0 ;
f. forming a quadratic equation with u and w as roots:
p.sup.2 +(.theta..sub.2 +t.sub.0.sup.2)p+.theta..sub.0 0
g. solving for the roots p.sub.0 and p.sub.1 ;
h. substituting the roots into .theta.(y) and determining the roots of a pair of quadratic equations:
y.sup.2 +t.sub.0 *y+p.sub.1 =0
y.sup.2 +t.sub.0 *y+p.sub.0 =0;
i. associating the roots y.sub.0, y.sub.1 and y.sub.2, y.sub.3 of the pair of quadratic equations with the roots of the degree-four error locator polynomial;
and
j. associating the roots of the degree-four error locator polynomial with locations in the code word.

20 more elements

A method of determining locations of four errors in a code word of a Reed-Solomon or BCH code, the method including the steps of:

a. manipulating a degree-four error locator polynomial
.sigma.(x)=.sigma..sub.4 x.sup.4 +.sigma..sub.3 x.sup.3 +.sigma..sub.2 x.sup.2 +.sigma..sub.1 x.sup.1 +.sigma..sub.0
by
i. changing variable to x=y+r, where ##EQU51## and expanding and collecting terms to produce an equation of the form:
.gamma.(y)=.sigma..sub.4 y.sup.4 +.sigma..sub.3 y.sup.3 +(.sigma..sub.3 r+.sigma..sub.2)y.sup.2 +(.sigma..sub.3 r.sup.2 .sigma..sub.1)y+.sigma..sub.4 r.sup.4 +.sigma..sub.3 r.sup.3 +.sigma..sub.2 r.sup.2 +.sigma..sub.1 r+.sigma..sub.0 =0;
ii. substituting ##EQU52## into the equation of step i to produce an equation of the form:
.gamma.(y)=.sigma..sub.4 y.sup.4 +.sigma..sub.3 y.sup.3 +(.sigma..sub.3 *.sigma..sub.1).sup.1/2 +.sigma..sub.2 !y.sup.2 +s,
where s is the constant term of the equation of step i;
iii. finding the roots of:
##EQU53## which expands to
.theta.(y)=y.sup.4 +.theta..sub.2 y.sup.2 +.theta..sub.1 y+.theta..sub.0 =0
where ##EQU54## b. factoring
.theta.(y)=(y.sup.2 +t*y+u)*(y.sup.2 +v*y+w);
c. determining the values of t,u, v and w;
d. substituting the values t, u, v and w into .theta.(y) and determining the roots of a pair of quadratic equations:
y.sup.2 +t*y+u=0
y.sup.2 +v*y+w=0;
e. associating the roots y.sub.0, y.sub.1 and y.sub.2, y.sub.3 of the pair of quadratic equations with the roots of the degree-four error locator polynomial;
and
f. associating the roots of the degree-four error locator polynomial with locations in the code word.

17 more elements

Dependencies are inferred from the claim text.

System for correction of three and four errors

Life of this patent

System for correction of three and four errors

Life of this patent

Abstract

Claims6