Chien's search

From Wikipedia, the free encyclopedia

You have new messages (last change).

Chien's search is a systematic way of finding roots to polynomials defined over a finite field. Chien's search is used specifically in finding the roots of error locator polynomials, encountered in decoding, of the Reed-Solomon codes and BCH codes. Chien's search would follow a Peterson's error locator, or a Berlekamp's error locator algorithm.

More generally Chien's Search is an exhaustive, brute force method to find solutions to the roots of a polynomial defined over finite fields of form GF(q) or GF(pm)

[edit] Algorithm

If we denote the polynomial by

\Lambda(x) = 1 + \Lambda_1 x + \Lambda_2 x^2 + \Lambda_3 x^3 \ldots + \Lambda_t x^t,

and we are interested in determining the roots of this polynomial.

Since the polynomial is defined over a finite field, with a primitive element α then we show that if order of field is n, α − i = αn − i. Using this fact, if αi is a root of the polynomial, then we may write \Lambda{(\alpha^{i})} = 1 + \Lambda_1\alpha + \Lambda_2\alpha^2 + \ldots + \Lambda_t \alpha^t


So following the steps, we may calculate the roots,

  • For each power of α in range j=0 \ldots n-1 use αj as our test root.
  • Calculate the polynomial coefficients, at the current root using, coefficients of the past iteration, using, \Lambda_i^{(j)} = \Lambda_i^{(j-1)} \alpha^i during the jth iteration.


  • Calculate the sum of the polynomial coefficients, and if

the sum is equal to 0, \sum_{i=1}^{t} \Lambda_i^{j} = 0 then save α − j as a root.

  • Continue to next iteration.

[edit] Computational Advantage

The Chien's search algorithm, is used to locate the roots, of the polynomials, and implemented in hardware, for decoding BCH codes. So, instead of evaluating the polynomial for every root, we make use of the property, that roots, are going to be powers of α. Hence computational advantage, is the following step, \Lambda_i^{(j)} = \Lambda_i^{(j-1)} \alpha^i This makes chien's search better than brute-force method, in terms of implementation, and computational complexity.

[edit] 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.
Retrieved from "http://en.wikipedia.org../../../c/h/i/Chien%27s_search.html"