A generalized modified split-radix FFT algorithm for N=q×2m and its applications
This paper presents a generalized odd factor modified split-radix-2/4 Fast Fourier transform (FFT) algorithm for computing the DFT of length-N = q×2<sup>m</sup>, where q is a positive odd integer. Compared with former algorithms for N = q×2<sup>m</sup>, the proposed algorithm reduces the computation complexity of DFT from O(4Nlog<sub>2</sub>(N/q)) to O((34/9)Nlog<sub>2</sub>(N/q)) for complex input. The proposed algorithm can be applied to some international wireless standards where the length of DFT is not a power of two, and to some international speech and audio standards where the modified discrete cosine transform (MDCT) with length-N = q×2<sup>m</sup>, q = 5, 15 is used.