A generalized modified split-radix FFT algorithm for N=q×2^m 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, where q is a positive odd integer. Compared with former algorithms for N = q×2, the proposed algorithm reduces the computation complexity of DFT from O(4Nlog(N/q)) to O((34/9)Nlog(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, q = 5, 15 is used.