A pipelined architecture for the multidimensional DFT

被引:9
作者
Yu, SW [1 ]
Swartzlander, EE
机构
[1] Intel Corp, Austin, TX 78746 USA
[2] Univ Texas, Dept Elect & Comp Engn, Austin, TX 78712 USA
关键词
discrete Fourier transform; multidimensional transforms; pipelined architecture;
D O I
10.1109/78.942637
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
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.
引用
收藏
页码:2096 / 2102
页数:7
相关论文
共 16 条
[1]   Implementation of the FFT butterfly with redundant arithmetic [J].
Bruguera, JD ;
Lang, T .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-ANALOG AND DIGITAL SIGNAL PROCESSING, 1996, 43 (10) :717-723
[2]   INDEX MAPPINGS FOR MULTIDIMENSIONAL FORMULATION OF DFT AND CONVOLUTION [J].
BURRUS, CS .
IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1977, 25 (03) :239-242
[3]   AN ALGORITHM FOR MACHINE CALCULATION OF COMPLEX FOURIER SERIES [J].
COOLEY, JW ;
TUKEY, JW .
MATHEMATICS OF COMPUTATION, 1965, 19 (90) :297-&
[4]   Pipelined adders [J].
Dadda, L ;
Piuri, V .
IEEE TRANSACTIONS ON COMPUTERS, 1996, 45 (03) :348-356
[5]   VLSI ARCHITECTURES FOR MULTIDIMENSIONAL FOURIER-TRANSFORM PROCESSING [J].
GERTNER, I ;
SHAMASH, M .
IEEE TRANSACTIONS ON COMPUTERS, 1987, 36 (11) :1265-1274
[6]   PARALLELISM IN FAST FOURIER-TRANSFORM HARDWARE [J].
GOLD, B ;
BIALLY, T .
IEEE TRANSACTIONS ON AUDIO AND ELECTROACOUSTICS, 1973, AU21 (01) :5-16
[7]   Multidimensional systolic arrays for the implementation of discrete Fourier transforms [J].
Lim, H ;
Swartzlander, EE .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 1999, 47 (05) :1359-1370
[8]  
LIM HS, 1995, P INT C APPL SPEC AR, P123
[9]  
OPPENHEIM AV, 1978, APPL DIGITAL SIGNAL, pCH5
[10]  
Peng ST, 1997, IEICE T INF SYST, VE80D, P455