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

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

2、师签名：年月曰 系主任（或责任教师）签名： 年月曰 XX 大学数字信号处理课程设计说明书 目录 摘 要 . . I 1 Matlab 软件简 介 . 1 1.1 Matlab 语言的历 史 . 1 1.2 Matlab 软件概 况 1.3 Matlab 的特 点 . 1 2 快速傅里叶变换算法分 析 . 3 2.1 FFT 简 介 3 2.2 按频率抽选的 FFT 算 法 . . 3 3 程序设 计 .6 3.1 程序设计思 路 . 6 3.2 要使用的 Matlab 函 数 . 6 4 程序流程 图 8 5 源程 序 . 9 5.1 直接调用 FFT 函数源程 序“ . 9 5.2 FFT

3、计算源程 序 6 程序运行结果分 析 . 11 6.1 程序运行结 果 . 11 6.2 结果分 析 . 2 7 课程设计心得体 会 . 13 参考文 献 . . 14 致 谢 . . 15 XX 大学数字信号处理课程设计说明书 摘要快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法，FFT 算法通过 利用旋转因子的性质，将一个大点数 DFT 化成几个小点数 DFT，就可以大大减 少运算量。DIF-FFT 是利用频率抽选的 FFT 算法，在 Matlab 中可以通过三重循环 语句实现。 关键词：FFT，蝶形运算，倒序排列 I XX 大学数字信号处理课程设计说明书 1 Matlab 软

4、件简介 1.1 Matlab 语言的历史 70 年代后期，身为美国 New Mexico 大学计算机系系主任的 Cleve Moler 发现学生 用FORTRAN 编写接口程序很费时间，于是他开始自己动手，利用业余时间为学生 编写EISPACK 和 LINPACK 的接口程序。Cleve Moler 给这个接口程序取名为 Matlabo 1984年，为了推广 Matlab 在数值计算中的应用，Cleve Moler、Johon Little 等正式成立了 Math works 公司，从而把 Matlab 推向市场，并开始了对 Matlab 工具相等的开发设计。 1.2 Matlab 软件概况

5、Matlab 是 Matrix Laboratory 的缩写，意为矩阵实验室。它具有强大的矩阵处理功 能和绘图功能，进还能进行文字处理，绘图，建模仿真等功能。随着版本的不断 升级，它在数值计算及符号计算功能上得到了进一步完善。 Matlab 已经发展成为 多学科、多种工作平台的功能强大的大型软件。在欧美等高校， Matlab 已经成为 线性代数、自动控制理论、概率论及数理统计、数字信号处理、时间序列分析、 动态系统仿真等高级课程的基本教学工具。 1.3 Matlab 的特点 Matlab 有以下一些特点： Matlab 的帮助功能很强大，自带有详细的帮助手册，基于 HTML 的完整的帮助功 能

6、，也可以用 help 命令来得到帮助信息。 程序语法与 C 语言类似，设计自由度大，方便我们编程。例如在 Matlab 里，用 户无需对变量预定义就可使用。大量数学函数已经定义好，并且有很强的用户自 定义函数的能力。 Matlab 有高级的程序环境，但程序环境很简单易用，有与其它语言编写的程序结 合和输入输出格式化数据的能力；Matlab 既具有结构化的控制语句，又有面向对 象编程的特性。 还有一个原因使 Matlab 受人们欢迎的，那就是 Matlab 源程序具有很大的开放 性。除了内部函数以外，所有 Matlab 的核心文件和工具箱文件都是可读可改的源 文件，用户可通过对源文件的修改以及加

7、入自己的文件构成新的工具箱。 1 XX 大学数字信号处理课程设计说明书 Matlab 有强大的的图形绘制功能。在 Matlab 里，数据可视化的操作非常简单易 用。Matlab 还有较强的编辑图形界面的能力。可以用来声成图解和可视化的二 维、三维图。 Matlab 还拥有功能强大的各种工具箱。其工具箱分为两类：功能性工具箱和学科 性工具箱。功能性工具箱主要用来扩充其符号计算功能，图示建模仿真功能，文 字处理功能以及与硬件实时交互功能。功能性工具箱用于多种学科。而学科性工 具箱是专业性比较强的，如( control、signal proceessing、commumnication) toolb

8、ox 等。这些工具箱都是由该领域内学术水平很高的专家编写的， 所以用户无 需编写自己学科范围内的基础程序，而直接进行高，精，尖的研究，能极大地促 进我们的学习研究工作。 虽然 Matlab 有很多优点，但它也有一些缺点，比如：由于 Matlab 的程序不用编 译等预处理，也不生成可执行文件，程序为解释执行，所以速度较慢。 2 XX 大学数字信号处理课程设计说明书 2 快速傅里叶变换算法分析 2.1 FFT 简介 快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的快速算法，他在傅里叶变 换理论上并没有新的发现， 但是却极大的减少了离散傅里叶变换的运算量。 快速 傅里叶变换是 1965年由 J.

