FFT快速算法C程序.doc

电子信息工程综合课程设计报告书 DSP课 程 设 计 报告题 目：FFT快速算法C程序学 院：计算机与信息工程学院专业班级：09级电子信息工程2班小组成员：刘森 指导教师：杨龙时间：2012年03月21日目录1.设计目的31.1.设计目的31.2.使用设备32.设计任务与要求43.原理与分析44.实验步骤55.实验程序76.心得体会101设计目的1.1. 设计目的1掌握用窗函数法设计FFT 快速傅里叶的原理和方法； 2熟悉FFT 快速傅里叶特性； 3了解各种窗函数对快速傅里叶特性的影响。1.2. 使用设备PC 兼容机一台，操作系统为Windows2000(或Windows98，WindowsXP，以下默认为Windows2000)，安装TC软件。 2设计任务与要求1按FFT流程设计程序；2 实现程序的抽样 输入倒位序输出自然序3可以观察到各次谐波3原理与分析1 FFT 的原理和参数生成公式 公式（1）FFT 运算公式 FFT 并不是一种新的变换，它是离散傅立叶变换（DFT ）的一种快速算法。由于我们在计算DFT 时一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法则需二次实数加法。每运算一个X（k）需要4N 次复数乘法及2N+2（N-1）=2（2N-1）次实数加法。所以整个DFT 运算总共需要4N2 次实数乘法和N*2(2N-1)=2N(2N-1)次实数加法。如此一来，计算时乘法次数和加法次数都是和N2 成正比的，当N 很大时，运算量是可观的，因而需要改进对DFT 的算法减少运算速度。 根据傅立叶变换的对称性和周期性，我们可以将DFT 运算中有些项合并。 我们先设序列长度为N=2L，L 为整数。将N=2L 的序列x(n)(n=0,1,，N-1)，按N的奇偶分成两组，也就是说我们将一个N 点的DFT 分解成两个N/2 点的DFT，他们又重新组合成一个如下式所表达的N 点DFT： 一般来说，输入被假定为连续的。当输入为纯粹的实数的时候，我们就可以利用左右对称的特性更好的计算DFT。 我们称这样的RFFT 优化算法是包装算法：首先2N 点实数的连续输入称为“进包”。其次N 点的FFT 被连续被运行。最后作为结果产生的N 点的合成输出是“打开”成为最初的与DFT 相符合的2N 点输入。 使用这战略，我们可以划分FFT 的大小，它有一半花费在包装输入O （N ）的操作和打开输出上。这样的RFFT 算法和一般的FFT 算法同样迅速，计算速度几乎都达到了两次DFT的连续输入。下列一部分将描述更多的在TMS320C54x 上算法和运行的细节。2 程序流程图开始初始化工作变量调用波形发生子程序产生波形（3个正弦波）调用FFT子程序计算当功率谱波形发生计算步长用标准C的sin函数计算当前波形值（8点）结束FFT按照编码逆序排列输入序列返回计算结果用蝶形算法计算计算功率谱4实验步骤1实验准备-启动TC。2打开工程，编写程序；3编译连接，并查看user screen；5实验程序#include#include/*定义结构体*/struct cmplex float zhen; float jia; ;/*复乘*/struct cmplex ls(struct cmplex a1,struct cmplex a2) struct cmplex c; c.zhen=a1.zhen*a2.zhen-a1.jia*a2.jia; c.jia=a1.zhen*a2.jia+a1.jia*a2.zhen; return(c); void main()int i,k,N=8,nv,nm,j=0,m,le,le1,ip;float pai=3.1415926,tmp,sum,*a ;struct cmplex u,w,t,x8;/*抽样函数*/for(i=0;iN;i+)xi.zhen=1; xi.jia=0;for(i=N/2;iN;i+)xi.zhen=-1; xi.jia=0;/*倒位序函数*/nv=N/2;nm=N-1;for(i=0;inm;i+)if(ij)t=xj;xj=xi;xi=t;k=nv;while(k=j)j-=k;k=k/2;j+=k;/*FFT快速算法*/for(m=1;m=3;m+)le=pow(2,m);le1=le/2;u.zhen=1;u.jia=0;tmp=pai/le1;w.zhen=cos(-tmp);w.jia=sin(-tmp);for(j=0;jle1;j+)for(i=j;iN;i+=le)ip=i+le1; t=ls(xip,u); xip.zhen=xi.zhen-t.zhen; xip.jia=xi.jia-t.jia; xi.zhen+=t.zhen; xi.jia+=t.jia;u=ls(u,w);/*最后输出结果*/printf(n);printf(*n) ;for(i=0;iN;i+) sum=xi.zhen*xi.zhen+xi.jia*xi.jia; ai=sqrt(sum); printf(%f n,ai);最后输出结果：a0=0.000000a1=5.226252a2=0.000000a3=2.164784a4=0.000000a5=2.164784a6=0.000000a7=5.2262526. 心得体会首先说明：1如果为商大的同学，杨龙老师的数字信号处理课程设计FFT运算，这个程序无需任何改动直接输出正确结果，然后就是“优秀”到手！2若为DSP爱好者参考使用，则里面的分段程序可供各位学友们参考。心得体会： 通过本次课程设计是我对DSP有了更深层次的理解，但是我最值得高兴地并非是这次课设的成功，而是经过两天的编程是我对C语言有了更深层次的理解也是我的编程能力有了很大的