Faster than the FFT: The chirp-z RAG-n Discrete Fast Fourier Transform
Uwe H. Meyer-Baese, Hariharan Natarajan, Encarnación Castillo, Antonio García · Frequenz · 2006
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 II FPGAs are provided and demonstrate the superior properties when compared with Xilinx FFT IP cores. Index Terms – Fast Fourier Transform, OFDM, FPGA, n-Dimensional Reduced Adder Graph