9、W.库利和 T.W.图基提出的。1965 年，库利和图基合作 在Mathematics of Computation上发表了论文An Algorithm for the Machine Computation of Complex Fourier Series，提出了按时抽取的快速傅立叶变换算 法，也称库利-图基算法，被视为 DSP 走向应用的开端。从此，对快速傅里叶变 换算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发展而 迅速发展。 之所以需要快速傅里叶变换，是因为离散傅里叶变换的运算量较大。离散傅里叶 变换的公式为： 正变换：X(k)=DFTx(n)= 刀 x(n)

10、WN n=0N1 nkn=0，1，2，N-1 1N-1-nk 逆变 换：x(n)=IDFTx(n)=刀 X(k)WN n=0 1，2，N-1 Nk=0 一般情况下 WN，x(n)，X (k)都是复序列，计算一个完整的 N 点 DFT 需要 N2 次复数乘法与 N-1 次复数加法，当 N 极大时运算量与 N2 成正比，运算量将过于 巨大，不方便应用。而 FFT 算法通过利用旋转因子的性质，将一个大点数 DFT 化成几个小点数 DFT，就可以大大减少运算量。 2.2 按频率抽选的 FFT 算法 FFT 算法主要有两种，按时间抽选的 FFT 的算法(DIT-FFT )和按频率抽选的 FFT 算法(D

11、IF-FFT )。这里主要介绍 DIF-FFT。 DIF-FFT 算法是将输入序列 x( k)分成前后两个部分。 X(k)=刀 x( n)WN=n=0 N-12 n=0N-Ink 刀 x( n)Wn=0212n kN+E x(n) Wn=N2N- 1n kN=E x( n)W Nn=0N - 1n kNNk( n+)+ E x(n+)WN22 n=02 仁 E x( n)+x( n+NNk/2 nk)WNWN2 3 XX 大学数字信号处理课程设计说明书 由于 WN N/2 =-1，则 WN N-12 n=0 Nk/2 =(-1) k ? 1k 为偶数=? ?-1k 为奇数 所以 X(k)= E

12、x(n)+(-1)x(n+ k Nn k)WN 2 k 为偶数？ k=2r 把 k 按奇数和偶数分，？ r=0, 1,N/2-1 ?k=2 叶 1k 为奇数 将 X (k)分为两部分：X(2 叶 1)= E x(nx(n+ n=0 N-12 Nn rn)WNWN/2 2 X(2r)= E x( n)+x( n+ n=0 N-12 Nn r)WN/2 2 令 x1=x(n)+x(n+ N-12 NNn ),x2=x(n)-x(n+)WN，可得 22 rn ? X(2r)=刀 x1( n) WN/2 ? n=0 ? , r=0, 1, 2,，N/2-1 N -1 ?2 rn X(2 r+1)=刀

13、x2( n) WN/2 ?n=0? 由此可得频率抽选法蝶形运算单元，如图 2.1 所示 x(n )N x( n+) 2 n x1=x (n )+x (n+ N)2 Nn )WN2 x2=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.2 4 XX 大学数字信号处理课程设计说明书 图 2.2 8 点 DIF-FFT

14、运算流图。 输出序列的排列规律不是从小到大按顺序的，而是按照倒叙规则排序的，即先将 0-7 转换为二进制数，然后将二进制数左右倒序，再转为十进制就可以得到新的 数列，即：0, 4, 2, 6，1, 5, 3，7。 5 XX 大学数字信号处理课程设计说明书 3 程序设计 3.1 程序设计思路 由 8 点 FFT 运算的蝶形图可知，FFT 运算的基本单元是一个个蝶形运算单元，一 个蝶形运算单元可以用几条语句实现，然后可以用循环语句来进行各个蝶形运算 单元的计算。 8 点 FFT 的蝶形运算有 3 级，第 1 级有 1 组，每组 4 个蝶形运算单元，旋转因子 是 W80、W81、W82、W83;第

15、2 级有 2 组，每组 2 个蝶形运算单元，循环因子 是 W40，W41 ;第 3 级有 4 组，每组 1 个蝶形运算单元，旋转因子是 W20。总结 运算规律，来设定循环语句。 第一层循环在 1 到 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(2)，x(4)，x(6)。设第二层 循环变量为 p，则在 Matlab 中，p=0： Nm: 7。 第三层循环在该组的各个蝶形运算单

