EVALUATION OF POLYNOMIALS OVER FINITE FIELDS AND DECODING OF CYCLIC CODES

摘要

An apparatus and method are disclosed for evaluating an input polynomial (p(x)) in a (possibly trivial) extension of the finite field of its coefficients, which are useful in applications such as syndrome evaluation in the decoding of cyclic codes. The apparatus comprises a decomposition/evaluation module (110) configured to iteratively decompose the input polynomial into sums of powers of the variable x, multiplied by powers of transformed polynomials, wherein each transformed polynomial has a reduced degree as compared to the input polynomial, and to evaluate the decomposed input polynomial. In another aspect, an apparatus and method of identifying errors in a data string based in a cyclic code are disclosed, which employ the Cantor-Zassenhaus algorithm for finding the roots of the error-locator polynomial, and which employ Shank's algorithm for computing the error locations from these roots.