数字信号处理课程设计-DFT的快速算法.doc

燕 山 大 学 课 程 设 计 说 明 书摘要在数字信号处理中，有限长序列占有很重要的地位，其频域分析方法既有Z变换也有序列的傅里叶变换，但ZT与DTFT的共同特点是：它们的频域变换函数都是连续函数，不适于计算机或数字处理。因此我们将介绍一种更为重要的数学的变换离散傅立叶变换（Discrete Fourier Transfor，简称DFT），其实质是有限长序列傅立叶变换的有限点离散采样，从而开辟了频域离散化的道路，是数字信号处理可以在频域采用数字运算的方法进行，从而大大增加了数字信号处理的灵活性，同时也奠定了DFT在信号处理中的核心地位。在此基础上，介绍了DFT的快速算法。由于直接计算DFT的计算量当N很大是会很大，所以在快速傅立叶便换（Fast Fourier Transfor，简称FFT）出现前，直接进行谱分析和信号的实时处理是不切实际的。直到1965年库利和图基提出了DFT运算的一种快速方法以后，情况才发生了根本的变化。FFT使得信号的实时处理和设备的简化得以实现。关键字 DFT FFT 算法比较 MATLAB目录 第一章 DFT原理与实现程序3第二章 FFT原理及实现程序4第三章 DFT与FFT的比较8心得体会12参考文献12第一章 DFT原理与实现程序一、DFT的引出思想 有限长序列x(n)的频域分析方法： 1、DTFT: 2、z变换 二者共同特点：频域变换函数 或 是连续函数，不适于计算机计算或数字处理。计算机处理要求：时域、频域都为有限长、离散形式。 观察DFS公式: 时域、频域离散。 因此，构造DFT从DFS的时域和频域中各取出一个周期。二、DFT的定义 设x（n) 是一个长度为M的有限长序列，则定义的N点离散傅立叶变换为其逆变换为：式中 ， N为DFT变换区间长度。三、DFT实现程序及应用举例DFT函数和对一单位抽样序列进行DFT处理的程序及结果：functionXk=dft(xn,N)n=0:1:N-1;k=0:1:N-1;WN=exp(-j*2*pi/N);nk=n*k;WNnk=WN.nk;Xk=xn*WNnk;clear all;N=32;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);第二章 FFT原理及实现程序离散傅立叶变换的快速算法根据基数的不同可以分为多种方法，其中基2FFT算法最为常用，基2FFT算法主要包括两类：按时间抽取（decimation-in-time，简称DIT）法和按频率抽取（decimation-in-frequence，简称DIF）法，这里主要介绍按时间抽取基2 算法。1、算法原理设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。其中基2表示：N=2M，M为整数.若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M。2、算法步骤现对原序列进行分组，变量置换先将x(n)按n的奇偶分为两组，作变量置换: 当n=偶数时，令n=2r; 当n=奇数时，令n=2r+1;得到由于所以X1(k)、X2(k)只有N/2个点，以N/2为周期；而X (k)却有N个点，以N为周期。要用X1(k)、X2(k)表达全部的X (k) 值，还必须利用WN系数的周期特性。由于所以又考虑到 的对称性：有：由此可得3、编程思想及流程图for(L=1; L=M; L+)开始送入x(n)和N=2M调整输入x(n)的顺序B = 2L-1for(J=0; J=B-1; J+)p = J2M-Lfor(k = J; k= N-1; k=k+2L) 输出结果结束4、具体程序如下：function z=FFtmatlab(a) N=length(a);N1=N;p=0; while p=N p=p+1;r=N1/2; if r=1 break end N1=r; end w=exp(-i*2*pi/N); for q=1:p n=2q; for k=0:N/n-1 for j=0:n/2-1 m=k*n; b(m+j+1)=a(m/2+j+1)+a(m/2+j+1+N/2); b(m+j+1+n/2)=(a(m/2+j+1)-a(m/2+j+1+N/2)*w(m/2); end end a=b; end z=a;clear all;N=32;x=zeros(1,N);x(1)=1;xn=0:N-1;subplot(121),stem(xn,x);axis(-1 33 0 1.1);XK=FFtmatlab(xn);subplot(122);stem(abs(XK)运行结果如下第三章 DFT与FFT的比较1、按时间抽取基2FFT算法与DFT运算量的比较由前面介绍的按时间抽取的FFT运算流图可见，每一级都由N/2个蝶形运算构成。每个蝶形需要一次复乘和两次复加运算，因此每一级都需要N/2次复乘和N次复加（每个结加减各一次）。这样m级运算共需要复乘次数 复加次数 而直接计算DFT时所需的复乘数为N的平方次，复数加为N(N-1)次，当N远大于1时N的平方也远大于 ,从而DIT-FFT算法比直接DFT的运算次数大大减少。例如，N=210=1024时这样就使运算效率提高200多倍。2、通过编写一段matlab程序比较按时间抽取基2FFT算法与DFT运算时间对长度为4096的随机序列进行fft所需时间的程序及结果如下：Nmax=4096;fft_time=zeros(1,Nmax);for n=1:1:Nmax x=rand(1,n); t=clock; fft(x); fft_time(n)=etime(clock,t);endn=1:1:Nmax;plot(n,fft_time,.);title(FFT执行时间)对长度为256的随机序列进行dft所需时间的程序及结果如下：Nmax=256;dft_time=zeros(1,Nmax);for n=1:1:Nmax x=rand(1,n); t=clock; dft(x,n); dft_time(n)=etime(clock,t);endn=1:1:Nmax;plot(n,dft_time,.);title(DFT执行时间)心得体会：通过这两周的数字信号处理的课程设计，我先在图书馆里查找了相关的书籍，如MATLAB类的编程书籍，各类数据处理类的书籍以及离散傅立叶变换的书籍等，既丰富了自己的知识范围，又对与自己所学的知识有了更深的了解和认识，同时也对它的应用有了一个大体的认识。在设计的过程中，我也认识到了自己所学知识的不足。这也让我再次认识到知识是无尽的，只有不断的充实自己、完善自己的知识理论体系，才能够更好的胜任自己以后的工作。设计过程中知识的不足也让我更加坚定了终身学习的决心。在设计的过程中，我也得到了我们设计小组的成员和很多同学的帮组。这也加强了我与其他同学合作的能力。查找资料的过程中我也增强自己学习的能力，这些都将让我在以后的学习、生活和工作中受益匪浅。参考文献：1、谢平 王娜 林洪彬 信号处理原理及应用 机械工业出版社 20092.、郭仕剑 王宝顺 贺志国 杨可心 等 MATLAB7.x数字信号处理 人民邮电出版社200