New Techniques for Decoding the BCH Error-Correcting Codes
Victor Pan
The coefficients of a polynomial of a degree $n$ can be expressed via the power sums of its zeros by means of a polynomial equation known as the key equation for decoding the BCH error-correcting codes. Berlekamp's algorithm of 1968 solves this equation by using order of $n^2$ operations in a fixed field. Several algorithms of 1975-1980 rely on the extended Euclidean algorithm and computing Padé approximation, which yields solution in $O( n (\log n)^2 \log \log n)$ operations, though a considerable overhead constant is hidden in the "$O$" notation. We show algorithms (depending on the characteristic $c$ of the ground field of the allowed constants) that simplify the solution and lead to further improvements of the latter bound, by factors ranging from order of $\log n$, for $c=0$ and $c>n$ (in which case the overhead constant drops dramatically), to order of $\min(c,\log n)$, for $2 \le c \le n$; the algorithms use Las Vegas type randomization in the case of $2 < c\le n$.