Twiddle-factor-based FFT algorithm with reduced memory access
Yingtao Jiang, Ting Zhou, Yiyan Tang, Yuke Wang · 2002
In microprocessor-based systems, memory access is expensive due to longer latency and higher power consumption. In this paper, we present a novel FFT algorithm to reduce the frequency of memory access as well as multiplication operations. For an N-point FFT, we design the FFT with two distinct sections: (1) The first section of the FFT structure computes the butterflies involving twiddle factors WNj(j ≠ 0) through a computation/partitioning scheme similar to the Hoffman coding. In this section, all the butterflies sharing the same twiddle factor will be clustered and computed together. In this way, redundant memory access to load twiddle factors is avoided. (2) In the second section, the remaining (N - 1) butterflies involving the twiddle factor WN0are computed with a register-based breadth first tree traversal algorithm. This novel twiddle factor-based FFT is tested on the TIT MS320C62x digital signal processor. The results show that, for a 32-point FFT, the new algorithm leads to as much as 20% reduction in clock cycles and an average of 30% reduction in memory access than that of the conventional DIF FFT.