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

给出了频域抽取(DIF)多维向量基快速傅里叶变换(FFT)算法。对多维频域信号的每一维，采用向量基2频域抽取法，导出了快速算法蝶形运算的一般形式。该FFT算法适合于维数为任意整数的情况，当维数为1时，算法退化为著名的频域抽取向量基2 FFT算法。为了便于编程实现，以频域抽取3维向量基FFT算法为例，给出了快速算法实现流程，该流程易于向任意整数维推广。计算量比较结果显示，频域抽取多维向量基FFT算法比多维分离式FFT算法计算量低。

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

A multi-dimensional vector radix Fast Fourier Transform (FFT) 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 FFT algorithm was obtained. This FFT 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.