In abstract algebra, the '''Chien search''', named after Robert Tienwen Chien, is a fast algorithm for determining roots of polynomials defined over a finite field. Chien search is commonly used to find the roots of error-locator polynomials encountered in decoding Reed-Solomon codes and BCH codes.
==Algorithm== The problem is to find the roots of the polynomial {{math|Λ(''x'')}} (over the finite field {{math|GF(''q'')}}): <math display="block"> \Lambda(x) = \lambda_0 + \lambda_1 x + \lambda_2 x^2 + \cdots + \lambda_t x^t </math>
The roots may be found using brute force: there are a finite number of {{mvar|x}}, so the polynomial can be evaluated for each element {{math|''x''<sub>''i''</sub>}}. If the polynomial evaluates to zero, then that element is a root.
For the trivial case {{math|1=''x'' = 0}}, only the coefficient {{math|''λ''<sub>0</sub>}} need be tested for zero. Below, the only concern will be for non-zero {{math|''x''<sub>''i''</sub>}}.<!-- Error location poly has only nonzero roots: α<sup>i</sup>, so decoder is not interested in the x=0 case. -->
A straightforward evaluation of the polynomial involves {{math|''O''(''t''<sup>2</sup>)}} general multiplications and {{math|''O''(''t'')}} additions. A more efficient scheme would use Horner's method for {{math|''O''(''t'')}} general multiplications and {{math|''O''(''t'')}} 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 {{math|α}}. Chien tests the elements in the generator's order {{math|α<sup>1</sup>, α<sup>2</sup>, α<sup>3</sup>, ....}}. Consequently, Chien search needs only {{math|''O''(''t'')}} multiplications by constants and {{math|''O''(''t'')}} additions. The multiplications by constants are less complex than general multiplications.<!-- There's more cleverness here; the polynomial is not known at compile time but alpha is known. Multiply by alpha is trivial. Constant multiplies may simplify with cancellation. -->
The Chien search is based on two observations:
* Each non-zero <math>\beta</math> may be expressed as <math>\alpha^{i_\beta}</math> for some <math>i_\beta</math>, where <math>\alpha</math> is a primitive element of <math>\mathrm{GF}(q)</math>, <math>i_\beta</math> is the power number of primitive element <math>\alpha</math>. Thus the powers <math>\alpha^i</math> for <math>0 \leq i < (q-1)</math> cover the entire field (excluding the zero element). * The following relationship exists:<math display="block"> \begin{array}{lllllllllll} \Lambda(\alpha^i) &=& \lambda_0 &+& \lambda_1 (\alpha^i) &+& \lambda_2 (\alpha^i)^2 &+& \cdots &+& \lambda_t (\alpha^i)^t \\ &\triangleq& \gamma_{0,i} &+& \gamma_{1,i} &+& \gamma_{2,i} &+& \cdots &+& \gamma_{t,i} \\ \Lambda(\alpha^{i+1}) &=& \lambda_0 &+& \lambda_1 (\alpha^{i+1}) &+& \lambda_2 (\alpha^{i+1})^2 &+& \cdots &+& \lambda_t (\alpha^{i+1})^t \\ &=& \lambda_0 &+& \lambda_1 (\alpha^i)\,\alpha &+& \lambda_2 (\alpha^i)^2\,\alpha^2 &+& \cdots &+& \lambda_t (\alpha^i)^t\,\alpha^t \\ &=& \gamma_{0,i} &+& \gamma_{1,i}\,\alpha &+& \gamma_{2,i}\,\alpha^2 &+& \cdots &+& \gamma_{t,i}\,\alpha^t \\ &\triangleq& \gamma_{0,i+1} &+& \gamma_{1,i+1} &+& \gamma_{2,i+1} &+& \cdots &+& \gamma_{t,i+1} \end{array} </math>
In other words, we may define each <math>\Lambda(\alpha^i)</math> as the sum of a set of terms <math>\{\gamma_{j,i} \mid 0\leq j \leq t\}</math>, from which the next set of coefficients may be derived thus: <math display="block"> \gamma_{j,i+1} = \gamma_{j,i}\,\alpha^j</math>
In this way, we may start at <math>i = 0</math> with <math>\gamma_{j,0} = \lambda_j</math>, and iterate through each value of <math>i</math> up to <math>(q-1)</math>. If at any stage the resultant summation is zero, i.e. <math display="block"> \sum_{j=0}^t \gamma_{j,i} = 0,</math> then <math>\Lambda(\alpha^i) = 0</math> also, so <math>\alpha^i</math> 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 |first= R. T. |last= Chien |title= Cyclic Decoding Procedures for the Bose-Chaudhuri-Hocquenghem Codes |journal= IEEE Transactions on Information Theory |volume= IT-10 |issue= 4 |pages=357–363 |date= October 1964 |issn= 0018-9448 |doi=10.1109/TIT.1964.1053699}} *{{Citation |first= Shu |last= Lin |first2= Daniel J. |last2= Costello |title= Error Control Coding: Fundamentals and Applications |edition=second |publisher= Prentice-Hall |location= Englewood Cliffs, NJ |year= 2004 |isbn= 978-0130426727 }} *{{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 }}
Category:Error detection and correction Category:Finite fields