DFT与FFT计算速度比较分析(共22页).doc

精选优质文档-倾情为你奉上大神大学课 程 设 计 说 明 书题目： DFT与FFT计算速度比较分析 系 别： 工业自动化仪表 年级专业： 22级仪表1班 学 号： 2 学生姓名： 仪表小子 指导教师： 林大神 赵大神 教师职称： 大神 大神 大神大学课程设计（论文）任务书院（系）： 大神工程学院 基层教学单位： 自动化仪表系 学 号2学生姓名仪表小子专业（班级）22级仪表1班设计题目DFT与FFT计算速度比较分析设计技术参数 用MATLAB实现DFT及FFT对任意长度的序列进行傅里叶变换DFT与FFT的运算时间比较 设计要求利用Matlab或者C语言设计DFT和FFT程序，比较两种频谱分析方法的计算速度，并与理论值进行比较。工作量先对两种算法进行介绍，包括推导过程及运算性质，然后用MATLAB实现两种算法，再分别对两种算法进行运算时间对比，并分析时间长短的原因。工作计划第一周第二周周一 接受任务并查阅资料周二到周五上午学习相关知识 下午编写程序上机调试程序周一到周四上午学习相关知识 下午编写程序上机调试程序编写 任务书参考资料1. 谢平、王娜、林洪斌等，信号处理原理及应用。机械工业出版社，2008.102. 王宏，MATLAB 6.5 及其在信号处理中的应用。清华大学出版社，2004.103. Sanjit K.Mitra 著 孙洪、余翔宇等译，数字信号处理实验指导书。电子工业出版社 2005.1指导教师签字林大神 赵大神基层教学单位主任签字谢大仙说明：此表一式四份，学生、指导教师、基层教学单位、系部各一份。 2011 年 7 月 13 日 大神工程学院课程设计评审意见表指导教师评语： 认真 正确完善 完善 较为合理 合理工作态度 较认真 理论分析 一般 软件设计 一般 不认真 较差 较差平时成绩： 指导教师签字： 年 月 日图面及其它成绩：答辩小组评语： 清晰 正确 基本掌握 优化设计 基本正确原理 了解 不正确 不清楚答辩成绩： 组长签字： 年 月 日课程设计综合成绩：答辩小组成员签字： 年 月 日 专心-专注-专业摘 要时域分析方法和频域分析方法是信号和系统的分析的两种方法，本文介绍离散信号和系统的频域分析方法，它和连续信号和系统的频域分析方法有所不同，但也有相似之处。本说明书主要是在介绍两种用于信号处理的傅里叶变换算法DFT（离散傅里叶变换）和FFT（快速傅里叶变换），分别介绍了这两种运算的推导过程，并且对这两种变换作了简要的介绍，分析了各自的性质。然后通过MATLAB分别实现了这两种傅里叶变换，并对这两种变换进行了运算时间的比较分别对同一函数进行DFT和FFT计算两者的运行时间，并作图比较。本说明书的程序部分都是在MATLAB环境下进行的运算。MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多。在新的版本中也加入了对C，FORTRAN，C+ ，JAVA的支持，可以直接调用,用户也可以将自己编写的实用程序导入到MATLAB函数库中方便自己以后调用。本文介绍了DFT与FFT的原理与Matlab实现程序，以及DFT与FFT的计算速度的比较。并用guide函数亲自编写了一个界面。 关键词：DFT、FFT、Matlab、运算速度、guide目录摘 要1第一章 DFT原理与Matlab实现31.1 DFT的原理31.2 DFT的Matlab实现4第二章 FFT的原理与Matlab实现62.1 FFT的原理62.1.1 FFT的基本思想62.1.2 基2 FFT算法72.2 FFT的Matlab实现9第三章 DFT与FFT计算速度比较分析123.1 FFT与直接计算DFT的比较123.2 FFT与DFT运算时间Matlab程序133.2.1随机序列的DFT计算时间程序133.2.2分析两者运算时间的差异：16第四章 心得体会18参考文献：19第一章 DFT原理与Matlab实现1.1 DFT的原理傅里叶变换就是在以时间为自变量的“信号”与以频率为自变量的“频谱”函数之间的某种变换关系。随时间自变量形式的不同，其傅里叶变换的形式也有不同：周期序列的离散傅里叶级数(DFS)和非周期序列的傅里叶变换(DTFT)，其表示式分别为： (1.1.1) (1.1.2)在实际工作中，当用数字计算机对信号进行频谱分析时，要求信号必须以有限长度的离散值作为输入，而计算所得的频谱值自然也是有限、离散的。上述两种形式的傅里叶变换中，DFS变换满足时、频域自变量的离散化，但其时间变量和频率变量又同时具有周期性；DTFT变换满足时间自变量的有限长度(非周期能量有限信号)，但其频率变量为连续形式。可见，这两种变换都难以实际应用。考虑到DFS变换的时、频域形式虽是周期序列，但每个周期却只有N个独立的复值，知道其一个周期的内容即可得到其它的内容。因此，若从DFS变换的时、频域各取出一个周期，即可构造出时间和频率自变量皆为离散、有限长度的傅氏变换，这就是离散傅里叶变换(DFT)的引出思想，下面进行具体推导。设是一个长度为M的有限长序列，由周期序列与有限长序列的本质联系，可以N()为周期将展开为无重叠的周期序列，即周期延拓为 (1.1.3)再利用式(1.1.1)对进行DFS变换，得到周期离散的频谱，取的主值序列，代入DFS反变换公式(4-3b)，即 (1.1.4)分析可见：在DFS正变换中，只要把一个周期内的乘以对应的，即可得任意k下的；同理，在DFS反变换中，仅用的一个周期的值，即可得到任意n下的。如果同时限制(1.1.1)式中的n和(1.1.4)式中的k，使其都只在区间内取值，就得到了一个周期的和一个周期的间的对应关系 (1.1.5) (1.1.6)式中，N为DFT变换区间的长度，上两式即称为有限长序列的离散傅里叶变换对。(1.1.5)式称为离散傅里叶变换，简称DFT；(1.1.6)式称为离散傅里叶逆变换(Inverse Discrete Fourier Transform)，简称IDFT。1.2 DFT的Matlab实现程序DFT函数：functionxk=dft(xn,N)%计算离散傅里叶变换%-%Xk=dft(xn,N)%Xk=在0<=k<=N-1间的DFT系数数组%xn=N点有限长度序列%N=DFT的长度n=0:1:N-1; %n的行向量k=0:1:N-1; %k的行向量WN=exp(-1i*2*pi/N); %Wn因子nk=n'*k; %产生一个含nk值的N乘N维矩阵WNnk=WN.nk; %DFT矩阵q=xn*WNnk; %DFT系数的行向量对一个单位抽样序列的DFT变换（N=64）：clear all;N=64;x=zeros(1,N);x(1)=1;xn=0:N-1;subplot(121),stem(xn,x);axis(-1 33 0 1.1);XK=dft(xn,N);subplot(122);stem(abs(XK);DFT Matlab处理结果：第二章 FFT的原理与Matlab实现2.1 FFT的原理DFT在数字信号处理中有很重要的作用，如频谱分析、线性卷积等，但由于直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(Fast Fourier Transform,简称FFT)出现前，直接用DFT进行谱分析和信号的实时处理是不切实际的。直到1965年库利(JW Cooley)和图基(JWTukey)提出了DFT运算的一种快速方法以后，情况才发生了根本的变化。多年来，人们不断改进和完善，形成了一系列新型FFT算法，如基2FFT算法、分裂基FFT算法、N为复合数的FFT算法等。必须强调指出：FFT并不是与DFT不同的另外一种变换，而是为减少DFT计算次数的一种快速算法。为了解FFT高效算法的重要及实现思路，先介绍DFT的运算特点，再具体讨论高效算法。2.1.1 FFT的基本思想从哪些方面能改进DFT的运算以减少运算工作量呢? 如前所述，DFT的运算量是与成正比的。显然，如果一个大点数N的DFT能分解为若干小点数DFT的组合，则可达到减少运算工作量的效果。充分利用系数的下列固有周期性和对称性，使DFT运算中的有些项可以合并，从而使长序列的DFT分解为更小点数的DFT，提高运算效率。的对称性 的周期性 快速傅里叶变换算法正是基于上述基本思想而发展起来的。下面介绍最常用的基2 FFT算法(，库利一图基算法)。2.1.2 基2 FFT算法基2 FFT算法主要包括两类：按时间抽取(Decimation-in-time，简称DIT)法和按频率抽取(Decmation-in-Frequence，简称DIF)法，本文只介绍DIT算法。设是列长为的输入序列，且，其中为整数。如果不满足这个条件，可以人为地加入若干零点来达到。将按n的奇偶分成两个子序列 (2.1.1)则(1.1.5)式可化为由于，故上式又可表示为 (2.1.2)其中和分别是及的点的DFT (2.1.3) (2.1.4)(2.1.2)式表明了个N点的DFT被分解为两个点的DFT。但是这里有一个问题，即，的列长为，它们的DFT，的点数也是，即，而却有N个点，所以按(2.1.2)式计算得到的只是 ()的前一半项数的结果，要用来表达全部的值还必须应用W系数的周期性，即这样可得同理可得另外又考虑到的对称性因此，将上述公式代入(2.1.2)中，又可表达为 (2.1.5) (2.1.6)图2.1.1 蝶形运算符号由上分析可见，只要求出区间内各个整数k值所对应的和值，即可求出区间内的全部值，这一点恰恰是FFT能大量节省计算的关键所在。式(2.1.5)、(2.1.6)的运算可用图2.1.1的信号流图符号表示，根据其形状称之为蝶形运算符号。图 2.1.2 N点DIT-DFT运算流图（N=8）依此类推得8点的DIT-FFT的运算流图如下：2.2 FFT的Matlab实现程序FFT函数：function xn=myfft(x)N=length(x);M=log2(N);xtmp=zeros(1,N);value=zeros(1,M);for i=0:N-1 repr=i; for t=1:1:M repr=bitshift(i,1-t); value(t)=bitand(repr,1); end pos=0; for k=1:1:M pos=pos+value(k)*2(M-k); end xtmp(pos+1)=x(i+1);end for i=1:M deepth=2(i-1); width=2(M-i); for t=1:2i:N for k=1:deepth tmp=xtmp(t+k-1); wn=width*(k-1); xtmp(t+k-1)=tmp+exp(-j*2*pi*wn/N)*xtmp(t+k+deepth-1); xtmp(t+k+deepth-1)=tmp-exp(-j*2*pi*wn/N)*xtmp(t+k+deepth-1); end endendxn=xtmp;对一个单位抽样序列的FFT变换（N=64）：clear all;N=64;x=zeros(1,N);x(1)=1;xn=0:N-1;subplot(121),stem(xn,x);axis(-1 33 0 1.1);XK=fft(xn);subplot(122);stem(abs(XK);FFT Matlab处理结果 第三章 DFT与FFT计算速度比较分析3.1 FFT与直接计算DFT的比较对于N点的DFT，需要计算的复数乘法和复数加法次数分别是N²和N(N-1)。由前面介绍的按时间抽取的FFT运算流图可见，每一级都由个蝶形运算构成。因此每一级运算都需要次复乘和N次复加(每个结加减各一次)。这样m级运算总共需要复乘数 复加数 FFT计算量与DFT计算量比较NDFTFFTDFT的乘法次数与FFT的乘法次数之比DFT的加法次数与FFT加法次数之比复数乘法次数复数加法次数复数乘法次数复数加法次数2421241416124841.58645612245.32.31625624032648.03.753210249928016012.86.2644096403219238421.310.5128163841625644889636.618.125665536652801024204864.031.951223044608113.856.81024512010240204.8102.320481126422528372.4186.140962457649152682.7341.38192532481260.3630.03.2 FFT与DFT运算时间Matlab程序3.2.1随机序列的DFT计算时间程序Guide 程序下的主函数set(handles.TITLE,'string','calculating.');Nmax=str2num(get(handles.N,'string'); axes(handles.FFT_axes) cla; axes(handles.DFT_axes) cla;fft_time=zeros(1,Nmax);for n=1:1:Nmax x=rand(1,n); t=clock; my_fft(x); fft_time(n)=etime(clock,t);end n=1:1:Nmax; axes(handles.FFT_axes) plot(n,fft_time,'.'); xlabel('N'); ylabel('时间 (单位:秒)') title('FFT执行时间')my_dft_time=zeros(1,Nmax);for n=1:1:Nmax x=rand(1,n); t=clock; my_dft(x,n); my_dft_time(n)=etime(clock,t);end n=1:1:Nmax; axes(handles.DFT_axes) plot(n,my_dft_time,'.'); xlabel('N'); ylabel('时间 (单位:秒) ')title(' DFT执行时间')set(handles.TITLE,'string','DFT_AND_FFT_TIME');3.2.2 Matlab实验结果：Guide程序界面运行结果Nmax =128Nmax =512N=1024N=20483.2.2分析两者运算时间的差异：由前面介绍的按时间抽取的FFT运算流图可见，每一级都由个蝶形运算构成。因此每一级运算都需要次复乘和N次复加(每个结加减各一次)。这样m级运算总共需要复乘数 (4.3.45)复加数 (4.3.46)实际计算量和这个数字稍有出入，因为由运算流图可见，这种情况共有次，这几个系数是都不用乘法运算的，但这种情况在直接计算DFT中也是有的，且当N较大时，这些影响也较小。所以为了统一作比较我们不考虑以上特例。综上所述，可以得出如下结论；按时间抽取法所需的复乘数和复加数都是与成正比的，而直接计算DFT时所需的复乘数为，复数加为N(N-1)次。当N>1时，从而，DIT-FFT算法比直接计算DFT的运算次数大大减小。例如时，0641282565121024641282565121024DFT算法FFT算法乘法次数(×1000)N(取样点数)图 3.2.2 FFT算法与直接计算DFT所需乘法次数的比较曲线这样，就使运算效率提高200多倍。图4.3.16为FFT算法和直接DFT算法所需运算量与计算点数N的关系曲线。由此图更加直观地看出FFT算法的优越性，显然，N越大时，优越性就越明显。随着运算次数的减少，FFT的运算时间明显减少。第四章 心得体会紧张而又兴奋的两周数字信号处理课程设计，令我成长很多。先在图书馆里查找了相关的书籍，如MATLAB类的编程书籍，各类信号处理类的书籍等，即丰富了自己的知识范围，又对与自己所学的知识有了更深的了解和认识，同时也对它的应用有了一个大体的认识。两周的课程设计，从拿到题目分析题目到编制相应程序、调试程序，其间的确遇到了不少难题，但通过老师的耐心辅导、与同组成员的互相讨论，终于将问题各个击破，完成了此次课设要求。在设计的过程中，我深刻认识到了自己所学知识的不足。这也让我再次认识到知识是无尽的，只有不断的充实自己、完善自己的知识理论体系，才能够更好的胜任自己以后的工作。在整个课程设计的过程中，我得到了其他其他同学的帮助，也帮助其他小组分析设计题目，不仅扩展大了自己的锻炼空间，也加强了我与其他同学合作的能力。查找资料的过程中我也增强自己学习的能力。真真正正的提高了我遇到问题分析问题解决问题的能力。这些都是我在以后的学习、生活和工作中的宝贵财富。参考文献：1. 谢平、王娜、林洪斌等，信号处理原理及应用。机械工业出版社，2008.102. 王宏，MATLAB 6.5 及其在信号处理中的应用。清华大学出版社，2004.103. Sanjit K.Mitra 著 孙洪、余翔宇等译，数字信号处理实验指导书。电子工业出版社 2005.14. 薛年喜，MATLAB在数字信号处理中的应用（第二版）。清华大学出版社，2008.15. 陈亚勇等，MATLAB信号处理详解。人民邮电出版社，2001.6