可见，离散傅立叶变换虽然是最直接的确定时域序列频率成分的方法，但是在计算机处理过程中，它的运算效率低，无法适用于实时问题的处理，因而并没有在实践中得到广泛的应用。这一状况一直到1965年才得到改善，当年，Cooley与Turkey就离散傅立叶变换的高速算法发表了一篇文章[3]。在文章中，他们提出了DFT的快速算法——快速傅立叶变换（FFT）。FFT算法的提出，大幅减少了DFT的运算量，提高了离散傅立叶变换的运算效率。此后，DFT与FFT在实践与应用中得到推广，开始在各个领域大放异彩。

在Cooley与Turkey之后，很多人开始从事进一步降低DFT运算量，提高DFT运算效率的快速算法的研究。包括滑动DFT算法[4]-[5]，FFT Pruning算法[6]等算法相继被提出。滑动DFT利用连续时刻滑动窗中样本的相似性进行递推，利用前窗的结果参与计算，减少了DFT的运算量。FFT Pruning算法则考虑了这样一种情形——当输入、输出端存在大量的零值时，蝶形运算中进行的许多运算是不必要且浪费时间的。针对这样的状况，通过去除传统FFT算法的蝶形运算路径中的无效路径，FFT Pruning算法大幅的减少了这类仅含少数非零点的特殊序列的FFT的运算量，从而提高了运算效率。

我们假设滑动窗的窗口长度为N，窗口滑动步距为p，当滑动窗在移动N点后, 采用传统的FFT算法的计算量为 。可见，在滑动窗的窗口长度较大并且窗口滑动步距较小的情况下，传统的FFT算法由于运算量相对来说很大，无法完成数据的实时处理，不能满足对实时性需求比较高的系统的要求[7]。

针对这样的情况，李文忠等人[8]提出了滑动FFT递推算法，在多点滑动DFT算法的基础上，对局部序列运用FFT Pruning算法进行优化，充分利用了前窗计算结果并去除了蝶形运算中的无效路径，大大减少了计算量，提高了使用的灵活性。本文对该算法进行了仔细的分析研究，并通过MATLAB对该算法的效果进行了验证。

1.2  论文主要工作

本文主要工作是对指定的文献进行仔细的分析研究，并查阅相关文献加深理解，对文献[提出的滑动FFT递推算法用MATLAB进行仿真检验其效果。本文以对滑动FFT递推算法的研究过程为主线组织全文。本文一共有三章，分别对研究背景、相关算法的介绍、滑动FFT递推算法的推导、MATLAB验证等方面进行了探讨，具体的组织结构如下：

第一章 介绍了滑动FFT递推算法提出的背景，回顾了DFT与FFT的发展过程，并对其优缺点进行了讨论。

第二章 介绍了与滑动FFT递推算法相关的算法包括FFT算法、滑动DFT算法、FFT Pruning算法等。

第三章 介绍了滑动FFT递推算法的推导过程，并用MATLAB进行仿真，对其效果进行验证验证，对仿真结果进行分析。

第四章 对滑动FFT递推算法以及学习研究的结果进行了总结，得到了关于滑动FFT算法的几点结论。