DSP课程设计-8点基于DIF的FFT的实现(精)

1、课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目：8点基于 DIF 的 FFT 的实现初始条件：具备数字信号处理的理论知识；具备 Matlab 编程能力；熟悉基于 DIF 的 FFT 的实现原理；提供编程所需要的计算机一台要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、独立编写一个 8点的基于 DIF 的 FFT 实现程序，不能使用 matlab自带的 FFT实现函数2、程序运行结果与 matlab自带函数结果进行对比3、完成符合学校要求的设计说明书时间安排：一周，其中 3天程序设计，2 天程序调试指导教师签名：年月曰系主任（或责任教师）签名：年月

2、曰XX 大学数字信号处理课程设计说明书目录摘要I1Matlab 软件简介11.1 Matlab 语言的历史 11.2 Matlab 软件概况 11.3 Matlab 的特点 12快速傅里叶变换算法分析 32.1 FFT 简介32.2按频率抽选的 FFT 算法 33 程序设计63.1程序设计思路 63.2要使用的 Matlab 函数 64程序流程图85源程序95.1直接调用 FFT 函数源程序 95.2 FFT 计算源程序 96程序运行结果分析 116.1程序运行结果 116.2结果分析127课程设计心得体会 13参考文献14致谢15XX 大学数字信号处理课程设计说明书摘要快速傅里叶变换（FFT

3、）是离散傅里叶变换（DFT）的快速算法，FFT 算法通过利用旋转因子的性质，将一个大点数 DFT 化成几个小点数 DFT，就可以大大减少运算量。DIF-FFT 是利用频率抽选的 FFT 算法，在 Matlab 中可以通过三重循环语句实现。关键词：FFT,蝶形运算，倒序排列IXX大学数字信号处理课程设计说明书1Matlab软件简介1.1 Matlab语言的历史70 年代后期， 身为美国 NewMexico 大学计算机系系主任的 CleveMoler发现学生用FORTRAN 编写接口程序很费时间，于是他开始自己动手,利用业余时间为学生编写 EISPACK 和 LINPACK 的接口程序。 Clev

4、eMoler 给这个接口程序取名为 Matlab。1984 年，为了推广 Matlab 在数值计算中的应用，CleveMoler、JohonLittle等正式成立了 Mathworks公司，从而把 Matlab 推向市场，并开始了对 Matlab 工具相等的开发设计。1.2 Matlab软件概况Matlab是 MatrixLaboratory 的缩写，意为矩阵实验室。它具有强大的矩阵处理功能和绘图功能， 进还能进行文字处理， 绘图， 建模仿真等功能。 随着版本的不断升级，它在数值计算及符号计算功能上得到了进-Matlab已经发展成为多学科、多种工作平台的功能强大的大型软件。在欧美等高校，Mat

5、lab 已经成为线性代数、自动控制理论、概率论及数理统计、数字信号处理、时间序列分析、动态系统仿真等高级课程的基本教学工具。1.3 Matlab的特点Matlab有以下一些特点：Matlab的帮助功能很强大，自带有详细的帮助手册，基于 HTML 的完整的帮助功能，也可以用 help命令来得到帮助信息。程序语法与 C 语言类似，设计自由度大，方便我们编程。例如在 Matlab 里，用户无需对变量预定义就可使用。 大量数学函数已经定义好， 并且有很强的用户自定义函数的能力。Matlab有咼级的程序环境， 但程序环境很简单易用， 有与其它语言编写的程序结合和输入输出格式化数据的能力； Matlab

6、既具有结构化的控制语句， 又有面向对象编程的特性。还有一个原因使 Matlab 受人们欢迎的，那就是 Matlab 源程序具有很大的开放性。除了内部函数以外， 所有 Matlab 的核心文件和工具箱文件都是可读可改的源文件，用户可通过对源文件的修改以及加入自己的文件构成新的工具箱。1XX大学数字信号处理课程设计说明书Matlab有强大的的图形绘制功能。在 Matlab里，数据可视化的操作非常简单易用。Matlab还有较强的编辑图形界面的能力。 可以用来声成图解和可视化的二维、 三维图。Matlab还拥有功能强大的各种工具箱。 其工具箱分为两类： 功能性工具箱和学科性工具箱。功能性工具箱主要用来

