Scaled Radix-2/8 Algorithm for Efficient Computation of Length-$N=2^{m}$ DFTs

摘要

This paper presents a scaled radix-2/8 fast Fourier transform (FFT) (SR28FFT) algorithm for computing length-$N=2^{m}$ discrete Fourier transforms (DFTs) scaled by complex number rotating factors. The idea of the SR28FFT algorithm is from the modified split radix FFT (MSRFFT) algorithm, and its purpose is to furnish other algorithms with high efficiency but without shortcomings of the MSRFFT algorithm. A novel radix-2/4 FFT (NR24FFT) algorithm and a novel radix-2/8 FFT (NR28FFT) algorithm are proposed. These two algorithms use SR28FFT to calculate their sub-DFTs of odd-indexed terms. Several aspects of the two algorithms such as computational complexity, computation accuracy, and coefficient evaluations or accesses to the lookup table all are improved. The bit-reverse method can be used for their order permutation and no extra memory is required to store their extra coefficients by the two novel algorithms, which contribute significantly to the performance of the FFT algorithms. The SR28FFT algorithm can also be applied to other algorithms whose decomposition contains sub-DFTs of powers-of-two. The Appendix presents an algorithm named SR28FFT-2 for further reducing the number of arithmetic operations, and NR24FFT and NR28FFT algorithms based on SR28FFT-2 requires fewer real operations than that required by the MSRFFT algorithm.