16、元间循环，每组有 Nm/2 个蝶形运算单元， 则循环变量 k 从 1 到 Nm/2，旋转因子是 e-2n (k1)j Nm，每次蝶形运算跨越的行 数是 Nm/2，则参加蝶形运算的 x 值为 x(k+p)和 x(k+p+Nm/2)。 循环完成后则 FFT 运算完成，再将 x 序列按倒叙规律重新排列就可以得到 X(k)序 列。 3.2 要使用的 Matlab 函数x(0 x(7) x(l x(2 r(4 工 x(6) * *-* A l 0 J 4- X(4l i 畑 A Al 6) * Jf(l) * X *片 4* AU) 程序设计思路已经有了，结下来分析如何在 Matlab 里具体实现该程序

17、。Matlab 的 语法并不困难，掌握了所需的函数后就能很快设计出程序了，这里主要介绍一下 要用到的函数。 直接用 Matlab 计算 N 点 FFT 可以用函数 fft(x,N)，在此课设中用来和自编程序对 照结果。还用到一些计算函数，如 exp(x)计算 e 的 x 次方,abs(x)计算 x 绝对值。 倒序运算主要用到的函数有，dec2bin(x,m)，是把十进制序列 x 转换为 m 位二进 制数，bin2dec(x,m)也是类似功能。fliplr 函数是将一个矩阵左右颠倒，则程 6 XX 大学数字信号处理课程设计说明书 序中求倒序的语句就是： d=b in 2dec(fliplr(de

18、c2b in (0:N-1,m)+1; y=x(d); x 是 N 点序列，执行完语句后，y 序列就是 x 序列的倒序排列。 计算完成结果要绘图输出，要用到的函数是 subplot(a,b,c),功能是让下面的语句 绘制 a行 b 列图形中的第 c 个。绘图用 stem(x,y)函数，是以 x 序列为横轴，y 序 列为纵轴，绘制离散的图像。绘完图可以用 title 函数给图像命名。 7 XX 大学数字信号处理课程设计说明书 4开始 图 4.1 程序流程图 8 XX 大学数字信号处理课程设计说明书 5 源程序 5.1 直接调用 FFT 函数源程序 以下是直接调用 Matlab 自带的 FFT 函

19、数计算的源程序，其输入序列为 x=0 2 4 6 0 2 4 6，求出 FFT 结果 y=X(k)后对其幅值和原序列进行绘图。 N=8; n=0:N-1; %FFT 点数为 8 点横坐标序列 %设定输入 x(n)序列 %调用 FFT 函数求 X(k)序列，y=X(k) % 求幅值 x=0 2 4 6 0 2 4 6 ; 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)序列 title(8 点调用 FFT 函数计算结果)

20、 5.2 FFT 计算源程序 以下是本次课程设计编写的 FFT 计算程序，输入序列和 5.1 的程序一样，都是 x=0 2 4 6 0 2 4 6，y 等于 FFT 输出序列 X(k)，最后对 y 的幅值和原序列进行绘 图。 N=8; n=0:N-1; %设定 FFT 点数为 8 点横坐标序列 %设定输入序列 x(n) %暂存 x 序列到 x1 %求蝶形运算级数 m %循环 mm=1 到 3 级蝶形运算 %求该级旋转因子下标 Nm，Nm=8,4,2 x=0 2 4 6 0 2 4 6 ; x1=x; m=log2(N); for mm=1:m Nm=2A(m-mm+1); for p=0:Nm

21、:N-1 %循环该级 1 到 2mm-1 组蝶形运算 for k=1:Nm/2 %循环该组 1 到 23-mm 个蝶形运算 9 XX 大学数字信号处理课程设计说明书 kp=k+Nm/2+p; a=x(kp); %确定蝶形运算对应单元下标暂存 x(xp) x(kp)=(x(k+p)-a)*exp(-j*2*pi*(k-1)/Nm); x(k+p)=x(k+p)+a; end end end d=bin2dec(fliplr(dec2bin(0:N-1,m)+1; % 把 0-7 倒序排列 y=x(d) %y=x 序列的倒序， 即 y=X(k) %求 y 幅值%x 恢复成原序列%进行蝶形运算 ma

22、g=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 计算结果) 10 XX 大学数字信号处理课程设计说明书 6 程序运行结果分析 6.1 程序运行结果 首先在 Matlab 中输入源程序，然后保存，选择 Debug 菜单中的 Run 执行程序 如图 6.1: 3 Editor - F八文苕课程设计DSPS程设 File Idit Text Cell Tools D 口 I Z 述那 - 43. - HF

23、O：N- I , - *5 246024 - y=fft (KW) - (y), 呂- subplot (2f 11 1), ? - stK), # Op电亚 Nil-Files vhen Dnp Bre4kp*int F1Z Set-：也 dchfy Condi ti onal Brfeakpo JLELL. Enble/Di E.abl Breakpoint - t itle t 译 - subplot 1卩2). - stenmac), - titleC 8点调用FFT甬 图 6.1 Matlab 界面首先运行程序 1,即直接调用 Matlab 自带的 FFT 函数计算。运行结果如图 所

24、示。y 序列即 X(k)序列为 y =24 0 -8+8i 0 -8 0 -8-8i 0。 30 20 10 0 图 6.2 调用 FFT 函数运行结果 1 11 XX 大学数字信号处理课程设计说明书 然后是用自己编写的 FFT 计算函数，运行得到如图 6.3 所示结果。y 序列即 X(k) 序列为 y =24 0 -8+8i 0 -8 0 -8-8i 0。L. 输入序列工何 8点调用FFT函数计算结果 r- r 6.2 结果分析 通过比较图 6.2 和图 6.3 可以看出，两者的 FFT 结果完全一样，可以证明编写的 FFT 程序正确，达到了课程设计的任务要求。而且本程序不仅可以计算 8 点

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