多维DFT的多维多项式变换与离散W变换算法

本文首先通过引进一种序列的重排技术将m(m2) 维离散Fourier变换 (m-D DFT)转化为一系列的一维广义离散Fourier变换(GDFT)的多重和.然后引入一维离散W变换(DWT)以及多维多项式变换(MD-PT)计算该多重和以减少冗余的算术运算,从而得到了高效的多维DFT算法,该算法与常用的行-列DFT算法相比,乘法仅约为行-列法的1/2m,而加法仅约为行-列法的(2m+1)/4m.对于2维DFT的计算,本文方法同单纯的多项式变换方法相比,乘法与加法分别减少50%与40%左右.另外,本文算法计算结构简单,易于编程实现,通过数值实验验证了本文算法的高效性.

Multidimensional Polynomial Transform and Discrete W Transform Algorithms for Multidimensional DFT

This paper first presents a conversion of the m-dimensional discrete Fourier transform(MD-DFT) into a multiple sum involving a number of one-dimensional generalized discrete Fourier transforms (1D-GDFT's) by reordering the input data.An one-dimensional discrete W transform (DWT) and multidimensional polynomialtransform (MD-PT) are then used to compute the m-D DFT so that the number of arithmetic operations needed is reduced.The number of multiplications and additions required by the proposed algorithm is only 1/2m and (2m+1)／4m times that of the usually used row-column DFT algorithm.Besides,compared with the polynomial transform for 2-D DFT developed by Nussbaumer,the multiplications and additions needed by the proposed algorithm are reduced by 50% and 40%,respectively.The numerical experiments show that the proposed algorithm is not only simple in computational structure and but also highly efficient.