Arithmetic Complexity of the Split-Radix FFT Algorithms
Saad Bouguezel, M. Omair Ahmad, M.N.S. Swamy · 2006
A radix-2/16 decimation-in-frequency (DIF) fast Fourier transform (FFT) algorithm and its higher radix version, namely radix-4/16 DIF FFT algorithm, are proposed by suitably mixing the radix-2, radix-4 and radix-16 index maps, and combing some of the twiddle factors. It is shown that the proposed algorithms and the existing radix-2/4 and radix-2/8 FFT algorithms require exactly the same number of arithmetic operations (multiplications+additions). Moreover, by using techniques similar to these, it can be shown that all the possible split-radix FFT algorithms of the type radix-2/sup r//2/sup rs/ for computing a 2/sup m/-point DFT require exactly the same number of arithmetic operations.