System and method for performing a chien search using multiple galois field elements

Abstract

A system for performing a Chien search simultaneously tests multiple elements of GF(2 ) as possible roots of a degree-t error locator polynomial &sgr;(x) using a plurality of simplified multipliers that each simultaneously produce the corresponding terms of &sgr;(x). In one embodiment of the system, t−1 simplified multipliers over GF(2 ) are used to simultaneously test as possible roots &agr; , (&agr; ) , (&agr; ) . . . (&agr; ) . Each multiplier includes a plurality of adders that are set up in accordance with precomputed terms that are based on combinations of the weight-one elements of GF(2 ). A summing circuit adds together the associated terms produced by the multipliers and produces j sums, which are then evaluated to test the j individual elements as possible roots. The coefficients of &sgr;(&agr; ) are then fed back to the multipliers, and the multipliers test, during a next clock cycle, the elements &agr; *(&agr; ) , (&agr; ) *(&agr; ) . . . , (&agr; ) and so forth. Similar multipliers also test the odd powers of &agr; as roots of &sgr;′(x)=&sgr;(&agr;x). If P=mn the system may be implemented using a plurality of GF(2 ) multipliers. The field GF(2 ) is a subfield of GF(2 ), and the elements of GF(2 ) can each be represented by a combination of n elements of GF(2 ). The error locator polynomial &sgr;(x) can thus be represented by a combination of n expressions &sgr; (x), &sgr; (x) . . . &sgr; (x), each with coefficients that are elements of GF(2 ). Each of the n expressions has 2 −1 coefficients for the terms x , x , x . . . x . Thus, n(2 −2) constant GF(2 ) multipliers are used to test each element of GF(2 ) as a possible root. The number of GF(2 ) multipliers in the system is independent of the degree of the error locator polynomial, and each multiplier operates over a subfield of GF(2 ). Accordingly, the system can simultaneously tests j elements using j sets of n(2 −2) constant multipliers over GF(2 ).