A General Class of Split-Radix FFT Algorithms for the Computation of the DFT of Length-$2^{m}$
Saad Bouguezel, M. Omair Ahmad, M.N.S. Swamy · IEEE Transactions on Signal Processing · 2007
In this paper, a general class of split-radix fast Fourier transform (FFT) algorithms for computing the length-2mDFT is proposed by introducing a new recursive approach coupled with an efficient method for combining the twiddle factors. This enables the development of higher split-radix FFT algorithms from lower split-radix FFT algorithms without any increase in the arithmetic complexity. Specifically, an arbitrary radix-2/2sFFT algorithm for any value of s, 4les sles m, is proposed and its arithmetic complexity analyzed. It is shown that the number of arithmetic operations (multiplications plus additions) required by the proposed radix-2/2sFFT algorithm is independent of s and is (2m-3)2m+1+8 regardless of whether a complex multiplication is carried out using four multiplications and two additions or three multiplications and three additions. This paper thus provides a variety of choices and ways for computing the length-2mDFT with the same arithmetic complexity.