Chien's search 
by Wikipedia editor/administrator Olifilth
a.k.a
This e-mail address is being protected from spam bots, you need JavaScript enabled to view it
(nonworking)
Oli Filth
Oliver Charlesworth
8 Moncrieff Close - 2nd floor
Cambridge CB4 2UY United Kingdom (UK)
auto: AF03 BXL
Contact Author: Oli Filth Olifilth
phone: (01223) 696552
From the US:
01144 (1223) 696552
Oliver Charlesworth
British Telephone Company
Olifilth Oli Filth Wikipedia Wiki
Introduction
In abstract algebra, Chien's search is a recursive algorithm
for determining roots of polynomials defined over a finite field.
The most typical use of Chien's search is in finding the roots of
error-locator polynomials encountered in decoding
Reed-Solomon codes and BCH codes.
Algorithm
We denote the polynomial whose roots we wish to determine as
Conceptually, we may evaluate  for each
non-zero  in our finite field GF(q).
Those resulting in 0 are roots of the polynomial.
Chien's search is based on two observations:
- Each non-zero may be expressed as
 for some 
- where
 is the primitive element of GF(q).
-
- Therefore, 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
- R.T. Chien, "Cyclic Decoding Procedure for the
- Bose-Chaudhuri-Hocquenghem Codes,"
- IEEE Transactions on Information Theory,
- Vol. IT-10, pp. 357-363, October 1964.
-
- S. Lin and D. Costello. Error Control Coding:
- Fundamentals and Applications.
- Prentice-Hall, Englewood Cliffs, NJ, 2004.
|
