Chien Search - Algorithm

Algorithm

We denote the polynomial (over the finite field GF) whose roots we wish to determine as:

Conceptually, we may evaluate for each non-zero in GF. Those resulting in 0 are roots of the polynomial.

The Chien search is based on two observations:

• Each non-zero may be expressed as for some, where is a primitive element of, is the power number of primitive element . Thus the powers for cover the entire field (excluding the zero element).

• The following relationship exists:

In other words, we may define each as the sum of a set of terms, from which the next set of coefficients may be derived thus:

In this way, we may start at with, and iterate through each value of up to . If at any stage the resultant summation is zero, i.e.

then also, so is a root. In this way, we check every element in the field.

When implemented in hardware, this approach significantly reduces the complexity, as all multiplications consist of one variable and one constant, rather than two variables as in the brute-force approach.