1、DSPDSP 原理及应用课程设计报告原理及应用课程设计报告 FFT 的 DSP 实现 一、一、设计目的设计目的 1、加深对 DFT 算法原理和基本性质的理解； 2、了解并学习使用 FFT 算法，以及其在 TMS320C54X 上的运用； 3、学习 DSP 中 FFT 的设计和编程思想； 4、练习使用 CCS 的探针和图形工具来观察器观察波形和频谱情况。 二、二、设计内容设计内容 用 C 语言及汇编语言进行编程，实现 FFT 运算，对于 C 语言，实现 8 点和 16 点的 FFT 运算，对于汇编语言，需调试出 8 点的 FFT 运算结果。 三、设计原理三、设计原理 快速傅里叶变换（FFT）是一
2、种高效实现离散傅里叶变换（DFT）的快速算 法，是数字信号处理中最为重要的工具之一，它在声学，语音，电信和信号处理 等领域有着广泛的应用。 1、离散傅里叶变换 DFT 对于长度为 N 的有限长序列 x(n)，它的离散傅里叶变换（DFT）为 1, 1 ,0,)()( 1 0 NkWnxkX n n nk N （1） 式中， Nj N eW /2 ，称为旋转因子或蝶形因子。 从 DFT 的定义可以看出，在 x(n)为复数序列的情况下，对某个 k 值，直 接按（1）式计算 X(k) 只需要 N 次复数乘法和（N-1）次复数加法。因此，对所 有 N 个 k 值，共需要 N 2次复数乘法和 N(N-1)
3、次复数加法。对于一些相当大有 N 值（如 1024 点）来说，直接计算它的 DFT 所需要的计算量是很大的，因此 DFT 运算的应用受到了很大的限制。 2、快速傅里叶变换 FFT 旋转因子 WN 有如下的特性: 对称性： 2/Nk N k N WW 周期性： Nk N k N WW 利用这些特性，既可以使 DFT 中有些项合并，减少了乘法积项，又可以将长 序列的 DFT 分解成几个短序列的 DFT。FFT 就是利用了旋转因子的对称性和周期 性来减少运算量的。 FFT 的算法是将长序列的 DFT 分解成短序列的 DFT。例如：N 为偶数时，先将 N 点的 DFT 分解为两个 N/2 点的 DFT
4、，使复数乘法减少一半：再将每个 N/2 点的 DFT 分解成 N/4 点的 DFT，使复数乘又减少一半，继续进行分解可以大大减少计 算量。最小变换的点数称为基数，对于基数为 2 的 FFT 算法，它的最小变换是 2 DSP 原理及应用课程设计 江苏大学计算机学院 2 点 DFT。 一般而言，FFT 算法分为按时间抽取的 FFT（DIT FFT）和按频率抽取的 FFT （DIF FFT）两大类。DIF FFT 算法是在时域内将每一级输入序列依次按奇/偶分 成 2 个短序列进行计算，而 DIF FFT 算法是在频域内将每一级输入序列依次奇/ 偶分成 2 个短序列进行计算。两者的区别是旋转因子出现的
5、位置不同， 但算法是 一样的。在 DIF FFT 算法中，旋转因子 k N W 出现在输入端，而在 DIF FFT 算法中 它出现在输入端。 假定序列 x(n)的点数 N 是 2 的幂，按照 DIF FFT 算法可将其分为偶序列和 奇序列，记偶序列为12/, 1 ,0),2(2),-(N(4),(2),(0), 1 Nrrxxxxxx即 ， 奇序 列为 12/, 1 ,0),12(1),-(N(5),(3),(1), 2 Nrrxxxxxx即 ，则 x(n)的 FFT 表示为 )2()()( )12()2( )()()( 12/ 0 2 2 12/ 0 2 1 12/ 0 )12( 12/ 0
6、 2 1 0 1 0 N r rk N k N N r rk N N r kr N N r rk N N n nk N N n nk N WrxWWrx WrxWrx nn WnxWnxkX 为奇数为偶数 由于 2/ )2/(2 2 )/2(2 N NjNj N WeeW ，则（3）式可表示为 )3(12/,1 ,0)()( )()()( 21 12/ 0 2/2 12/ 0 2/1 NkkXWkX WrxWWrxkX k N N r rk N k N N r rk N 式中， )( 1 kX和)( 2 kX分别为)( 1 nx和)( 2 nx的 N/2 的 DFT。 由于对称性， , 2/K N Nk N WW 则)()()2/( 21 kXWkXNkX k N 。因此，N 点 )(kX可分为两部分： 前半部分：12/, 1 ,0
