Faster than the FFT: The chirp-z RAG-n Discrete Fast Fourier Transform

摘要

DFT and FFTs are important but resource intensive building blocks and have found many application in communication systems ranging from fast convolution to coding of OFDM signals. It has recently be shown that the n-Dimensional Reduced Adder Graph (RAG-n) technique is beneficially in many applications such as FIR or IIR filters, where multiplier can be grouped in multiplier blocks. This paper explores how the RAG-n technique can be applied to DFT algorithms. A RAG-n fast discrete Fourier transform will be shown to be of low latency and complexity and posses a VLSI attractive regular data flow when implemented with the Bluestein chirp-z algorithm. VHDL code synthesis results for Xilinx Virtex Ⅱ FPGAs are provided and demonstrate the superior properties when compared with Xilinx FFT IP cores.