A Fast Algorithm With Less Operations for Length- DFTs
Kenli Li, Weihua Zheng, Keqin Li · 2015
Discrete Fourier transform (DFT)iswidelyusedinal- most 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- DFTs. The algorithm transforms all -points sub- DFTs into three parts. In the second part, the operations of sub- transformation contain only multiplications by real constant fac- tors. By transformation, length- -scaled DFTs (SDFT) are ob- tained. An extension of scaled radix-2/8 FFT (SR28FFT) is pre- sented for computing these SDFTs, in which, the real constant fac- tors of SDFTs are attached to the coefficients of sub-DFTs to sim- plify multiplication operations. The proposed algorithm achieves reduction of arithmetic complexity over the related algorithms. It can achieve a further reduction of arithmetic complexity for com- puting a length- IDFT by