第一章是文章的绪论，对本课题的研究背景以及意义作了介绍，并且简单说明了的历史发展与研究意义，最后对本文的流程安排进行了简单的描述。

第二章介绍了算法的原理。首先简单介绍了算法的原理，进而推导出共轭对称序列的DFT所具有的特殊性质。然后讨论算法的原理，其中主要介绍了基2算法，并且就按时间抽取，按频率抽取，这三种算法进行了分析，比较各自的特点，再结合课题最终确定要使用的方法。通过给出蝶形流图等的方法对这几种的原理有了一个比较直观的理解，最后也给出了几种算法在运算次数、分解级数等方面的特点的描述。

第三章给出了共轭对称数据的算法的原理，从分析其基础蝶形出发，给出一系列相关公式、通式的推导，再通过对蝶形流图的观察，再从每一级的输入输出数据以及蝶形的结构特点出发，采用由特殊到一般的方法，先选取几个特殊的数据，来确定循环内部的一般变量的计算、赋值，以及数组下标通式的，算法程序循环的构成等等。然后分析该改进算法，发现重新安排蝶形和输入数据可以进一步优化，此时实现原位运算是通过合并蝶形运算。而重新排布之后输入数据全是实数这一特殊性，使得该算法比前一算法节省一半存储空间并且减少部分复数乘法运算，算法进一步得到优化。为之后的程序的编写做了铺垫。

第四章为运行程序部分，这一章首先在理论上就两种改进算法的推导过程分析各自需要计算的复数乘法次数，再与传统的算法进行比较。然后给出了在MATLAB中运行两个改进FFT算法的具体步骤以及运行后的结果与MATLAB中自带的FFT算法比较结果验证其正确性，并且使用tic和toc语句分别导出运行时间再对比，验证两种改进算法的优越性。最后再根据其他两种特殊输入序列，对算法进行了修改拓展。来:自[优.尔]论,文-网www.youerw.com +QQ752018766-

2  FFT算法原理

2。1  离散傅里叶变换

对于序列x(n), n = 0，1，。。。，N −1的离散傅立叶变换 X(k), k = 0。。。N −1 的定义式可写成：

                （2。1。1）

式中，被称为旋转因子。

反离散傅立叶（）的定义式可写成: 

                （2。1。2）

式中，

注意到，以及的输入输出均为复数。因为的一次基础运算是把两个复数相乘再相加，如果直接按照上面公式进行计算时就要进行次复乘以及N（N+1）次加法运算。特别是当N较大时，由于复数乘法是幂指数，它的值会变得很大。由此，庞大的计算量让这种直接利用去计算的方法在很多领域中都很难去采用。

对于具有共轭对称性的特殊序列，下面来研究其性质：

点共轭对称复序列的定义为

,,和为实数。

序列的可以写成

                ，               （2。1。3）

其中，旋转因子为。把式2。1。3写成前后两部分的形式来推导其的性质

上式中的后一项，令代入，则上式变为

             （2。1。4）

再把换为，上式变为

                （2。1。5）

因为和都具有共轭对称性，即， ，那么上式可重新写为

               （2。1。6）

把表示成复数的形式，再把旋转因子写成三角的形式

把二者一起代入式2。1。6，运算整合之后可以得到