A Fast Algorithm Based on SRFFT for Length $N = qtimes 2^{m}$ DFTs

摘要

In this brief, we present a fast algorithm for computing length-$qtimes 2^{m}$ discrete Fourier transforms (DFT). The algorithm divides a DFT of size- $N = qtimes 2^{m}$ decimation in frequency into one length- $N/2$ DFT and two length-$N/4$ DFTs. The length-$N/2$ sub-DFT is recursively decomposed decimation in frequency, and the two size-$N/4$ sub-DFTs are transformed into two dimension and the terms with the same rotating factor are arranged in a column. Thus, the scaled DFTs (SDFTs) are obtained, simplifying the real multiplications of the proposed algorithm. A further improvement can be achieved by the application of radix-2/8, modified split-radix FFT (MSRFFT), and Wang's algorithm for computing its length-$2^{m}$ and length- $q$ sub-DFTs. Compared with the related algorithms, a substantial reduction of arithmetic complexity and more accurate precision are obtained.