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. 王宏，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)210DFSNjnkNnXkxxe(1.1.2)()T()()j jnnexxe 在实际工作中，当用数字计算机对信号进行频谱分析时，要求信号必须以有限长度的离散值作为输入，而计算所得的频谱值自然也是有限、离散的。上述两种形式的傅里叶变换中，DFS 变换满足时、频域自变量的离散化，但其时间变量和频率变量又同时具有周期性；DTFT 变换满足时间自变量的有限长度(非周期能量有限信号) ，但其频率变量为连续形式。可见，这两种变换都难以实际应用。考虑到 DFS 变换的时、频域形式虽是周期序列，但每个周期却只有 N 个独立的复值，知道其一个周期的内容即可得到其它的内容。因此，若从 DFS 变换的时、频域各取出一个周期，即可构造出时间和频率自变量皆为离散、有限长度的傅氏变换，这就是离散傅里叶变换(DFT)的引出思想，下面进行具体推导。设 是一个长度为 M 的有限长序列，由周期序列与有限长序列的本质联系，可xn以 N( )为周期将 展开为无重叠的周期序列，即周期延拓为Nxn(1.1.3)rxnxnrN再利用式(1.1.1)对 进行 DFS 变换，得到周期离散的频谱 ， Xk(,)取 的主值序列 ，代入 DFS 反变换公式 (4-3b)，即Xk(0,1.)kN(1.1.4)210NjknNkxnIDFSXXe分析可见：在 DFS 正变换中，只要把一个周期内的 乘以对应的x2jnkNe，即可得任意 k 下的 ；同理，在 DFS 反变换中，仅用 的一个周(0,1.)nNX期的值 ，即可得到任意 n 下的 。如果同时限制(1.1.1) 式中的 n 和,.1k(1.1.4)式中的 k，使其都只在 区间内取值，就得到了一个周期的 和一个10Nx周期的 间的对应关系X(1.1.5)10NnknNWxkX 10Nk(1.1.6)kkx n式中， ，N 为 DFT 变换区间的长度，上两式即称为有限长序列的离散2jNWe傅里叶变换对。(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 年库利(J W Cooley)和图基(JWTukey)提出了 DFT 运算的一种快速方法以后，情况才发生了根本的变化。多年来，人们不断改进和完善，形成了一系列新型 FFT 算法，如基 2FFT 算法、分裂基 FFT 算法、N 为复合数的 FFT 算法等。必须强调指出：FFT 并不是与 DFT 不同的另外一种变换，而是为减少 DFT 计算次数的一种快速算法。为了解 FFT 高效算法的重要及实现思路，先介绍 DFT 的运算特点，再具体讨论高效算法。2.1.1 FFT 的基本思想从哪些方面能改进 DFT 的运算以减少运算工作量呢? 如前所述，DFT 的运算量是与 成正比的。显然，如果一个大点数 N 的 DFT 能分解为若干小点数 DFT 的组合，2N则可达到减少运算工作量的效果。充分利用系数 的下列固有周期性和对称性，使nkWDFT 运算中的有些项可以合并，从而使长序列的 DFT 分解为更小点数的 DFT，提高运算效率。的对称性 nkNWknNknNnNk的周期性 WW快速傅里叶变换算法正是基于上述基本思想而发展起来的。下面介绍最常用的基 2 FFT 算法 ( ，库利一图基算法 )。2mN2.1.2 基 2 FFT 算法基 2 FFT 算法主要包括两类：按时间抽取(Decimation-in-time，简称 DIT)法和按频率抽取(Decmation-in-Frequence，简称 DIF)法，本文只介绍 DIT 算法。设 是列长为 的输入序列，且 ，其中 为整数。如果nx1,0Nn 2mN不满足这个条件，可以人为地加入若干零点来达到。将 按 n 的奇偶分成两个子序列x(2.1.1)rxr21 12,0r则(1.1.5)式可化为 11NNnk nkNnXkDFTxxWxW偶 数 奇 数N21N212120 0N21 N212 20 0rkrk Nr rk