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

学生姓名： 专业班级： 指导教师： 工作单位：

题 目：8点基于DIF的FFT的实现 初始条件：

具备数字信号处理的理论知识；

具备Matlab编程能力；

熟悉基于DIF的FFT的实现原理； 提供编程所需要的计算机一台

要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等

具体要求）

1、独立编写一个8点的基于DIF的FFT实现程序，不能使用matlab自带的FFT实现函数

2、程序运行结果与matlab自带函数结果进行对比 3、完成符合学校要求的设计说明书 时间安排：

一周，其中3天程序设计，2天程序调试

指导教师签名： 年 月 日

系主任（或责任教师）签名： 年 月 日

XX大学《数字信号处理》课程设计说明书

目录

摘要 ································································································· I 1 Matlab软件简介 ·············································································· 1

1.1 Matlab语言的历史 ··································································· 1 1.2 Matlab软件概况 ······································································ 1 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计算源程序 ······································································· 9 6 程序运行结果分析·········································································· 11

6.1 程序运行结果 ········································································ 11 6.2 结果分析 ·············································································· 12 7 课程设计心得体会·········································································· 13 参考文献 ························································································· 14 致谢 ······························································································· 15

XX大学《数字信号处理》课程设计说明书

摘要

快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法，FFT算法通过利用旋转因子的性质，将一个大点数DFT化成几个小点数DFT，就可以大大减少运算量。DIF-FFT是利用频率抽选的FFT算法，在Matlab中可以通过三重循环语句实现。

关键词：FFT，蝶形运算，倒序排列

I

XX大学《数字信号处理》课程设计说明书

1 Matlab软件简介

1.1 Matlab语言的历史

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

1.2 Matlab软件概况

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

1.3 Matlab的特点

Matlab有以下一些特点：

Matlab的帮助功能很强大，自带有详细的帮助手册，基于HTML的完整的帮助功能，也可以用help命令来得到帮助信息。

程序语法与C语言类似，设计自由度大，方便我们编程。例如在Matlab里，用户无需对变量预定义就可使用。大量数学函数已经定义好，并且有很强的用户自定义函数的能力。

Matlab有高级的程序环境，但程序环境很简单易用，有与其它语言编写的程序结合和输入输出格式化数据的能力；Matlab既具有结构化的控制语句，又有面向对象编程的特性。

还有一个原因使Matlab受人们欢迎的，那就是Matlab源程序具有很大的开放性。除了内部函数以外，所有Matlab的核心文件和工具箱文件都是可读可改的源文件，用户可通过对源文件的修改以及加入自己的文件构成新的工具箱。

1

XX大学《数字信号处理》课程设计说明书

Matlab有强大的的图形绘制功能。在Matlab里，数据可视化的操作非常简单易用。Matlab还有较强的编辑图形界面的能力。可以用来声成图解和可视化的二维、三维图。

Matlab还拥有功能强大的各种工具箱。其工具箱分为两类：功能性工具箱和学科性工具箱。功能性工具箱主要用来扩充其符号计算功能，图示建模仿真功能，文字处理功能以及与硬件实时交互功能。功能性工具箱用于多种学科。而学科性工具箱是专业性比较强的，如（control、signal proceessing 、commumnication） toolbox等。这些工具箱都是由该领域内学术水平很高的专家编写的，所以用户无需编写自己学科范围内的基础程序，而直接进行高，精，尖的研究，能极大地促进我们的学习研究工作。

虽然Matlab有很多优点，但它也有一些缺点，比如：由于Matlab的程序不用编译等预处理，也不生成可执行文件，程序为解释执行，所以速度较慢。

2

XX大学《数字信号处理》课程设计说明书

2 快速傅里叶变换算法分析

2.1 FFT简介

快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法，他在傅里叶变换理论上并没有新的发现，但是却极大的减少了离散傅里叶变换的运算量。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。1965年，库利和图基合作在《Mathematics of Computation》上发表了论文《An Algorithm for the Machine Computation of Complex Fourier Series》，提出了按时抽取的快速傅立叶变换算法，也称库利-图基算法，被视为DSP走向应用的开端。从此，对快速傅里叶变换

