DFT与FFT计算速度比较分析

《DFT与FFT计算速度比较分析》由会员分享，可在线阅读，更多相关《DFT与FFT计算速度比较分析（20页珍藏版）》请在装配图网上搜索。

1、 DFT与FFT计算速度比较分析 摘 要时域分析方法和频域分析方法是信号和系统的分析的两种方法，本文介绍离散信号和系统的频域分析方法，它和连续信号和系统的频域分析方法有所不同，但也有相似之处。本说明书主要是在介绍两种用于信号处理的傅里叶变换算法DFT（离散傅里叶变换）和FFT（快速傅里叶变换），分别介绍了这两种运算的推导过程，并且对这两种变换作了简要的介绍，分析了各自的性质。然后通过MATLAB分别实现了这两种傅里叶变换，并对这两种变换进行了运算时间的比较分别对同一函数进行DFT和FFT计算两者的运行时间，并作图比较。本说明书的程序部分都是在MATLAB环境下进行的运算。MATLAB是矩阵实验

2、室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多。在新的版本中也加入了对C，FORTRAN，C+ ，JAVA的支持，可以直接调用,用户也可以将自己编写的实用程序导入到MATLAB函数库中方便自己以后调用。本文介绍了DFT与FFT的原理与Matlab实现程序，以及DF

3、T与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

4、第四章 心得体会18参考文献：19第一章 DFT原理与Matlab实现1.1 DFT的原理傅里叶变换就是在以时间为自变量的“信号”与以频率为自变量的“频谱”函数之间的某种变换关系。随时间自变量形式的不同，其傅里叶变换的形式也有不同：周期序列的离散傅里叶级数(DFS)和非周期序列的傅里叶变换(DTFT)，其表示式分别为： (1.1.1) (1.1.2)在实际工作中，当用数字计算机对信号进行频谱分析时，要求信号必须以有限长度的离散值作为输入，而计算所得的频谱值自然也是有限、离散的。上述两种形式的傅里叶变换中，DFS变换满足时、频域自变量的离散化，但其时间变量和频率变量又同时具有周期性；DTFT变换

5、满足时间自变量的有限长度(非周期能量有限信号)，但其频率变量为连续形式。可见，这两种变换都难以实际应用。考虑到DFS变换的时、频域形式虽是周期序列，但每个周期却只有N个独立的复值，知道其一个周期的内容即可得到其它的内容。因此，若从DFS变换的时、频域各取出一个周期，即可构造出时间和频率自变量皆为离散、有限长度的傅氏变换，这就是离散傅里叶变换(DFT)的引出思想，下面进行具体推导。设是一个长度为M的有限长序列，由周期序列与有限长序列的本质联系，可以N()为周期将展开为无重叠的周期序列，即周期延拓为 (1.1.3)再利用式(1.1.1)对进行DFS变换，得到周期离散的频谱，取的主值序列，代入DFS

6、反变换公式(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的

7、Matlab实现程序DFT函数：functionxk=dft(xn,N)%计算离散傅里叶变换%-%Xk=dft(xn,N)%Xk=在0=k1时，从而，DIT-FFT算法比直接计算DFT的运算次数大大减小。例如时，0641282565121024641282565121024DFT算法FFT算法乘法次数(1000)N(取样点数)图 3.2.2 FFT算法与直接计算DFT所需乘法次数的比较曲线这样，就使运算效率提高200多倍。图4.3.16为FFT算法和直接DFT算法所需运算量与计算点数N的关系曲线。由此图更加直观地看出FFT算法的优越性，显然，N越大时，优越性就越明显。随着运算次数的减少，FFT

8、的运算时间明显减少。第四章 心得体会紧张而又兴奋的两周数字信号处理课程设计，令我成长很多。先在图书馆里查找了相关的书籍，如MATLAB类的编程书籍，各类信号处理类的书籍等，即丰富了自己的知识范围，又对与自己所学的知识有了更深的了解和认识，同时也对它的应用有了一个大体的认识。两周的课程设计，从拿到题目分析题目到编制相应程序、调试程序，其间的确遇到了不少难题，但通过老师的耐心辅导、与同组成员的互相讨论，终于将问题各个击破，完成了此次课设要求。在设计的过程中，我深刻认识到了自己所学知识的不足。这也让我再次认识到知识是无尽的，只有不断的充实自己、完善自己的知识理论体系，才能够更好的胜任自己以后的工作。

9、在整个课程设计的过程中，我得到了其他其他同学的帮助，也帮助其他小组分析设计题目，不仅扩展大了自己的锻炼空间，也加强了我与其他同学合作的能力。查找资料的过程中我也增强自己学习的能力。真真正正的提高了我遇到问题分析问题解决问题的能力。这些都是我在以后的学习、生活和工作中的宝贵财富。参考文献：1. 谢平、王娜、林洪斌等，信号处理原理及应用。机械工业出版社，2008.102. 王宏，MATLAB 6.5 及其在信号处理中的应用。清华大学出版社，2004.103. Sanjit K.Mitra 著 孙洪、余翔宇等译，数字信号处理实验指导书。电子工业出版社 2005.14. 薛年喜，MATLAB在数字信号处理中的应用（第二版）。清华大学出版社，2008.15. 陈亚勇等，MATLAB信号处理详解。人民邮电出版社，2001.6