第三章研究对基-2FFT优化算法的理论可行性分析，以DIF FFT为例，先介绍按相同旋转因子分组法将基-2FFT算法进行优化，减少旋转因子的访问次数，然后利用旋转因子的特性，进一步理论分析减少旋转因子的访问次数的优化算法。

第四章首先介绍实验硬件平台TMS320C6678和软件平台CCS，研究实现优化的FFT算法来减少旋转因子的引用次数，消除冗余的内存引用，减少资源占用，并且调用Matlab中FFT函数，得到结果与CCS环境中所得的结果进行比较，验证算法的正确性，以及不同点数的FFT运用两种算法的性能比较。

第五章为了进一步提高DSP的运算效率，研究实现FFT在多核DSP上的并行实现方法，首先介绍FFT并行分解算法原理,然后介绍并行算法在TMS320C6678上的具体实现的软件线程和函数流程,最后对不同点数利用不同个数的核进行并行FFT运算,并对实验结果进行分析。

2  快速傅里叶算法原理

2。1  离散傅里叶变换

对于有限长离散数字信号，它的离散频谱可由离散傅里叶变换求得[7]。DFT定义为：

      （2。1）

或者方便地写为：

        （2。2）

其中都是复数序列，。即为旋转因子，不难看出，旋转因子是周期性的，且周期为N，即。除了周期性外，旋转因子还具有对称性，即。

由DFT的定义可以看出，直接运算N点实序列的DFT需要进行次复数乘法和次复数加法。因此，对于一些相当大的N值来说，直接计算DFT运算量是很大的。为了减少计算中的运算量，提高算法的运算速度，从而减少DFT运行所需要的时间，可以利用旋转因子特有的周期性和对称性将原有的N点序列分解为两个较短的序列，再将这些较短序列的DFT简单组和得到原序列的DFT，即FFT的基本思想。

DFT最初是由库利和图基提出的，后续有很多研究人员对其进行了加强和改进。目前，已经涌现许多独立于库利图基方法之外的算法，如素因子算法，分裂基算法，向量基算法，分裂向量基算法，Winograd算法等。

2。2  基-2算法

基-2算法又可分为两类，即按时间抽取FFT算法（DIT FFT）与按频率抽取FFT算法（DIF FFT）[8]。

2。2。1  DIT FFT来:自[优.尔]论,文-网www.youerw.com +QQ752018766-

假定序列的点数N是2的整数次幂，在时域上按奇数项和偶数项分解为两个长度为N/2的子序列和。于是，的N点DFT可写为：

            （2。3）

和均分别是N/2点序列和的DFT，，由DFT和旋转因子的性质可得后N/2个值

             （2。4）

由式2。3和2。4可知只需要求两个N/2点的DFT，即可得全部的N点。当时，可以分解至两点DFT为止。图2。1为基本的基-2DIT FFT蝶形图。

图 2。1 基本基-2DIT FFT蝶形图

2。2。2  DIF FFT

假定序列的点数N是2的整数次幂，在时域上按前后对半分开为两个长度为N/2的子序列和。于是，的N点DFT可写为：

      （2。5）

然后对频率序列抽取，把它按奇偶分开，偶数时令，奇数时令，其中。因为且，则式2。5可以改写为：

     （2。6）

   （2。7）

频率序列是时间序列的N/2点DFT，频率序列是时间序列的N/2点DFT。于是，N点DFT便化成了两个N/2点DFT的计算。图2。2为基本的基-2DIF FFT蝶形图。