DFT与FFT计算速度比较分析

大神大学课程设计说明书题目：DFT与FFT计算速度比较分析系别：工业自动化仪表年级专业：22级仪表1班学号：222222222222学生姓名：仪表小子指导教师：林大神赵大神教师职称：大神大神大神大学课程设计（论文）任务书院（系）：大神工程学院基层教学单位：自动化仪表系学号222222222222学生姓名仪表小子专业（班级）22级仪表1班设计题目DFT与FFT计算速度比较分析设计技术参数用MATLAB实现DFT及FFT对任意长度的序列进行傅里叶变换DFT与FFT的运算时间比较设计要求利用Matlab或者C语言设计DFT和FFT程序，比较两种频谱分析方法的计算速度，并与理论值进行比较。工作量先对两种算法进行介绍，包括推导过程及运算性质，然后用MATLAB实现两种算法，再分别对两种算法进行运算时间对比，并分析时间长短的原因。工作计划第一周第二周周一接受任务并查阅资料周二到周五上午学习相关知识下午编写程序上机调试程序周一到周四上午学习相关知识下午编写程序上机调试程序编写任务书参考资料1.谢平、王娜、林洪斌等，信号处理原理及应用。机械工业出版社，2008.102.王宏，MATLAB6.5及其在信号处理中的应用。清华大学出版社，2004.103.SanjitK.Mitra著孙洪、余翔宇等译，数字信号处理实验指导书。电子工业出版社2005.1指导教师签字林大神赵大神基层教学单位主任签字谢大仙说明：此表一式四份，学生、指导教师、基层教学单位、系部各一份。2011年7月13日大神工程学院课程设计评审意见表指导教师评语：认真正确完善完善较为合理合理工作态度较认真理论分析一般软件设计一般不认真较差较差平时成绩：指导教师签字：年月日图面及其它成绩：答辩小组评语：清晰正确基本掌握优化设计基本正确原理了解不正确不清楚答辩成绩：组长签字：年月日课程设计综合成绩：答辩小组成员签字：年月日大神大学课程设计说明书共14页第1页摘要时域分析方法和频域分析方法是信号和系统的分析的两种方法，本文介绍离散信号和系统的频域分析方法，它和连续信号和系统的频域分析方法有所不同，但也有相似之处。本说明书主要是在介绍两种用于信号处理的傅里叶变换算法——DFT（离散傅里叶变换）和FFT（快速傅里叶变换），分别介绍了这两种运算的推导过程，并且对这两种变换作了简要的介绍，分析了各自的性质。然后通过MATLAB分别实现了这两种傅里叶变换，并对这两种变换进行了运算时间的比较——分别对同一函数进行DFT和FFT计算两者的运行时间，并作图比较。本说明书的程序部分都是在MATLAB环境下进行的运算。MATLAB是矩阵实验室（MatrixLaboratory）的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多。在新的版本中也加入了对C，FORTRAN，C++，JAVA的支持，可以直接调用,用户也可以将自己编写的实用程序导入到MATLAB函数库中方便自己以后调用。本文介绍了DFT与FFT的原理与Matlab实现程序，以及DFT与FFT的计算速度的比较。并用guide函数亲自编写了一个界面。关键词：DFT、FFT、Matlab、运算速度、guide大神大学课程设计说明书共14页第2页目录摘要.....................................................................................................................................1第一章DFT原理与Matlab实现.............................................................................................31.1DFT的原理...................................................................................................................31.2DFT的Matlab实现.....................................................................................................4第二章FFT的原理与Matlab实现..........................................................................................62.1FFT的原理...................................................................................................................62.1.1FFT的基本思想.............................................................................................62.1.2基2FFT算法.................................................................................................72.2FFT的Matlab实现......................................................................................................9第三章DFT与FFT计算速度比较分析................................................................................123.1FFT与直接计算DFT的比较....................................................................................123.2FFT与DFT运算时间Matlab程序...........................................................................133.2.1随机序列的DFT计算时间程序.....................................................................133.2.2分析两者运算时间的差异：..........................................................................16第四章心得体会.....................................................................................................................18参考文献：...............................................................................................................................19大神大学课程设计说明书共14页第3页第一章DFT原理与Matlab实现1.1DFT的原理傅里叶变换就是在以时间为自变量的“信号”与以频率为自变量的“频谱”函数之间的某种变换关系。随时间自变量形式的不同，其傅里叶变换的形式也有不同：周期序列的离散傅里叶级数(DFS)和非周期序列的傅里叶变换(DTFT)，其表示式分别为：210DFSNjnkNnXkxnxne(1.1.1)()DTFT[()]()jjnnXexnxne(1.1.2)在实际工作中，当用数字计算机对信号进行频谱分析时，要求信号必须以有限长度的离散值作为输入，而计算所得的频谱值自然也是有限、离散的。上述两种形式的傅里叶变换中，DFS变换满足时、频域自变量的离散化，但其时间变量和频率变量又同时具有周期性；DTFT变换满足时间自变量的有限长度(非周期能量有限信号)，但其频率变量为连续形式。可见，这两种变换都难以实际应用。考虑到DFS变换的时、频域形式虽是周期序列，但每个周期却只有N个独立的复值，知道其一个周期的内容即可得到其它的内容。因此，若从DFS变换的时、频域各取出一个周期，即可构造出时间和频率自变量皆为离散、有限长度的傅氏变换，这就是离散傅里叶变换(DFT)的引出思想，下面进行具体推导。设xn是一个长度为M的有限长序列，由周期序列与有限长序列的本质联系，可以N(NM)为周期将xn展开为无重叠的周期序列，即周期延拓为rxnxnrN(1.1.3)再利用式(1.1.1)对xn进行DFS变换，得到周期离散的频谱Xk((,))k，取大神大学课程设计说明书共14页第4页Xk的主值序列(0,1,...,1)kN，代入DFS反变换公式(4-3b)，即2101NjknNkxnIDFSXkXkeN(1.1.4)分析可见：在DFS正变换中，只要把一个周期内的nx~乘以对应的2jnkNe(0,1,...,1)nN，即可得任意k下的kX~；同理，在DFS反变换中，仅用kX~的一个周期的值(0,1,...,1)kN，即可得到任意n下的nx~。如果同时限制(1.1.1)式中的n和(1.1.4)式中的k，使其都只在1~0N区间内取值，就得到了一个周期的nx和一个周期的kX间的对应关系10NnknNWnxkX10Nk(1.1.5)101NkknNWkXNnx10Nn(1.1.6)式中，2jNNWe，N为DFT变换区间的长度，上两式即称为有限长序列的离散傅里叶变换对。(1.1.5)式称为离散傅里叶变换，简称DFT；(1.1.6)式称为离散傅里叶逆变换(InverseDiscreteFourierTransform)，简称IDFT。1.2DFT的Matlab实现程序DFT函数：function[xk]=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的行向量大神大学课程设计说明书共14页第5页WN=exp(-1i*2*pi/N);%Wn因子nk=n'*k;%产生一个含nk值的N乘N维矩阵WNnk=WN.^nk;%DFT矩阵q=xn*WNnk;%DFT系数的行向量对一个单位抽样序列的DFT变换（N=64）：clearall;N=64;x=zeros(1,N);x(1)=1;xn=0:N-1;subplot(121),stem(xn,x);axis([-13301.1]);XK=dft(xn,N);subplot(122);stem(abs(XK));DFTMatlab处理结果：大神大学课程设计说明书共14页第6页第二章FFT的原理与Matlab实现2.1FFT的原理DFT在数字信号处理中有很重要的作用，如频谱分析、线性卷积等