1、太原理工大学现代科技学院 课程设计 1 专业班级 学号 姓名 成绩 一、 设计目的 1、 加深对 DFT 算法原理和基本性质的理解； 2、 熟悉 FFT 的算法原理和 FFT 子程序的算法流程和应用； 3、 学习用 FFT 对连续信号和时域信号进行频谱分析的方法； 4、 学习 DSP 中 FFT 的设计和编程思想； 5、 学习使用 CCS 的波形观察器观察波形和频谱情况； 二 、 设计内容 用 DSP 汇编语言及 C 语言进行 编程，实现 FFT 运算、对输入信号进频谱分析。 三 、 设计原理 快速傅里叶变换 FFT 快速傅里叶变换（ FFT）是一种高效实现离散傅里叶变换（ DFT）的快速算法
2、，是数字信号处理中最为重要的工具之一，它在声学，语音，电信 和信号处理等领域有着广泛的应用。 1 离散傅里叶变换 DFT 对于长度为 N 的有限长序列 x(n)，它的离散傅里叶变换（ DFT）为 X(k)= 0 *)(n WnxN-nk （ 1） 式中， WN=e-j*2 /N ，称为旋转因子或蝶形因子。 从 DFT的定义可以看出，在 x(n)为复数序列的情况下， 装订线 太原理工大学现代科技学院 课程设计 2 （ N-1）次复数加法。因此，对所有 N 个 k 值，共需要 N2次复数乘法和 N(N-1)次复数加法。对于一些相当大有 N值（如 1024 点）来说，直接计算它的 DFT 所需要的计
3、算量是很大的，因此 DFT 运算的应用受到了很大的限制。 2 快速傅里叶变换 FFT 旋转因子 WN 有如下的特性。 对称性： WNk+N/2=-WNk 周期性： WNn(N-k)=WNk(N-n)=WN-nk 利用这些特性，既可以使 DFT 中有些项合并，减少了乘法积项，又可以将长序列的 DFT 分解成几个短序列的 DFT。 FFT 就是利用了旋转因子的对称性和周期性来减少运算量的。 FFT 的算法是将长序列的 DFT 分解成短序列的 DFT。例如： N为偶数时，先将 N点的 DFT 分解为两个 N/2 点的 DFT，使复数乘法减少一半：再将每个 N/2 点的 DFT 分解成 N/4 点的
4、DFT，使复数乘又减少一半，继续进行分解可以大大减少计算量。最小变换的点 数称为基数，对于基数为 2的 FFT算法，它的最小变换是 2点 DFT。 一般而言， FFT算法分为按时间抽取的 FFT（ DIT ）和按频率抽取的（ DIF FFT）两大类。 IF FFT 算法是在时域内将每一级输入序列依次按奇偶分成个短序列进行计算。而 DIF FFT 算法是在频域内将每一级输入序列依次奇偶分成个短序列进行计算。两者的区别是旋转因子出现的位置不太原理工大学现代科技学院 课程设计 3 同，得算法是一样的。在 DIF FFT 算法中，旋转因子 出现在输入端，而在 DIF FFT 算法中它出现在输入端。 假
5、定序列 x(n)的点数 N 是 2 的幂，按照 DIF FFT 算法可将其分为偶序列和奇序列。 偶序列 ： x(2r)=x1(r) 奇序列 ： x(2r+1)=x2(r) 其中： r=0,1,2, ,N/2-1 则 x(n)的 DFT 表示为 1 1 10 0 0N N Nnk nk nkN N Nn n nX k x n W x n W x n W n为 偶 数 n为 奇 数 / 2 1 / 2 1 212002 2 1NN rkrkNNrrx r W x r W / 2 1 / 2 1221200NN rk rkkN N Nrrx r W W x r W / 2 1 / 2 11 / 2
6、2 / 200NN rk k rkN N Nrrx r W W x r W 12 kNX k W X k , 0 , 1 , . . / 2 1r k N太原理工大学现代科技学院 课程设计 4 式中， x1(k)和 x2(k)分别为 x1(r)和 x2(r)的 N/2 的 DFT。 由于对称性， WNk+N/2=-WNk。因此， N 点 DFT 可分为两部分： 前半部分： x(k)=x1(k)+WkNx2(k) （ 4） 后半部分 ： x(N/2+k)=x1(k)-WkNx2(k) k=0,1, ,N/2-（ 5） 从式（ 4）和式（ 5）可以看出，只要求出 0N/2-1 区间 x1(k)和
7、x2(k)的值，就可求出 0N-1区间 x(k)的 N点值。 以同样的方式进行抽取，可以求得 N/4 点的 DFT，重复抽取过程，就可以使 N 点的 DFT 用上组 2 点的 DFT 来计算，这样就可以大减少运算量。 基 2 DIF FFT 的蝶形运算如图 (a)所示。设蝶形输入为 X1(K)和 X2(K)，输出为 x(k)和 x(N/2+K)，则有 x(k)=x1(k)+WkNx2(k) （ 6） x(N/2+k)=x1(k)-WkNx2(k) （ 7） 在基数为 2 的 FFT 中，设 N=2M，共有 M级运算，每级有 N/2个 2点 FFT 蝶形运算，因此， N点 FFT总共有 MN/2
8、 个蝶形运 算。 图 (a) 基 2 DIF FFT 的蝶形运算 CABA BCA BC太原理工大学现代科技学院 课程设计 5 例如：基数为 2的 FFT，当 N=8 时，共需要 3级， 12个基 2 DIT FFT 的蝶形运算。其信号流程如图 (b)所示。 x(0) x(0) WN0 x(4) x(1) -1 WN0 x(2) x(2) -1 WN0 WN2 x(6) x(3) -1 -1 WN0 x(1) x(4) -1 WN0 WN1 x(5) x(5) -1 -1 WN0 WN2 x(3) x(6) -1 -1 WN0 WN2 WN3 x(7) x(7) -1 -1 -1 图 (b)
9、8 点基 2 DIF FFT 蝶形运算 从图 (b)可以看出，输入是经过比特反转的倒位序列，称为位码倒置，其排列顺序为 x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)，输出是按自然顺序排列，其顺序 x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7). 四、总体设计方案 对 FFT 算法进行深入了解，以便确定设计的方案，可以参考其他书籍关于 FFT 的算法及应用说明，其次确定参数本实验我们完成一个 64点 FFT程序， FFT模拟输入数据文件可以由 MATLAB编程实现。 太原理工大学现代科技学院 课程设计 6 五、主要参数 1）数据文
10、件 coeff.inc 2）输入一组 FFT 模拟数据用 C 语言编写，程序如下： /*文件名： sindatagen.c*/ #include “stdio,h” #include”math.h” main() int i; float f256; FILE *fp; If(fp=fopen(“d:tms320c54fftsindata”,”wt”)=NULL) Printf(“cant open file!n”); Exit(0); For(i=0;i=255;i+) fi=sin(2*3.131415926*256.0); Fprintf(fp,”.word%1dn”,(log)(fi*16384); Fclose(fp); 太原理工大学现代科技学院 课程设计 7 六、 设计步骤 启动 CCS，在 CCS 中建立一个 C 源文件和一个命令文件，并将这两个文件添加到工程，再编译并装载程序： 启动 ccs2 后建立工程文件 FFT.pjt 建立源文件 FFT.c 与链接文件 FFT.cmd 太原理工大学现代科技学院 课程设计 8 将这两个文件加到 FFT.pjt 这个工程中。 创建 out 文件 加载 out 文件 太原理工大学现代科技学院 课程设计 9 加载数据 太原理工大学现代科技学院 课程设计 10 观察输入输出波形 输入波形（时域）
