在图像处理、物理学等领域，经常遇到多维离散傅立叶变换（DFT）问题。除快速傅立叶变换算法（FFT）外，目前人们已提出许多其他的有效求解算法，如向量基（VR）算法、多项式变换算法、分裂向量基（SVR）算法等。这些算法可显著减少计算复杂性，但FFT由于编码结构简单，成为其中最流行的算法。目前研究热点集中于编码技术而非算法本身。

 

通过扩展整数二进制编码至多维积分点情形，然后基于多维积分点的矢量编码，可设计新的求解多维DFT的矢量编码（VC）算法，如基-2VC算法、基-16VC算法等。对于向量集（N为向量的长度，m为维数）上的基-2 VC算法，递归次数为，加法运算次数为，最多需要次乘法运算。

 

在不增加加法运算次数的情况下，该算法和VR等算法相比，大幅度减少了乘法运算和递归的次数，也节省了数据存取的时间。另外，该算法更适合于并行实现。VR、SVR等一维FFT算法也可通过VC方法扩展至多维的情形。数值算例表明，矢量编码VC算法在实际求解DFT问题时是高效的。

 

原文链接：http://www.sciencedirect.com/science/journal/03770427（常红旭/编译）