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

课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目：8点基于DIF的FFT的实现初始条件：具备数字信号处理的理论知识；具备Matlab编程能力；熟悉基于DIF的FFT的实现原理；提供编程所需要的计算机一台要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、独立编写一个8点的基于DIF的FFT实现程序，不能使用matlab自带的FFT实现函数2、程序运行结果与matlab自带函数结果进行对比3、完成符合学校要求的设计说明书时间安排：一周，其中3天程序设计，2天程序调试指导教师签名：年月日系主任（或责任教师）签名：年月日XX大学《数字信号处理》课程设计说明书目录摘要·································································································I1Matlab软件简介··············································································11.1Matlab语言的历史···································································11.2Matlab软件概况······································································11.3Matlab的特点··········································································12快速傅里叶变换算法分析·································································32.1FFT简介················································································32.2按频率抽选的FFT算法····························································33程序设计·······················································································63.1程序设计思路·········································································63.2要使用的Matlab函数·······························································64程序流程图····················································································85源程序··························································································95.1直接调用FFT函数源程序·························································95.2FFT计算源程序·······································································96程序运行结果分析··········································································116.1程序运行结果········································································116.2结果分析··············································································127课程设计心得体会··········································································13参考文献·························································································14致谢·······························································································15XX大学《数字信号处理》课程设计说明书I摘要快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法，FFT算法通过利用旋转因子的性质，将一个大点数DFT化成几个小点数DFT，就可以大大减少运算量。DIF-FFT是利用频率抽选的FFT算法，在Matlab中可以通过三重循环语句实现。关键词：FFT，蝶形运算，倒序排列XX大学《数字信号处理》课程设计说明书11Matlab软件简介1.1Matlab语言的历史70年代后期,身为美国NewMexico大学计算机系系主任的CleveMoler发现学生用FORTRAN编写接口程序很费时间,于是他开始自己动手,利用业余时间为学生编写EISPACK和LINPACK的接口程序。CleveMoler给这个接口程序取名为Matlab。1984年，为了推广Matlab在数值计算中的应用，CleveMoler、JohonLittle等正式成立了Mathworks公司，从而把Matlab推向市场，并开始了对Matlab工具相等的开发设计。1.2Matlab软件概况Matlab是MatrixLaboratory的缩写，意为矩阵实验室。它具有强大的矩阵处理功能和绘图功能，进还能进行文字处理，绘图，建模仿真等功能。随着版本的不断升级，它在数值计算及符号计算功能上得到了进一步完善。Matlab已经发展成为多学科、多种工作平台的功能强大的大型软件。在欧美等高校，Matlab已经成为线性代数、自动控制理论、概率论及数理统计、数字信号处理、时间序列分析、动态系统仿真等高级课程的基本教学工具。1.3Matlab的特点Matlab有以下一些特点：Matlab的帮助功能很强大，自带有详细的帮助手册，基于HTML的完整的帮助功能，也可以用help命令来得到帮助信息。程序语法与C语言类似，设计自由度大，方便我们编程。例如在Matlab里，用户无需对变量预定义就可使用。大量数学函数已经定义好，并且有很强的用户自定义函数的能力。Matlab有高级的程序环境，但程序环境很简单易用，有与其它语言编写的程序结合和输入输出格式化数据的能力；Matlab既具有结构化的控制语句，又有面向对象编程的特性。还有一个原因使Matlab受人们欢迎的，那就是Matlab源程序具有很大的开放性。除了内部函数以外，所有Matlab的核心文件和工具箱文件都是可读可改的源文件，用户可通过对源文件的修改以及加入自己的文件构成新的工具箱。XX大学《数字信号处理》课程设计说明书2Matlab有强大的的图形绘制功能。在Matlab里，数据可视化的操作非常简单易用。Matlab还有较强的编辑图形界面的能力。可以用来声成图解和可视化的二维、三维图。Matlab还拥有功能强大的各种工具箱。其工具箱分为两类：功能性工具箱和学科性工具箱。功能性工具箱主要用来扩充其符号计算功能，图示建模仿真功能，文字处理功能以及与硬件实时交互功能。功能性工具箱用于多种学科。而学科性工具箱是专业性比较强的，如（control、signalproceessing、commumnication）toolbox等。这些工具箱都是由该领域内学术水平很高的专家编写的，所以用户无需编写自己学科范围内的基础程序，而直接进行高，精，尖的研究，能极大地促进我们的学习研究工作。虽然Matlab有很多优点，但它也有一些缺点，比如：由于Matlab的程序不用编译等预处理，也不生成可执行文件，程序为解释执行，所以速度较慢。XX大学《数字信号处理》课程设计说明书32快速傅里叶变换算法分析2.1FFT简介快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法，他在傅里叶变换理论上并没有新的发现，但是却极大的减少了离散傅里叶变换的运算量。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。1965年，库利和图基合作在《MathematicsofComputation》上发表了论文《AnAlgorithmfortheMachineComputationofComplexFourierSeries》，提出了按时抽取的快速傅立叶变换算法，也称库利-图基算法，被视为DSP走向应用的开端。从此，对快速傅里叶变换算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。之所以需要快速傅里叶变换，是因为离散傅里叶变换的运算量较大。离散傅里叶变换的公式为：正变换：WnkNNnnxnxDFTkX)()]([)(10n=0，1，2…，N-1逆变换：WnkNNkkXNnxIDFTnx)(1)]([)(10n=0，1，2…，N-1一般情况下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）分成前后两个部分。])2()([)2()()()()()(2/120)2(10101212010XX大学《数字信号处理》课程设计说明书4由于12/WNN，则11)1(2/kNkNW所以WnkNkNnNnxnxkX)]2()([)()1(120把k按奇数和偶数分，122rkrkr=0，1，…N/2-1将X（k）分为两部分：WWrnNnNNnNnxnxrX2/120)]2()([)12(WnrNNnNnxnxrX2/120)]2()([)2(令)2()(1Nnxnxx，WnNNnxnxx)]2()([2，可得WWrnNNnrnNNnnxrXnxrX2/21202/1120)()12()()2(，r=0，1，2，…，N/2-1由此可得频率抽选法蝶形运算单元，如图2.1所示图2.1频率抽选法蝶形运算单元这样可以把一个N点DFT分解为两个N/2点DFT的组合，两个N/2点DFT还可以继续分解，设N=2M，则经过M-1次分解，最后可以分解成为N/2个两点DFT，可以由一个蝶形运算来求解。例如8点DIF-FFT蝶形运算图如图2.2)2()(1NnxnxxWnNNnxnxx)]2()([2nNW)(nx)2(Nnxk为偶数k为奇数k为偶数k为奇数XX大学《数字信号处理》课程设计说明书5图2.28点DIF-FFT运算流图。输出序列的排列规律不是从小到大