NEW TECHNIQUES FOR DECODING THE BCH ERROR-CORRECTING CODES

VICTOR PAN

Abstract. 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 ≤ c ≤ n; the algorithms use Las Vegas type randomization in the case of 2 < c ≤ n.