On the Structure of Cyclotomic Fourier Transforms and Their Applications to Reed-Solomon Codes

This paper is focused on cyclotomic Fourier transforms in GF(2^m), and on their applications to algebraic decoding of Reed-Solomon codes, like the evaluation of syndromes and of error locator (or evaluator) polynomials. Cyclotomic transforms are much more efficient than straightforward evaluation. In particular, the number of multiplications is quite small. In this paper it is shown that also the number of additions can be considerably reduced with respect to previous analyses. A simple interpretation of the cyclotomic Fourier transform best suited for the evaluation of syndromes allows to assemble the required matrix easily and quickly, even in large fields. Many equivalent matrices exist. Then, fast construction of such matrices is important to obtain the best results, since as many matrices as possible must be generated and compared. It is shown that also the structure of bilinear convolutions is to be exploited, to reduce complexity. For the costly part of cyclotomic Fourier transforms, which is a matrix-vector product, only heuristic algorithms are available. Since also these algorithms are to be run many and many times to obtain the best transform, execution times are important. It is shown that a very simple and fast heuristic algorithm gives satisfactory results.