In
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures, which are set (mathematics), sets with specific operation (mathematics), operations acting on their elements. Algebraic structur ...
, the Chien search, named after
Robert Tienwen Chien, is a fast algorithm for determining
root
In vascular plants, the roots are the plant organ, organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often bel ...
s of
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
s defined over a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
. Chien search is commonly used to find the roots of error-locator polynomials encountered in decoding
Reed-Solomon codes and
BCH code
In coding theory, the Bose–Chaudhuri–Hocquenghem codes (BCH codes) form a class of cyclic error-correcting codes that are constructed using polynomials over a finite field (also called a '' Galois field''). BCH codes were invented in ...
s.
Algorithm
The problem is to find the roots of the polynomial (over the finite field ):
The roots may be found using brute force: there are a finite number of , so the polynomial can be evaluated for each element . If the polynomial evaluates to zero, then that element is a root.
For the trivial case , only the coefficient need be tested for zero. Below, the only concern will be for non-zero .
A straightforward evaluation of the polynomial involves general multiplications and additions. A more efficient scheme would use
Horner's method
In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. Although named after William George Horner, this method is much older, as it has been attributed to Joseph-Louis Lagrange by Hor ...
for general multiplications and additions. Both of these approaches may evaluate the elements of the finite field in any order.
Chien search improves upon the above by selecting a specific order for the non-zero elements. In particular, the finite field has a (constant) generator element . Chien tests the elements in the generator's order . Consequently, Chien search needs only multiplications by constants and additions. The multiplications by constants are less complex than general multiplications.
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.
References
*
*
*{{Citation
, last=Gill
, first= John
, date=n.d.
, title= EE387 Notes #7, Handout #28
, access-date= April 21, 2010
, pages=42–45
, publisher= Stanford University
, url= http://www.stanford.edu/class/ee387/handouts/notes7.pdf
, archive-date=2014-06-30
, archive-url=https://web.archive.org/web/20140630172526/http://web.stanford.edu/class/ee387/handouts/notes7.pdf
Error detection and correction
Finite fields