一种基于矢量基2×2的二维FFT高效结构

An Efficient Architecture of Vector-Radix 2×2 Two Dimensional Fast Fourier Transform

提出了一种基于时间抽取原位计算的高效并行的二维矢量基2×2快速傅里叶变换的硬件实现结构.该算法结构将N×N点数据分解为4个独立存储的部分来实现矢量基2×2蝶形计算单元4个操作数的并行访问,仅用一个二维分裂基蝶形运算单元对这4块数据进行二维矢量基快速傅里叶变换,利用无冲突访问方法完成对存储器的并行访问.推导出了该算法硬件实现结构下的各存储器数据地址存取公式和旋转因子的产生方法,并利用CORDIC算法实现旋转因子的产生来减少存储器的使用.该算法对N×N点数据进行二维离散傅里叶变换处理的时间仅为(N2/2)(lb N-1)个时钟周期,与以往算法计算时间的比较结果表明了该设计的有效性.

An efficient architecture of vector radix 2 × 2 （VR2 ×2） two dimensional fast Fourier transform （2D-FFT） algorithm for hardware implementation is presented using decimation-in- time. The data of N×N points were divided into four parts to allow simultaneous access to four data needed by the unit of VR2×2 butterfly. The memory assignment was in-place to minimize the memory size, and the access of conflict free allowed four memory banks to be accessed simultaneously. The data address generation algorithms were proposed. The coordinated rotation digital computer （CORDIC） algorithm was used to generate the twiddle factors to save the memories. For data of N × N points, the proposed architecture only costs （N^2/2）（1b N -1） clock periods to complete the two dimensional DFT transform. The comparison of computing time with that needed by other methods shows the effectiveness of the new architecture.