A Fast Algorithm With Less Operations for Length-N = q x 2(m) DFTs

作者：Li, Kenli; Zheng, Weihua; Li, Keqin

来源：IEEE Transactions on Signal Processing, 2015, 63(3): 673-683.

DOI：10.1109/TSP.2014.2379678

• Fast Fourier transform (FFT)
• inverse DFT (IDFT)
• quantization error
• radix-2/8 FFT
• scaled DFT (SDFT)

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 x 2(m) DFTs. The algorithm transforms all q-points sub-DFTs into three parts. In the second part, the operations of sub-transformation contain only multiplications by real constant factors. By transformation, length-2(m)-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 x 2(m) IDFT by 2N - 4m real multiplications. In addition, the proposed algorithm is applied to real-data FFT, and is extended to 6(m) DFTs.

• 出版日期2015-2-1
• 单位湖南大学