Easy generation of small-Ndiscrete Fourier transform algorithms
Ryszard Stasiński · IEE Proceedings G (Electronic Circuits and Systems) · 1986
In the paper, a set of rules is provided that allow construction of a wide range of efficient Rader's discrete Fourier transform (DFT) algorithms for the sizes of N being (a power of) an odd prime, having a limited set of polynomial reduction, multiplication and reconstruction algorithms. In theory, the algorithms obtained meet the lower bound on the number of multiplications. In practice, they have the same performance as the existing ones, and some new interesting algorithms are obtained, in particular for N = 25 and 27. For N being a power of 2, the use of the radix-4/2 fast Fourier transform is proposed, as this algorithm exhibits excellent properties when used as a small-N DFT algorithm. The paper contains two results of more general application: a rule determining when to use nesting or row-column algorithms, and propositions of new bounds on the number of multiplications for DFT algorithms for N = Pr, where p is a prime number.