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

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

给出了频域抽取(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.