Efficient FFT engine with reduced addressing logic

In this study, an efficient address generation method for pipelined Radix-2 fast Fourier transform (FFT) is presented. Conventional pipelined FFT addressing schemes utilize dedicated address generators in order to enable parallel access to the memory units and in-place calculation. These address generator units require substantial hardware logic including counters and rotational shifters to generate the addresses and registers to buffer the outputs of each butterfly operation. In the proposed method, the new parallel addressing scheme utilizes only counters and inverters to generate the addresses; replacing the barrel shifter units and reducing the hardware requirements. In order to replace the barrel shifters, two outputs of the butterfly unit switch places depending on the status of the butterfly pass operation. The only additional hardware unit is extra multiplexers for switching the butterfly outputs. We present the signal flow graph for 8, 16, and 32-point FFT and derive the methodology for 2^r = N-point transforms. Furthermore, as a case study, 16-point FFT with 64-bit complex numbers is synthesized using an FPGA device. The results indicate that approximately 20% logic reduction can be achieved with exactly same throughput.