频域抽取多维向量基快速傅里叶变换  

Multi-dimensional vector radix fast Fourier transform with decimation in frequency domain

作　　者：徐妮妮[1] 于海艳[1] 肖志涛[1] 

机构地区：[1]天津工业大学信息与通信工程学院,天津300160

出　　处：《计算机应用》2010年第10期2777-2780,2818,共5页journal of Computer Applications

基　　金：国家青年自然科学基金资助项目(60602036);国家自然科学基金资助(20676100);天津工业大学校基金资助项目(029470)

摘　　要：给出了频域抽取(DIF)多维向量基快速傅里叶变换(FFT)算法。对多维频域信号的每一维,采用向量基2频域抽取法,导出了快速算法蝶形运算的一般形式。该FFT算法适合于维数为任意整数的情况,当维数为1时,算法退化为著名的频域抽取向量基2FFT算法。为了便于编程实现,以频域抽取3维向量基FFT算法为例,给出了快速算法实现流程,该流程易于向任意整数维推广。计算量比较结果显示,频域抽取多维向量基FFT算法比多维分离式FFT算法计算量低。A multi-dimensional vector radix Fast Fourier Transform （FRY） algorithm with Decimation In Frequency （DIF） was proposed. Using vector radix 2 DIF for each dimension of the multi-dimensional frequency domain signal, the general form of butterfly computation of the FFY algorithm was obtained. This FFr algorithm can be used with arbitrary integer dimensions. For 1-dimension, the algorithm will be simplified as the well-known DIF vector radix 2 FFT. To facilitate the programming, flow chart with DIF 3-dimension vector radix FFT was given. And this flow chart can be extended to any integer dimensions easily. The comparison results show that, compared with multi-dimensional separable FFT, the DIF multi- dimensional vector radix FFT algorithm has lower calculation load.

关 键 词：多维离散傅里叶变换 频域抽取 多维向量基 快速傅里叶变换 多维分离式FFT算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]