《离散傅里叶变换(DF).ppt》由会员分享，可在线阅读，更多相关《离散傅里叶变换(DF).ppt（95页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章离散傅里叶变换(DFT)2.1离散傅里叶变换(DFT)2.2快速傅里叶变换(FFT)2.3离散卷积2.4FFT应用第2章离散傅里叶变换(DFT)1第2章离散傅里叶变换(DFT)2.1离散傅里叶变换(DFT)2.1.1DFT定义2.1.2DFT推导2.1.3DFT性质2.1.4DFT的矩阵计算2第2章离散傅里叶变换(DFT)2.1.1离散傅里叶变换的定义1.定义设x(n)是一个长度为N的有限长序列，则定义x(n)的N点离散傅里叶变换为X(k)的离散傅里叶逆变换为(3.1.2)式中，N称为DFT变换区间长度，通常称(3.1.1)式和(3.1.2)式为离散傅里叶变换对。3第2章离散傅里叶变换(
2、DFT)证明IDFTX(k)的唯一性。证明：把(3.1.1)式代入(3.1.2)式有为整数为整数所以，在变换区间上满足下式：IDFTX(k)=x(n),0nN-1由此可见，(3.1.2)式定义的离散傅里叶逆变换是唯一的。4第2章离散傅里叶变换(DFT)例3.1.1x(n)=R4(n)，求x(n)的8点和16点DFT。解：设变换区间N=8，则设变换区间N=16，则n16161615n5第2章离散傅里叶变换(DFT)2.DFT的隐含周期性前面定义的DFT变换对中，x(n)与X(k)均为有限长序列，但由于的周期性，使(3.1.1)式和(3.1.2)式中的X(k)隐含了周期性，且周期为N。对任意整数m
3、，总有均为整数所以(3.1.1)式中，X(k)满足同理可证明(3.1.2)式中x(n+mN)=x(n)6第2章离散傅里叶变换(DFT)实际上，任何周期为N的周期序列都可以看作长度为N的有限长序列x(n)的周期延拓序列，而x(n)则是的一个周期，即为了叙述方便，将(3.1.5)式用如下形式表示：(3.1.7)7第2章离散傅里叶变换(DFT)图3.1.2有限长序列及其周期延拓8第2章离散傅里叶变换(DFT)2.1.2DFT推导1.由Z 变换推导由Z变换可知，非周期序列x(n)的Z变换为对于有限长序列x(n)(n=0,N-1)，X(z)的收敛区域总包括单位圆。若在单位圆的N个均分点上计算Z变换，得周
4、期序列为9第2章离散傅里叶变换(DFT)上式两边乘以，再对k从0N-1求和，得这说明，长度小于或等于N的有限时宽序列可以用它的Z变换在单位圆上的N个取样精确地表示，或有限时宽序列的DFT相当于其Z变换在单位圆等间隔点上的取样。Z 平面IR2/N10第2章离散傅里叶变换(DFT)图3.1.1X(k)与X(ej)的关系X(z)X(ej)X(k)11第2章离散傅里叶变换(DFT)2.由离散傅里叶级数推导如果x(n)的长度为N，且，则可写出的离散傅里叶级数为(3.1.8)(3.1.9)式中(3.1.10)12第2章离散傅里叶变换(DFT)3.由连续傅里叶变换推导设xa(t)与Xa(j)构成傅立叶变换对
5、，则(1)时域采样：将xa(t)离散化其频谱为X(ej)，是以2为周期的周期函数，即13第2章离散傅里叶变换(DFT)(2)时域截断：将xa(nT)由无限变为有限时宽x(n)x(n)=xa(nT)w(t)其中且N=T0/T也即此时频谱为X(ejT)*W(j)，是的连续周期函数。14第2章离散傅里叶变换(DFT)(3)频域采样：将频谱离散化为周期序列，其时域函数为显然，是以T0（T0=NT）为周期的序列，故其一周内恰好为原信号xa(t)的N个采样值。15第2章离散傅里叶变换(DFT)将上述求解，得令显然完全由X(k)确定，而X(k)是以N为周期的序列，且在0N-1区间上xa(nT)可用x(n)表
6、示，于是16第2章离散傅里叶变换(DFT)同样，可推导出显然，当时域采样满足时域采样定理时，频域不会发生混叠，这时，在0N-1区间上定义的X(k)恰好表示Xa(j)在带限区域内的采样值；而当频域采样满足频域采样定理时，时域才不会发生混叠，在0N-1区间上定义的x(n)才能代表x(t)的有效采样值。上述推导说明，离散傅立叶变换与连续傅立叶变换有密切关系。17第2章离散傅里叶变换(DFT)2.1.3DFT性质DFT有许多性质与连续、序列傅里叶变换相似，但也有其独特性，这主要源于它所隐含的周期性，即循环性。1.线性性如果x1(n)和x2(n)是两个有限长序列，长度分别为N1和N2y(n)=ax1(n
7、)+bx2(n)0nN-1式中a、b为常数，N=maxN1,N2，则y(n)的N点DFT为Y(k)=DFTy(n)=aX1(k)+bX2(k),0kN-1(3.2.1)其中X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT。该性质说明，DFT适用于离散线性系统。18第2章离散傅里叶变换(DFT)2.循环位移性质若x(n)X(k)成立，则x(n-n0)X(k)称为时间位移性(1)或x(n)X(k-k0)称为频率位移性(2)(1)说明时域信号的加载时刻，对信号DFT的幅度不产生任何影响，只在频域引入一线性相移。(2)说明用特定频率的余弦（或正弦）对信号进行调制，其结果是信号的频谱发生了
8、位移（以调制频率为中心）。由于x(n)与X(k)的周期性，使DFT的位移呈现循环特性。19第2章离散傅里叶变换(DFT)图3.2.1循环位移过程示意图20第2章离散傅里叶变换(DFT)3.对称性若x(n)X(k)成立，则x*(n)X*(-k)（复共轭序列的DFT）或x*(-n)X*(k)或(1/N)X(n)x(-k)说明DFT的时域与频域具有对偶关系。21第2章离散傅里叶变换(DFT)证明：根据DFT的唯一性由X(k)的隐含周期性，有X*(N-k)=X*(-k)，X(N)=X(0)。用同样的方法可以证明DFTx*(N-n)=X*(k)(3.2.8)22第2章离散傅里叶变换(DFT)4.DFT的
9、共轭对称性如同任何实函数都可以分解成偶对称分量和奇对称分量一样，任何有限长序列x(n)也可以表示成其共轭对称分量和共轭反对称分量之和，即x(n)=xep(n)+xop(n),0nN-1(3.2.11)将式中的n换成N-n，并取复共轭，得到x*(N-n)=x*ep(N-n)+x*op(N-n)=xep(n)-xop(n)(3.2.12)xep(n)=1/2x(n)+x*(N-n)(3.2.13)xop(n)=1/2x(n)-x*(N-n)(3.2.14)23第2章离散傅里叶变换(DFT)(1)如果x(n)=xr(n)+jxi(n)其中xr(n)=Rex(n)=1/2x(n)+x*(n)jxi(n
10、)=jImx(n)=1/2x(n)-x*(n)则DFTxr(n)=1/2DFTx(n)+x*(n)=1/2X(k)+X*(N-k)=Xep(k)DFTjxi(n)=1/2DFTx(n)-x*(n)=1/2X(k)-X*(N-k)=Xop(k)由DFT的线性性质可得X(k)=DFTx(n)=Xep(k)+Xop(k)(3.2.16)其中Xep(k)=DFTxr(n)，X(k)的共轭对称分量Xop(k)=DFTjxi(n)，X(k)的共轭反对称分量24第2章离散傅里叶变换(DFT)(2)如果x(n)=xep(n)+xop(n)，0nN-1(3.2.17)其中xep(n)=1/2x(n)+x*(N-
11、n)，x(n)的共轭对称分量xop(n)=1/2x(n)-x*(N-n)，x(n)的共轭反对称分量则DFTxep(n)=1/2DFTx(n)+x*(N-n)=1/2X(k)+X*(k)=ReX(k)DFTxop(n)=1/2DFTx(n)-x*(N-n)=1/2X(k)-X*(k)=jImX(k)因 此 X(k)=DFTx(n)=XR(k)+jXI(k)(3.2.18)其中XR(k)=ReX(k)=DFTxep(n)jXI(k)=jImX(k)=DFTxop(n)25第2章离散傅里叶变换(DFT)有限长实序列DFT的共轭对称性说明：设x(n)是长度为N的实序列，且X(k)=DFTx(n)，则(
12、1)X(k)共轭对称，即X(k)=X*(N-k),0kN-1(3.2.19)(2)如果x(n)=x(N-n)，则X(k)实偶对称，即X(k)=X(N-k)(3.2.20)(3)如果x(n)=-x(N-n)，则X(k)纯虚奇对称，即X(k)=-X(N-k)(3.2.21)26第2章离散傅里叶变换(DFT)利用DFT的共轭对称性，通过计算一个N点DFT，可以得到两个不同实序列的N点DFT。设x1(n)和x2(n)为两个实序列，构成新序列x(n)如下：x(n)=x1(n)+jx2(n)对x(n)进行DFT，得到X(k)=DFTx(n)=Xep(k)+Xop(k)由(3.2.16)式、(3.2.13)
13、式、(3.2.14)式得到Xep(k)=DFTx1(n)=1/2X(k)+X*(N-k)Xop(k)=DFTjx2(n)=1/2X(k)-X*(N-k)所以X1(k)=DFTx1(n)=1/2X(k)+X*(N-k)X2(k)=DFTx2(n)=-j1/2X(k)-X*(N-k)27第2章离散傅里叶变换(DFT)2.1.4DFT的矩阵计算DFT计算也可以采用矩阵计算法，这样可以利用计算机中的矩阵乘法子程序。28第2章离散傅里叶变换(DFT)1.DFT的矩阵计算根据DFT定义有用一组线性方程表示为29第2章离散傅里叶变换(DFT)令x(n)=x(0)，x(1)，x(2)，x(N-1)TX(k)=
14、X(0)，X(1)，X(2)，X(N-1)T则方程组可用矩阵表示为X(k)=ANx(n)30第2章离散傅里叶变换(DFT)2.IDFT 的矩阵计算根据IDFT定义有类似地，可将逆变换表示为其中AN*是AN的共轭矩阵，即31第2章离散傅里叶变换(DFT)显然，当N确定时，AN与AN*为常数矩阵，只要给定x(n)或X(k)就可以通过矩阵计算出X(k)或x(n)。用计算机程序实现时，可以事先将AN与AN*存储在内存中。AN与AN*中各元素由旋转因子组成，利用旋转因子的周期性，可将AN与AN*简化。即AN与AN*中实际只包含N个不相同的元素：，或，因此，只要确定出上述N个值，即可确定AN或AN*。32
15、第2章离散傅里叶变换(DFT)有两种确定方法：(1)定义计算(2)几何计算将单位圆从正实轴开始N等分，等分点在Z平面上的坐标即确定了的值。对于AN，按i=0N-1在单位圆上顺时针取点；对于AN*，按i=0N-1在单位圆上逆时针取点。33第2章离散傅里叶变换(DFT)以N=8为例计算AN与AN*。显然有，34第2章离散傅里叶变换(DFT)于是35第2章离散傅里叶变换(DFT)例：计算x(t)=cos(2t)的频谱。解:(1)对x(t)采样根据采样定理，余弦信号一周至少采3个点，取N=4，则x(n)=1,0,-1,0T(2)求X(k)(3)将X(k)的观察区间位移到-N/2N/2-1，得X(-2)
16、=0,X(-1)=2,X(0)=0,X(1)=2,(4)离散频谱与连续频谱的对比频域采样间隔f=1/T0=1/TP=1由图中可看出X(f)=(1/N)X(k)(f=kf)该结论证明略。X(f)1/2 1/2-1 1fX(k)2 2-1 1k36第2章离散傅里叶变换(DFT)时域频域非周期，连续x(t)X(j)或X(f)非周期，连续无限长序列x(n)X(ej)周期，连续周期N(T0)，序列x(n)X(k)周期N(1/T=fs),离散时域采样间隔Tt=nTf=k(1/T0)频域采样间隔1/T0=kffX(f)=(1/N)X(k)(f=kf)=2f=T37第2章离散傅里叶变换(DFT)2.2快速傅里
17、叶变换(FFT)频谱分析作为信号处理的基本工具已在多学科领域得到应用。然而DFT运算量大，使应用受到限制。1965年，库利图基(Cooley-Tukey)发表了快速计算DFT的方法，使DFT得到实际应用，并由此发展成为称之为快速傅立叶变换(FFT)的一类算法。FFT仅是DFT的一类特殊计算方法。它的价值在于：将DFT的计算时间减少12个数量级（甚至性能改善达100倍之多）。它的重要性在于：明显地证明了采用数字方法进行频谱分析较之用模拟方法更经济。38第2章离散傅里叶变换(DFT)2.2.1FFT 原理长度为N的有限长序列x(n)的DFT为考虑x(n)为复数序列的一般情况，对某一个k值，直接按(
18、4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法，N点DFT的复乘次数为N2，复加次数为N(N-1)。(4.2.1)39第2章离散傅里叶变换(DFT)FFT的基本原理是：把N点序列的DFT逐次分解为若干个较短序列DFT的线性组合。分解的效果是：DFT的乘法和加法次数大大减少。分解的方法不同，导致不同的FFT算法。在FFT算法中，普遍利用了旋转因子WNm的周期性和对称性。即周期性为对称性为(4.2.2)40第2章离散傅里叶变换(DFT)以一种序列分解法-时间抽取法为例说明FFT原理。设N为合数，即N=ML，则N点序列可分解为M个L点的新序列，即x(n)=x(0),x(1),x(
19、2),x(N-1)分解为x(iM)=x(0),x(M),x(2M),x(L-1)M)x(iM+1)=x(1),x(M+1),x(2M+1),x(L-1)M+1)x(iM+M-1)=x(M-1),x(2M-1),x(3M-1),x(L-1)M+M-1)41第2章离散傅里叶变换(DFT)由此，DFT可写为式中，复数乘法次数：ML2+NM=N(M+L)复数加法次数：ML(L-1)+N(M-1)=N(M+L-2)当L、M均大于1时，有N(M+L)N2N(M+L-2)N(N-1)即分解减少了计算次数。42第2章离散傅里叶变换(DFT)若L也为合数的话，则上述分解可继续，从而使计算次数进一步降低。当N=P
20、1P2P3Pk时，按上述逐次分解方法可得计算次数为复数乘法：N(P1+P2+P3+Pk)复数加法：N(P1+P2+P3+Pk-k)当Pi各不相同时，按上述逐次分解方法得到的FFT算法称为混基FFT；当Pi=r(即N=rk)时，得到的FFT算法称为基rFFT；当r=2时，得到常用的基2FFT。43第2章离散傅里叶变换(DFT)2.2.2基2FFT1.时间抽取法设序列x(n)的长度为N，且满足按n的奇偶把x(n)分解为两个N/2点的子序列为自然数44第2章离散傅里叶变换(DFT)则x(n)的DFT为其中kr45第2章离散傅里叶变换(DFT)由于X1(k)和X2(k)均以N/2为周期，且所以X(k)
21、又可表示为(4.2.7)(4.2.8)图4.2.1蝶形运算符号46第2章离散傅里叶变换(DFT)图4.2.2N点DFT的一次时域抽取分解图(N=8)47第2章离散傅里叶变换(DFT)与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即那么，X1(k)又可表示为同理，由X3(k)和X4(k)的周期性和WmN/2的对称性得：1(4.2.9)(4.2.10)48第2章离散傅里叶变换(DFT)用同样的方法可计算出其中(4.2.11)49第2章离散傅里叶变换(DFT)图4.2.3N点DFT的第二次时域抽取分解图(N=8)50第2章离散傅里叶变换(DFT)图4.2.4N
22、点时域抽取FFT运算流图(N=8)蝶形运算，同址计算，序列倒序，系数WNr确定51第2章离散傅里叶变换(DFT)算法复杂度：设P(N)表示N点DFT所需复数乘法计算次数，Q(N)表示N点DFT所需复数加法计算次数，则按时间抽取法得到当将DFT最终分解为2点时，P(2)=1，Q(2)=2。将此初始条件带入上式递归求解得取N=1024，基2FFT速度比DFT提高200倍。52第2章离散傅里叶变换(DFT)图4.2.5FFT算法与DFT定义计算之间乘法次数比较曲线53第2章离散傅里叶变换(DFT)2.频率抽取法设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为
23、如下形式：54第2章离散傅里叶变换(DFT)将X(k)分为偶数与奇数组，当k取偶数(k=2r,r=0,1,N/2-1)时当k取奇数(k=2r+1,r=0,1,N/2-1)时偶数奇数(4.2.15)(4.2.14)rn55第2章离散傅里叶变换(DFT)将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得(4.2.16)图4.2.10DIFFFT蝶形运算流图符号56第2章离散傅里叶变换(DFT)图4.2.12DIFFFT二次分解运算流图(N=8)57第2章离散傅里叶变换(DFT)图4.2.13DIFFFT运算流图(N=8)58第2章离散傅里叶变换(DFT)3.DFT程序#in
24、clude#include#include#includemsp.hvoidmcmpdft(complexx,complexy,intn,intisign)/*-Routinuemcmpdft:DirectlytoComputetheDFT/IDFTofComplexDatax(n)ByDFTdefinition.IfISIGN=-1:ForForwardTransform;ISIGN=1:ForInverseTransform.-*/complext,ts,z;floatpi2;intm,k;pi2=8.*atan(1.);t.real=0.;t.imag=isign*pi2/n;ts.re
25、al=0.0;for(m=0;mn;m+)ym=x0;for(k=1;kn;k+)ts.imag=t.imag*k*m;z=cexp(ts);ym.real+=xk.real*z.real-xk.imag*z.imag;ym.imag+=xk.real*z.imag+xk.imag*z.real;if(isign=1)ym.real/=n;ym.imag/=n;59第2章离散傅里叶变换(DFT)4.FFT程序#include#include#include#includemsp.hvoidmcmpfft(complexx,intn,intisign)/*-Routinemcmpfft:toob
26、taintheDFTofComplexDatax(n)ByCooley-Tukeyradix-2DITAlgorithm.inputparameters:x:complexarray.inputsignalisstoredinx(0)tox(n-1).n:thedimensionofxandy.isign:ifISIGN=-1ForForwardTransformifISIGN=+1ForInverseTransform.outputparameters:x:complexarray.DFTresultisstoredinx(0)tox(n-1).Notes:nmustbepowerof2.-*/complext,z,ce;floatpisign;intmr,m,l,j,i,nn;for(i=1;i16)printf(Nisnotapowerof2!n);return;z.real=0.0;pisign=4*isign*atan(1.);mr=0;for(m=1;m=n)l=l/2;mr=mr%l+l;if(mr=m)continue;60