Reduce FFT memory reference for low power applications

Memory reference is one of the major courses of power consumption incurred in a microprocessor. In this paper, we propose two matrix transformation techniques to reduce the number of memory references in the FFT computation. With the first transformation, all the butterflies sharing the same twiddle factor will be clustered and computed together to eliminate redundant memory access to load twiddle factors. With the second transformation, all remaining (N − 1) butterflies involving the twiddle factor WN⁰ are computed using a register-based breadth-first tree traversal algorithm so that load/store operations of intermediate data arrays are minimized. The proposed two transformations together have led to a novel twiddle-factor-based FFT algorithm. The test results on the TI TMS320C62x digital signal processor show that, for a 32-point FFT, the new algorithm exhibits as much as 20% reduction in clock cycles and an average of 30% reduction in memory access than that of the conventional DIF FFT.