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

Abstract

In this brief, we present a fast algorithm for computing length- q×2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> discrete Fourier transforms (DFT). The algorithm divides a DFT of size- N = q×2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> and length- q sub-DFTs. Compared with the related algorithms, a substantial reduction of arithmetic complexity and more accurate precision are obtained.