7、扩充其符号计算功能，图示建模仿真功能，文字处理功能以及与硬件实时交互功能。 功能性工具箱用于多种学科。 而学科性工具箱是专业性比较强的，如(control、signalproceessing、commumnication)toolbox 等。这些工具箱都是由该领域内学术水平很高的专家编写的， 所以用户无需编写自己学科范围内的基础程序，而直接进行高，精，尖的研究，能极大地促进我们的学习研究工作。虽然 Matlab 有很多优点，但它也有一些缺点，比如：由于 Matlab 的程序不用编译等预处理，也不生成可执行文件，程序为解释执行，所以速度较慢。2XX大学数字信号处理课程设计说明书2 快速傅里叶变换

8、算法分析2.1 FFT 简介快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的快速算法，他在傅里叶变换理论上并没有新的发现， 但是却极大的减少了离散傅里叶变换的运算量。 快速傅里叶变换是 1965 年由 J.W.库利和 T.W.图基提出的。1965 年，库利和图基合作在MathematicsofComputation上发表了论文AnAlgorithmfortheMachineComputationofComplexFourierSeries，提出了按时抽取的快速傅立叶变换算法，也称库利-图基算法，被视为 DSP 走向应用的开端。从此，对快速傅里叶变换算法的研究便不断深入，数字信号处理这门新兴

9、学科也随FFT 的出现和发展而迅速发展。之所以需要快速傅里叶变换， 是因为离散傅里叶变换的运算量较大。 离散傅里叶变换的公式为：正变换：X(k)=DFTx(n)=x(n)WNn=0N-1nkn=0，1，2.，N-11N-1-nk 逆变换：x(n)=IDFTx(n)=X(k)WNn=0，1，2.,N-1Nk=0一般情况下 WN，x(n),X(k)都是复序列，计算一个完整的 N点 DFT 需要 N2 次复数乘法与 N-1 次复数加法，当 N极大时运算量与 N2 成正比，运算量将过于巨大，不方便应用。而 FFT 算法通过利用旋转因子的性质，将一个大点数 DFT 化成几个小点数 DFT，就可以大大减少

