A General Class of Split-Radix FFT Algorithms for the Computation of the DFT of Length-$2^{m}$
- 23 July 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 55 (8) , 4127-4138
Abstract
In this paper, a general class of split-radix fast Fourier transform (FFT) algorithms for computing the length-2 m DFT 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/2 s FFT 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/2 s FFT algorithm is independent of s and is (2m-3)2 m+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-2 m DFT with the same arithmetic complexity.Keywords
This publication has 26 references indexed in Scilit:
- Bit reverse unscrambling for a radix-2>sup/sup<FFT2005
- A radix-16 FFT algorithm suitable for multiply-add instruction based on Goedecker method2003
- Extendible look-up table of twiddle factors and radix-8 based fast Fourier transformSignal Processing, 2002
- Vector computation of the discrete Fourier transformIEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1998
- Implementation of "Split-radix" FFT algorithms for complex, real, and real-symmetric dataIEEE Transactions on Acoustics, Speech, and Signal Processing, 1986
- On computing the split-radix FFTIEEE Transactions on Acoustics, Speech, and Signal Processing, 1986
- Simple FFT and DCT algorithms with reduced number of operationsSignal Processing, 1984
- Recursive cyclotomic factorization--A new algorithm for calculating the discrete Fourier transformIEEE Transactions on Acoustics, Speech, and Signal Processing, 1984
- ‘Split radix’ FFT algorithmElectronics Letters, 1984
- An economical method for calculating the discrete Fourier transform1968