DFT与FFT计算速度比较分析.doc

dft与fft计算速度比较分析 摘 要时域分析方法和频域分析方法是信号和系统的分析的两种方法，本文介绍离散信号和系统的频域分析方法，它和连续信号和系统的频域分析方法有所不同，但也有相似之处。本说明书主要是在介绍两种用于信号处理的傅里叶变换算法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=k1时，n2n2log2n，从而，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