10、运算量。2.2按频率抽选的 FFT 算法FFT 算法主要有两种，按时间抽选的 FFT 的算法(DIT-FFT)和按频率抽选的 FFT算法(DIF-FFT)。这里主要介绍 DIF-FFT。DIF-FFT 算法是将输入序列 x(k)分成前后两个部分。X(k)=x(n)WN=n=ON-12n=ON-lnkx(n)Wn=ON-12nkN+x(n)Wn=N2N-lnkN=x(n)WNn=ON-lnkNNk(n+)+x(n+)WN22n=0N-1=x(n)+x(n+NNk/2nk)WNWN23XX大学数字信号处理课程设计说明书由于 WNN/2=-1，则 WNN-12n=0Nk/2=(-1)k(1k 为偶数

11、=1I-1k为奇数所以 X(k)=x(n)+(-1)x(n+kNnk)WN2k 为偶数(k=2r把 k 按奇数和偶数分，ir=0,1,.N/2-1Ik=2r+1k为奇数将 X(k)分为两部分：X(2r+1)=口x(n)-x(n+n=0N-12Nnrn)WNWN/22X(2r)=x(n)+x(n+n=0N-12Nnr)WN/22令 x1=x(n)+x(n+N-12NNn),x2=x(n)-x(n+)WN，可得 222r)=Yxl(n)WN/2I，r=0，1，2，N/2-1N-1I2rnX(2r+l)=x2(n)WN/2I1n=0丿由此可得频率抽选法蝶形运算单元，如图 2.1 所示x(n)Nx(n

12、+)2nx1=x(n)+x(n+N)2Nn)WN2x2=x(n)-x(n+图 2.1 频率抽选法蝶形运算单元这样可以把一个 N点 DFT 分解为两个 N/2 点 DFT 的组合，两个 N/2 点 DFT 还可以继续分解，设 N=2M，则经过 M-1 次分解，最后可以分解成为 N/2 个两点 DFT,可以由一个蝶形运算来求解。例如 8 点 DIF-FFT 蝶形运算图如图 2.24XX大学数字信号处理课程设计说明书图 2.28 点 DIF-FFT 运算流图。输出序列的排列规律不是从小到大按顺序的，而是按照倒叙规则排序的，即先将0-7 转换为二进制数，然后将二进制数左右倒序，再转为十进制就可以得到新

13、的数列，即：0，4，2，6，1，5，3，7。O一一n5XX大学数字信号处理课程设计说明书3 程序设计3.1程序设计思路由 8 点 FFT 运算的蝶形图可知，FFT 运算的基本单元是一个个蝶形运算单元，一个蝶形运算单元可以用几条语句实现， 然后可以用循环语句来进行各个蝶形运算单元的计算。8 点 FFT 的蝶形运算有 3 级，第 1级有 1组，每组 4 个蝶形运算单元，旋转因子是W80、W81、W82、W83；第 2级有 2 组，每组 2 个蝶形运算单元，循环因子是W40，W41；第 3 级有 4 组，每组 1 个蝶形运算单元，旋转因子是 W20。总结运算规律，来设定循环语句。第一层循环在 1 到

14、 3 级间循环， 循环变量 mm=1， 2， 3。 旋转因子下标 Nm=24-mm=8，4，2。第二层循环在该级的各组间循环，每级有 2mm-1 组，每组第一行对应的 x值为：第 1 级是 x(0)，第 2 级是 x(0)，x(4)，第 3 级是 x(0)，x,x,x(6)。设第二层循环变量为 p，则在 Matlab中，p=0：Nm：7。第三层循环在该组的各个蝶形运算单元间循环，每组有 Nm/2 个蝶形运算单元，则循环变量 k 从 1到 Nm/2，旋转因子是 e-2n(-1)jNm，每次蝶形运算跨越的行数是 Nm/2，则参加蝶形运算的 x 值为 x(k+p)和 x(k+p+Nm/2)。循环完成

15、后则 FFT 运算完成，再将 x 序列按倒叙规律重新排列就可以得到 X(k)序列。3.2要使用的 Matlab 函数程序设计思路已经有了，结下来分析如何在 Matlab 里具体实现该程序。Matlab 的语法并不困难，掌握了所需的函数后就能很快设计出程序了，这里主要介绍一下要用到的函数。直接用 Matlab 计算 N 点 FFT 可以用函数 fft(x,N)， 在此课设中用来和自编程序对照结果。还用到一些计算函数，如 exp(x)计算 e 的 x 次方,abs(x)计算 x 绝对值。倒序运算主要用到的函数有，dec2bin(x,m)，是把十进制序列 x转换为 m位二进制数，bin2dec(x,

16、m)也是类似功能。fliplr 函数是将一个矩阵左右颠倒，则程6XX 大学数字信号处理课程设计说明书序中求倒序的语句就是：d=bin2dec(fliplr(dec2bin(0:N-l,m)+l;y=x(d);x是 N 点序列，执行完语句后，y 序列就是 x 序列的倒序排列。计算完成结果要绘图输出，要用到的函数是 subplot(a,b,c)，功能是让下面的语句绘制 a 行 b 列图形中的第 c 个。绘图用 stem(x,y)函数，是以 x序列为横轴，y 序列为纵轴，绘制离散的图像。绘完图可以用 title 函数给图像命名。7XX 大学数字信号处理课程设计说明书4图 4.1程序流程图8XX 大学

17、数字信号处理课程设计说明书5源程序5.1直接调用 FFT 函数源程序以下是直接调用 Matlab自带的 FFT函数计算的源程序， 其输入序列为 x=02460246,求出 FFT 结果 y=X(k)后对其幅值和原序列进行绘图。N=8;n=0:N-1;%FFT点数为 8 点横坐标序列%设定输入 x(n)序列%调用 FFT 函数求 X(k)序列，y=X(k)%求幅值 x=02460246;y=fft(x,N)mag=abs(y);subplot(2,1,1);stem(n,x);%绘制原序列 title(输入序列 x(n);subplot(2,1,2);stem(n,mag);%绘制 X(k)序列

18、 title(8 点调用 FFT 函数计算结果)5.2FFT 计算源程序以下是本次课程设计编写的 FFT 计算程序，输入序列和 5.1 的程序一样，都是x=02460246，y等于 FFT 输出序列 X(k)，最后对 y 的幅值和原序列进行绘图。N=8;斤始N循环mm=l到3级蝶形运算求出蘇形运算级数m=3到个蝶形运算循环该组3-ntnii循环该级1到2mmJ组蝶晦算计算一个蝶形运算单元求该级旋转因子下标Nm序列倒序后绘图设足输入序列n=0:N-1;%设定 FFT 点数为 8 点横坐标序列%设定输入序列 x(n)%暂存 x序列到 x1%求蝶形运算级数 m%循环 mm=1到 3 级蝶形运算%求该

19、级旋转因子下标 Nm，Nm=8,4,2x=02460246;x1=x;m=log2(N);formm=1:mNm=2人(m-mm+1);forp=0:Nm:N-1%循环该级 1到 2mm-1 组蝶形运算fork=1:Nm/2%循环该组 1到 23-mm 个蝶形运算9XX 大学数字信号处理课程设计说明书 kp=k+Nm/2+p;a=x(kp);%确定蝶形运算对应单元下标暂存x(xp)x(kp)=(x(k+p)-a)*exp(-j*2*pi*(k-l)/Nm);x(k+p)=x(k+p)+a;endendendd=bin2dec(fliplr(dec2bin(0:N-1,m)+1;%把 0-7 倒

20、序排列 y=x(d)%y=x序列的倒序，即 y=X(k)%求 y幅值%x 恢复成原序列进行蝶形运算mag=abs(y);x=x1;subplot(2,1,1);stem(n,x);%绘制原序列 title(输入序列 x(n);subplot(2,1,2);stem(n,mag);%绘制 X(k)序列 title(8点 FFT 计算结果)10XX 大学数字信号处理课程设计说明书6程序运行结果分析6.1程序运行结果首先在 Matlab 中输入源程序，然后保存，选择 Debug 菜单中的 Run执行程序。如图 6.1：图 6.1Matlab界面首先运行程序 1,即直接调用 Matlab自带的 FFT

21、 函数计算。运行结果如图6.2 所示。y序列即 X(k)序列为 y=240-8+8i0-80-8-8i0。图 6.2调用 FFT 函数运行结果 111XX 大学数字信号处理课程设计说明书30110jfrj.p24输入序列刈m然后是用自己编写的 FFT 计算函数，运行得到如图 6.3 所示结果。y序列即 X(k)序列为 y=240-8+8i0-80-8-8i0。图 6.3运行结果 26.2结果分析通过比较图 6.2和图 6.3可以看出， 两者的 FFT 结果完全一样， 可以证明编写的 FFT程序正确，达到了课程设计的任务要求。而且本程序不仅可以计算 8 点 FFT,也可以计算 N 点 FFT(N

22、=2m)，经测试结果也是正确的。12XX 大学数字信号处理课程设计说明书7课程设计心得体会通过 Matlab 一周以来的学习研究，我对 Matlab 有了初步的认识，我掌握了Matlab的基本操作，并学会了用 Matlab 解决一些电路和数学上的问题，下面是我具体的一些体会Matlab功能非常强大，几乎可以计算我们目前所遇到的任何问题，不仅可以计算数学问题，也可以用来解决电路等其他学科的各种问题。而且我们可以自编函数，从而可以解决更多样的问题。但以目前我们的知识，只能掌握 Matlab 的一小部分功能，在以后的学习中，我还需要继续学习 Matlab 的相关知识。Matlab虽然功能非常强大，但其操作却非常简单，它的语法类似于我们以前学过的C 语言，使我很容易上手，而其语法比 C 语言更为自由，限制更少，语法类似于自然语言，简洁而智能化，使我可以很容易的编写程序且不容易出错。关于绘图的操作则比 C 语言简单得多，用几条简单的语句就可以绘出各种曲线、图形，使我们的学习研究变的非常方便。通过本次课程设计我掌握了 FFT 的编程方法，对 FFT 有了更深刻的了解。我认为学习 Matlab 的关键在于函数，只要