A Fast Algorithm With Less Operations for Length-<formula formulatype="inline"><tex Notation="TeX">$N=q\times 2^{m}$</tex></formula> DFTs

Abstract

Discrete Fourier transform (DFT) is widely used in almost all fields of science and engineering. Fast Fourier transform (FFT) is an efficient tool for computing DFT. In this paper, we present a fast Fourier transform (FFT) 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> DFTs. The algorithm transforms all q-points sub-DFTs into three parts. In the second part, the operations of subtransformation contain only multiplications by real constant factors. By transformation, length- 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> -scaled DFTs (SDFT) are obtained. An extension of scaled radix-2/8 FFT (SR28FFT) is presented for computing these SDFTs, in which, the real constant factors of SDFTs are attached to the coefficients of sub-DFTs to simplify multiplication operations. The proposed algorithm achieves reduction of arithmetic complexity over the related algorithms. It can achieve a further reduction of arithmetic complexity for computing a length- N=q×2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> IDFT by 2N-4m real multiplications. In addition, the proposed algorithm is applied to real-data FFT, and is extended to 6 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> DFTs.