On the decoding complexity of cyclic codes up to the BCH bound

The standard algebraic decoding algorithm of cyclic codes [n, k, d] up to the BCH bound δ = 2t + 1 is very efficient and practical for relatively small n while it becomes unpractical for large n as its computational complexity is O(nt). Aim of this paper is to show how to make this algebraic decoding computationally more efficient: in the case of binary codes, for example, the complexity of the syndrome computation drops from O(nt) to O(t√n), while the average complexity of the error location drops from O(nt) to max{O(t√n), O(t log²(t)log log(t)log(n))}.