System for finding roots of degree three and degree four error locator polynomials over gf(2m)

Abstract

A system determines the locations of four errors in a code word over GF(2,), for any m, by transforming a degree-four error locator polynomial &sgr;(x) ultimately into two quadratic equations, finding the solutions of these equations, and from these solutions determining the roots of the error locator polynomial. The system first manipulates the degree-four error locator polynomial into a polynomial &thgr;(y) that has a coefficient of zero for the degree-three term. The system then factors this polynomial into two degree-two factors with four unknown variables. The system expands the factors and represents the coefficients of &thgr;(y) as expressions that include the four unknown variables, and manipulates the expressions to produce a degree-three polynomial with only one of the unknown variables. The system next solves for that variable by finding a root of the degree-three polynomial in GF(2,) if the field is an even-bit field or in an even-bit extension of GF(2,) if the field is an odd-bit field. The system then substitutes the root into the expressions for the coefficients of &thgr;(y) and produces a degree-two expression is with the remaining unknown variables. The system finds the roots of this expression, substitutes these values into the factors of&thgr;(y), and sets the factors equal to zero to produce two quadratic equations. The system then solves the equations to produce the roots of&thgr;(y), and from these solutions determines the roots of the degree-four error locator polynomial.