A VLSI-oriented FFT algorithm and its pipelined design

This paper presents a novel FFT algorithm based on a multi-dimensional index mapping method. Twiddle factor multiplications are decomposed in a divide and conquer approach to minimize the number of multipliers and remain the simpleness of the butterfly computation. And canonic signed digit representation is applied to constant multiplications introduced from the decomposition. By exploiting the symmetry of twiddle factors, the algorithm also reduces the memory requirement for twiddle factors. These characteristics make the proposed algorithm suitable for long size FFT VLSI implementation. Based on the algorithm we propose an efficient pipeline FFT architecture and implement a 1024-point FFT processor by 0.18 um CMOS technology.