算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。

之所以需要快速傅里叶变换，是因为离散傅里叶变换的运算量较大。离散傅里叶变换的公式为：

正变换：X(k)DFT[x(n)]x(n)WN

n0N1nkn=0，1，2…，N-1

1逆变换：x(n)IDFT[x(n)]NX(k)WN n=0，1，2…，N-1

k0N1nk一般情况下WN，x(n)，X（k）都是复序列，计算一个完整的N点DFT需要N2次复数乘法与N-1次复数加法，当N极大时运算量与N2成正比，运算量将过于巨大，不方便应用。而FFT算法通过利用旋转因子的性质，将一个大点数DFT化成几个小点数DFT，就可以大大减少运算量。

2.2 按频率抽选的FFT算法

FFT算法主要有两种，按时间抽选的FFT的算法（DIT-FFT）和按频率抽选的FFT算法（DIF-FFT）。这里主要介绍DIF-FFT。

DIF-FFT算法是将输入序列x（k）分成前后两个部分。

X(k)x(n)WNx(n)WNn0n0N12n0N1nkN12nkx(n)WnN2N1nkNx(n)WNn0N1nkNNk(n)x(n)WN22n0N1[x(n)x(n

NNk/2nk)WN]WN2 3

XX大学《数字信号处理》课程设计说明书

由于WN1，则WNN12n0N/2Nk/2(1)k1k为偶数 

1k为奇数

所以X(k)[x(n)(1)x(nkNnk)]WN 2k为偶数 k2r把k按奇数和偶数分， r=0，1，…N/2-1

k2r1k为奇数

将X（k）分为两部分：X(2r1)[x(n)x(nn0N12Nnrn)]WNWN/2 2X(2r)[x(n)x(nn0N12Nnr)]WN/2 2令x1x(n)x(nNNn)，x2[x(n)x(n)]WN，可得 22N12rnX(2r)x1(n)WN/2n0，r=0，1，2，…，N/2-1 N12rnX(2r1)x2(n)WN/2n0由此可得频率抽选法蝶形运算单元，如图2.1所示

x(n)x1x(n)x(nnWNN)2Nn)]WN2

Nx(n)2x2[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运算流图。

输出序列的排列规律不是从小到大按顺序的，而是按照倒叙规则排序的，即先将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；第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。

第三层循环在该组的各个蝶形运算单元间循环，每组有Nm/2个蝶形运算单元，则循环变量k从1到Nm/2，旋转因子是e2(k1)jNm，每次蝶形运算跨越的行

数是Nm/2，则参加蝶形运算的x值为x(k+p)和x(k+p+Nm/2)。

循环完成后则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,m)也是类似功能。fliplr函数是将一个矩阵左右颠倒，则程

6

XX大学《数字信号处理》课程设计说明书

序中求倒序的语句就是：

