A pipelined architecture for the multidimensional DFT

This paper presents an efficient pipelined architecture for the N ^m-point m-dimensional discrete Fourier transform (DFT). By using a two-level index mapping scheme that is different from the conventional decimation-in-time (DIT) or decimation-infrequency (DIF) algorithms, the conventional pipelined architecture for the one-dimensional (1-D) fast Fourier transform (FFT) can be efficiently used for the computation of higher dimensional DFTs. Compared with systolic architectures, the proposed scheme is area-efficient since the computational elements (CEs) use the minimum number of multipliers, and the number of CEs increases only linearly with respect to the dimension m. It can be easily extended to the N^m-point m-dimensional DFT with large m and/or N, and it is more flexible since the throughput can be easily varied to accommodate various area/throughput requirements