DFT 具有线性性质、正交性、移位性质、奇偶虚实对称性质、Parseval 定理和时域循环卷 积等性质。DFT 具有非常广泛的作用，运用 DFT 可以进行计算线性卷积、求解偏微分方程、 分析和处理数字信号及光学成像等。

2。2 DFT 谱的计算方法

计算 DFT 谱的方法不唯一，根据（1）式可以看出，对于求一点的�(�)，总共需要进行N 次复数乘法，对于求出N点的�(�)，则一共需要�2次复数乘法，当N很大时，其计算量也相当

复杂。因此，直接进行计算并不便捷，简化的 DFT 谱计算方法有快速傅里叶变换（fast Fourier

transform，FFT）和递归算法等。

快速傅里叶变换（fast Fourier transform，FFT），它的原理主要是巧妙地运用 W 因子的周 期性和对称性，将 W 矩阵中大量的重复计算简化，从而形成了 FFT 算法。FFT 算法由 Cooley

和 Tukey 在 1965 年提出，其算法能够使 N 点的 DFT 乘法计算量由原有的�2次降为文献综述

2 2

次，有效的简化 DFT 的计算量。

快速傅里叶变换的发展方向主要有两种：一是针对 N 等于 2 的整数次幂的算法，这类算 法利用其序列长度特点，将其进行分组计算，如基 2 算法、基 4 算法和实因子算法等；另一 个是 N 不等于 2 的整数次幂算法，这类算法是以 Winograd 为代表的一类算法[1]，其包括素因 子算法、Winograd 算法等。

基 2 算法是在序列长度 N 的数值为 2 的整数次幂时，将序列分为奇数组合偶数组，也就

是说，人为地将�(�)分成了不同的两个�/2的离散余弦变换（discrete Cosine Transform，DCT） 分别进行计算，最后再进行整合计算，这样简化了 FFT 的计算。基 4 算法的原理基本相似于

基 2 算法，但比基 2 算法进步的是，基 4 算法能够不使用乘法计算，而是只使用加法计算来

实现，也就是说，这种算法比基 2 算法更为有效。分裂基算法的原理是既采用了基 2 算法，

又采用了基 4 算法，其算法的基本思路是，在序列中，对序号为偶数的输出都使用基 2 算法， 对序号为奇数的输出都使用基 4 算法，这种算法被认为是当 N 的数值为 2 的整数次幂时的最 佳算法[5]。

素音子算法主要针对于 N 的数值不为 2 的整数次幂时，将 N 因式分解成若干个数值，然 后在进行计算，可以大大减少计算量。Winograd 算法是以数据寻址理论为基础，进行卷积运 算的一种算法，其复数乘法计算次数，比起 FFT 算法，所需的计算次数少。但是其理论复杂， 控制复杂，数据的长度受到较大的限制，在程序中，数据所占的内存及数据传递次数增多， 导致其优势越来越受到质疑。来`自+优-尔^论:文,网www.youerw.com +QQ752018766-

随着计算机技术和并行技术的发展，为了适应系统需要，在开发计算软件和硬件过程中， 不仅需要降低其计算复杂度，还需要关注系统软件和硬件设计，特别是模块化设计。FFT 算 法的数据传输是全景性质的，因而存在一定的缺点，相比较而言递归计算则灵活许多。而 Goertzel 算法可以减少 DFT 谱的计算量，也能够计算局部频段的谱值，其递归单元也适用于 并行计算。Goertzel 算法被广泛应用于双音多频（dual-tone multi-frequency，DTMF）信号的 检测、滑动 DFT 算法等场合。