d=bin2dec(fliplr(dec2bin([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 程序流程图

开始 设定输入序列 求出蝶形运算级数m=3 循环mm=1到3级蝶形运算 Y 求该级旋转因子下标Nm N

循环该级1到2mm-1组蝶形运算 N Y 循环该组1到23-mm个蝶形运算 N Y 计算一个蝶形运算单元 序列倒序后绘图 结束 图4.1 程序流程图

8

XX大学《数字信号处理》课程设计说明书

5 源程序

5.1 直接调用FFT函数源程序

以下是直接调用Matlab自带的FFT函数计算的源程序，其输入序列为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函数计算结果')

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=2^(m-mm+1);

for p=0:Nm: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恢复成原序列

%进行蝶形运算

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计算结果')

10

XX大学《数字信号处理》课程设计说明书

6 程序运行结果分析

6.1 程序运行结果

首先在Matlab中输入源程序，然后保存，选择Debug菜单中的Run执行程序。如图6.1：

图6.1 Matlab界面

首先运行程序1，即直接调用Matlab自带的FFT函数计算。运行结果如图6.2所示。y序列即X(k)序列为y ={24 0 -8+8i 0 -8 0 -8-8i 0}。

图6.2调用FFT函数运行结果1

11

XX大学《数字信号处理》课程设计说明书

然后是用自己编写的FFT计算函数，运行得到如图6.3所示结果。y序列即X(k)序列为y ={24 0 -8+8i 0 -8 0 -8-8i 0}。

图6.3运行结果2

6.2 结果分析

通过比较图6.2和图6.3可以看出，两者的FFT结果完全一样，可以证明编写的FFT程序正确，达到了课程设计的任务要求。而且本程序不仅可以计算8点FFT，也可以计算N点FFT（N=2m），经测试结果也是正确的。

12

XX大学《数字信号处理》课程设计说明书

7 课程设计心得体会

通过Matlab一周以来的学习研究，我对Matlab有了初步的认识，我掌握了Matlab的基本操作，并学会了用Matlab解决一些电路和数学上的问题，下面是我具体的一些体会

Matlab功能非常强大，几乎可以计算我们目前所遇到的任何问题，不仅可以计算数学问题，也可以用来解决电路等其他学科的各种问题。而且我们可以自编函数，从而可以解决更多样的问题。但以目前我们的知识，只能掌握Matlab的一小部分功能，在以后的学习中，我还需要继续学习Matlab的相关知识。

Matlab虽然功能非常强大，但其操作却非常简单，它的语法类似于我们以前学过的C语言，使我很容易上手，而其语法比C语言更为自由，限制更少，语法类似于自然语言，简洁而智能化，使我可以很容易的编写程序且不容易出错。关于绘图的操作则比C语言简单得多，用几条简单的语句就可以绘出各种曲线、图形，使我们的学习研究变的非常方便。通过本次课程设计我掌握了FFT的编程方法，对FFT有了更深刻的了解。

我认为学习Matlab的关键在于函数，只要掌握了函数的用法，那么就能很快的编出程序。而Matlab的难点也正是函数，因为Matlab拥有大量的函数，仅仅基本的函数就超过七百个，要是算上专业拓展函数那就更多，想在短时间内掌握这么多函数是很难的。我认为应该多练多学，在解决问题的过程中学习并记住所用的函数，有不懂的就查资料，问同学，争取彻底搞懂所作的问题，并牢牢掌握，这样以后就可以独立解决类似问题。

在这次课程设计中，我学到了很多关于Matlab的知识，但这还远远不够，我现在只掌握了一些基本的功能，而解决更高级问题我的知识还不够，我要在日后进一步学习，更好地掌握Matlab。

13

XX大学《数字信号处理》课程设计说明书

参考文献

[1] 刘泉，阙大顺．数字信号处理原理与实现．北京：电子工业出版社，2005． [2] 陈怀琛，吴大正，高西全．Matlab及在电子信息课程中的应用，第三版．北京：电子工业出版社，2006．

[3] 杨高波，元波．精通Matlab 7.0混合编程．北京：电子工业出版社，2006． [4] 陈怀琛．Matlab及其在理工课程中的应用指南．西安：西安电子科技大学出版社，2000．

[5] 张小虹．信号、系统与数字信号处理．北京：机械工业出版社，2004．

14

XX大学《数字信号处理》课程设计说明书

致谢

本次课设的指导老师XXX老师给了我很大帮助，帮助我修订了课程设计说明书，巩固了数字信号处理的相关知识，使我的知识水平有了较大提高。我的数字信号处理老师XX在课堂上认真细致的讲解也使我受益匪浅，在此对他们表示诚挚的谢意。我同组的同学也给了我很多帮助，我们共同努力完成了本次课程设计，在此也对他们表示感谢。

15

本科生课程设计成绩评定表

姓 名 专业 班级 性 别 课程设计题目：8点基于DIF的FFT的实现 课程设计答辩或质疑记录： 成绩评定依据：

指导教师签字：_____________ 年 月 日