Fast, prime factor, discrete Fourier transform algorithms over GF(2 m ) for 8⩽ m ⩽10

Abstract: In this paper it is shown that Winograd’s algorithm for computing convolutions and a fast, prime factor, discrete Fourier transform (DFT) algorithm can be modified to compute Fourier-like transforms of long sequences of 2 m −1 points over GF(2 m ), for 8⩽ m ⩽10. These new transform techniques can be used to decode Reed–Solomon (RS) codes of block length 2 m −1. The complexity of this new transform algorithm is reduced substantially from more conventional methods. A computer simulation verifies these new results. [Copyright &y& Elsevier]