8点基于DIT的FFT的实现

课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目：8点基于DIT的FFT的实现初始条件：具备Matlab编程能力；熟悉基于DIT的FFT的实现原理；提供编程所需要的计算机一台。要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、编写一个8点的基于DIT的FFT函数，不能使用matlab自带的FFT实现函数；2、并调用该函数实现16点的FFT运算，用matlab自带函数对运行结果进行验证；3、完成符合学校要求的设计说明书。时间安排：一周，其中3天程序设计，2天程序调试指导教师签名：年月日系主任（或责任教师）签名：年月日目录摘要..............................................................................................................................IAbstract.........................................................................................................................II1概述............................................................................................................................11.1快速傅立叶变换(FFT)简介...........................................................................11.2MATLAB简介................................................................................................22直接计算DFT的问题及改进..................................................................................42.1直接计算DFT的运算量...............................................................................42.2改进措施.........................................................................................................53按时间抽选的基-2FFT算法（DIT-FFT)................................................................63.1DIT-FFT算法原理..........................................................................................63.2DIT-FFT的运算量........................................................................................133.3DIT-FFT算法的特点....................................................................................143.4N=16时的DIT-FFT算法.............................................................................164MATLAB程序代码.................................................................................................184.1N=8点DIT-FFT代码...................................................................................184.2N=16点DIT-FFT代码.................................................................................195MATLAB仿真结果及验证.....................................................................................205.1DIT-FFT函数调试........................................................................................205.2DIT-FFT函数运行结果................................................................................215.3调用系统函数验证........................................................................................226心得体会..................................................................................................................247参考文献..................................................................................................................25武汉理工大学《信号分析与处理》课程设计说明书I摘要此次课程设计的目的是利用MATLAB实现8点基于DIT的FFT的仿真，不使用MATLAB自带的FFT实现函数。本文先就直接计算傅立叶变换（DFT）存在的问题进行讨论，之后详细介绍了快速傅立叶变换（FFT）的原理以及推导过程，给出了8点FFT的蝶形流图以及MATLAB仿真的程序代码，并通过调用该函数代码计算16点的FFT。最后给出了仿真调试结果和此次课程设计的总结。关键词：FFTMATLAB仿真武汉理工大学《信号分析与处理》课程设计说明书IIAbstractTheaimofthisCourseDesignistouseMATLABtoachieve8-pointDIT-FFTsimulation,andcannotusethebuilt-inMATLABFFTfunctiontorealize.ThebeginningofthisarticlediscusstheproblemsofdirectcalculationoftheFouriertransform(DFT),andthenintroducestheprincipleofFastFourierTransform(FFT)andtheprocessofderivation.Thenthereisgivenbutterflyflowdiagramof8-pointFFTandtheMATLABsimulationprogramcode,andrealize16-pointFFTcalculationbycallingthefunctioncode.Finally,enumeratethesimulationresultsandmakethesummaryofthiscurriculumdesign.Keywords:FFTMATLABSimulation武汉理工大学《信号分析与处理》课程设计说明书11概述1.1快速傅立叶变换(FFT)简介傅立叶变换，表示能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。傅立叶变换是一种分析信号的方法，它可分析信号的成分，也可用这些成分合成信号。傅立叶变换是声学、语音、电信和信号处理等领域中一种重要的分析工具。在不同的研究领域，傅立叶变换具有多种不同的变体形式，如连续傅立叶变换和离散傅立叶变换。离散傅立叶变换（DFT），是傅立叶变换在时域和频域上都呈现离散的形式，将时域信号的采样变换为在离散时间傅立叶变换（DTFT）频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作经过周期延拓成为周期信号再作变换。有限长序列可以通过离散傅立叶变换(DFT）将其频域也离散化成有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅立叶变换(FFT)。1965年，Cooley和Tukey提出了计算离散傅立叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅立叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。FFT在离散傅立叶反变换、线性卷积和线性相关等方面也有重要应用。计算离散傅立叶变换的快速方法，有按时间抽取的FFT算法（DIT-FFT）和按频率抽取的FFT算法（DIF-FFT)。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。它们都借助于的两个特点：一是周期性；二是对称性。这样，便可以把离散傅立叶变换的计算分成若干步进行，计算效率大为提高。快速傅立叶变换（FFT），是离散傅立叶变换的快速算法，它是根据离散傅立叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。武汉理工大学《信号分析与处理》课程设计说明书2它对傅立叶变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。1.2MATLAB简介MATLAB是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。MATLAB是matrix&laboratory两个词的组合，意为矩阵工厂（矩阵实验室）。是由美国MathWorks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且MATLAB也吸收了像Maple等软件的优点，使MATLAB成为一个强大的数学软件。在新的版本中也加入了对C，FORT