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

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,710,782 A
- Document ID: US5710782A
- Status: Granted
- Kind: A
- Application number: 08/580,351
- Filed: 1995-12-28
- Granted: 1998-01-20
- Earliest claimed: 1995-12-28
- Assignees: Quantum Corporation
- Inventors: Lih-Jyh Weng
- Web page: https://patentgrep.com/patent/US5710782A

## CPC

- H03M 13/151: {using error location or error correction polynomials}
- G06F 7/724: {Finite field arithmetic (for error detection or correction in general H03M13/00, in computers G06F11/10)}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The method of claim 1, wherein the step of solving for a root of
t.sup.3 +.theta..sub.2 t+.theta..sub.1 =0
includes:
i. changing variable to ##EQU44## where a=.theta..sub.2, to produce an equation of the form ##EQU45## ii. multiplying the equation of step i by z.sup.3 to obtain a quadratic equation with z.sup.3 as the variable:
(z.sup.3).sup.2 +.theta..sub.1 z.sup.3 +a.sup.3 =0;
iii. solving the quadratic equation of step ii for z.sup.3 ;
iv. determining the cube root, z.sub.0, of z.sup.3 ; and
v. substituting the value of z.sub.0 into the expression ##EQU46##

### Claim 3 (depends on 1)

The method of claim 1 wherein the step of transforming the error locator polynomial into .theta.(y) includes:
i. changing variable to x=y+r, where ##EQU47## 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.sup.2 +.sigma..sub.1 r+.sigma..sub.0 =0
ii. substituting ##EQU48## 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: ##EQU49## which expands to
.theta.(y)=y.sup.4 +.theta..sub.2 y.sup.2 +.theta..sub.1 y+.theta..sub.2 =0
where ##EQU50##

### Claim 4

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.

### Claim 5 (depends on 4)

The method of claim 4, wherein the step of determining the values of t,u, v and w includes the steps of:
i. equating the coefficients of the polynomials of steps a and b:
t+v=O
t*v+u+w=.theta..sub.2
t*w+v*u=.theta..sub.1
u*w=.theta..sub.0 ;
ii determining an equation with t as the only unknown:
t.sup.3 +.theta..sub.2 t+.theta..sub.1 =O
iii. solving for a root t.sub.0 ;
iv. 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 =O
v. solving for the roots p.sub.0 and p.sub.1, which are u and w.

### Claim 6 (depends on 5)

The method of claim 5, wherein the step of solving for a root of t.sup.3 +.theta..sub.2 t+.theta..sub.1 =O includes:
a. changing variabel to ##EQU55## where a=.theta..sub.2, to produce an equation of the form ##EQU56## b. multiplying the equation of step a by z.sup.3 to obtain a quadratic equation with z.sup.3 as the variable:
(z.sup.3).sup.2 +.theta..sub.1 Z.sup.3 +a.sup.3 =O;
c. solving the quadratic equation of step b for z.sup.3 ;
d. determining the cube root, z.sub.0, of z.sup.3 ; and
e. substituting the value of z.sub.0 into the expression ##EQU57##