A new pipelined implementation of the fast Fourier transform

This paper presents a new pipelined architecture for the N/sup m/-point FFT (Fast Fourier Transform). Unlike conventional pipelined architectures, which are based on the DIT (Decimation in Time) or DIF (Decimation in Frequency) algorithms, the proposed architecture is based on a new index mapping scheme which has two levels of decomposition. As a result, the new architecture can be efficiently used to realize a pipelined implementation of the N/sup m/-point m-dimensional DFT simply by omitting some of the twiddle factor ROMs.