徐 妍,杨齐琪,余 玲

(北京服装学院 材料科学与工程学院，北京 100029)



基-4高维离散傅立叶变换PM向量编码算法

徐 妍,杨齐琪,余 玲

(北京服装学院 材料科学与工程学院，北京 100029)

离散傅立叶变换是数字信号处理中一种很重要的数学工具，它可以描述离散信号的时域与频域的关系，在数字信号处理中有着重要的地位，应用十分广泛[文献1-3]。本文提出的基-4PM向量编码算法是结合PM算法[文献4]和向量编码算法[文献5-6]创造出的新算法。在采样点数相同的情况下，与现行的几种算法相比，该算法在计算量和运算时间上都有不同程度的降低，从而提高了运算效率。这在实际应用中具有重要的意义。

离散傅立叶变换;行列算法;PM算法;向量编码算法;PM向量编码算法

1 引言

高维离散Fourier变换 (DFT) 的一般形式为

(1)

对高维DFT的计算通常采用行列算法，即将m维DFT化为m个一维DFT计算：

X(a1，a2,…,am)

(2)

对每个一维DFT采用Cooley-Tukey的快速算法计算。行列算法是目前最为常用的计算高维DFT的算法，它的计算效率取决于一维DFT的计算效率。这种算法虽然程序结构较其他算法简单，但就高维DFT变换的特点来说，算法的运算量还是可以进一步减少的。

本文讨论的基-4 PM向量编码算法，是将高维PM离散傅立叶变换的快速算法(Plus-Minus Fast Discrete Fourier Transform Algorithm)与向量编码算法相结合，得到一种新的FFT算法，在采样点数相同的情况下，能够减少执行高维DFT的位码倒序、同址运算和蝶形运算所消耗的时间，与现行的行列算法相比，计算的结构复杂度大大降低，减少了计算量，从而有效的提高了算法的运算效率。……