多维快速Fourier变换的计算

ALGORITHM FOR MULTI-DIMENSIONAL FAST FOURIER TRANSFORM

本文提出了一个N₁×N₂×…×N_n点组N维离散傅里叶变换的有效高速算法。该算法要求个复数加法和个复数乘法。从本文中,可以看到多维快速傅里叶算法的数据组织和具体算法与一维快速傅里叶算法的数据组织和具体算法与一维快速傅里叶算法是一样的。由于计算结果仍放在原始数据的相应位置,因此,用这样的代换算法,其存储量的要求,只限于原始数据的存储量即可。

An efficient high speed algorithm for computing the N-Dimension-al discrete Fourier transform of an array of N₁×N₂×…×N_n points where N1, N2, ...Nn are all some powers of 2 is described, It requirescomplex multiplications. In the present paper, particular organization of data and the techniques of one dimensional fast Fourier transform are used to obtain multi-dimensional discrete Fourier transforms. Since the computed results can be stored in the same place as the original one’s. Therefore by using this in-place algorithm, its storage requirements are then limited to the original data array only.