Automatic generation of parallelized FFT logic for implementation in FPGA chips

This paper considers the automatic generation of parallelized fast-Fourier-transform (FFT) logic for field-programmable gate-array (FPGA) chips. A custom software tool has been created to generate VHDL logic descriptions for parallelized radix-4 FFT architectures using decimation-in-frequency (DIF). These architectures accept N simultaneously-provided fixed-point complex-valued input samples every cycle for applications that demand high throughput. Two approaches are described for generating the product terms in complex multiplications involving twiddle constants: standard single-cycle multiplication, and multi-cycle shift-and-add multiplication. Synthesis results are reported for parallelized FFT implementations of different sizes targeting low-cost Cyclone III chips and high-end Stratix III and IV chips from Altera. The shift-and-add approach for constant multiplication is shown to consume more logic resources, but provide a higher maximum clock frequency.