《离散傅里叶变换DF课件》由会员分享，可在线阅读，更多相关《离散傅里叶变换DF课件（95页珍藏版）》请在金锄头文库上搜索。
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的的有有限限长长序序列
2、列，则则定定义义x(n)的的N点离散傅里叶变换为点离散傅里叶变换为X(k)的离散傅里叶逆变换为的离散傅里叶逆变换为(3.1.2)式中，式中，N称为称为DFT变换区间长度，通常称变换区间长度，通常称(3.1.1)式和式和(3.1.2)式为离散傅里叶式为离散傅里叶变换对变换对。3第第2章章离散傅里叶变换离散傅里叶变换(DFT)证明证明IDFTX(k)的唯一性。的唯一性。证明：把证明：把(3.1.1)式代入式代入(3.1.2)式有式有为整数为整数所以，所以，在变换区间上满足下式：在变换区间上满足下式：IDFTX(k)=x(n),0nN-1由此可见，由此可见，(3.1.2)式定义的离散傅里叶逆变换是唯
3、一的。式定义的离散傅里叶逆变换是唯一的。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
4、，总有总有均为整数均为整数所以所以(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第
5、第2章章离散傅里叶变换离散傅里叶变换(DFT)2.1.2DFT推导推导1.由由Z变换推导变换推导由由Z变换可知，非周期序列变换可知，非周期序列x(n)的的Z变换为变换为对于有限长序列对于有限长序列x(n)(n=0,N-1)，X(z)的收敛区域的收敛区域总包括单位圆。若总包括单位圆。若在单位圆的在单位圆的N个均分点上计算个均分点上计算Z变换变换，得周期序列为得周期序列为9第第2章章离散傅里叶变换离散傅里叶变换(DFT)上式两边乘以上式两边乘以，再对，再对k从从0N-1求和，得求和，得这说明，长度小于或等于这说明，长度小于或等于N的有限时宽序列可以的有限时宽序列可以用它的用它的Z变换在单位圆上的变
6、换在单位圆上的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
7、)3.由连续傅里叶变换推导由连续傅里叶变换推导设设xa(t)与与Xa(j)构成傅立叶变换对，则构成傅立叶变换对，则(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)频域采样频
8、域采样：将频谱离散化：将频谱离散化为周期序列，其时域函数为为周期序列，其时域函数为显然，显然，是以是以T0（T0=NT）为周期的序列，故其一周）为周期的序列，故其一周内恰好为原信号内恰好为原信号xa(t)的的N个采样值。个采样值。15第第2章章离散傅里叶变换离散傅里叶变换(DFT)将上述将上述求解，得求解，得令令显然显然完全由完全由X(k)确定，而确定，而X(k)是以是以N为周期的序列，为周期的序列，且在且在0N-1区间上区间上xa(nT)可用可用x(n)表示，于是表示，于是16第第2章章离散傅里叶变换离散傅里叶变换(DFT)同样，可推导出同样，可推导出显然，当显然，当时域采样满足时域采样定理
9、时域采样满足时域采样定理时，时，频域不会发频域不会发生混叠生混叠，这时，在，这时，在0N-1区间上定义的区间上定义的X(k)恰好表示恰好表示Xa(j)在带限区域内的采样值；而当在带限区域内的采样值；而当频域采样满足频频域采样满足频域采样定理域采样定理时，时，时域才不会发生混叠时域才不会发生混叠，在，在0N-1区间上区间上定义的定义的x(n)才能代表才能代表x(t)的有效采样值。的有效采样值。上述推导说明，离散傅立叶变换与连续傅立叶变上述推导说明，离散傅立叶变换与连续傅立叶变换有密切关系。换有密切关系。17第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.1.3DFT性质性质DFT有有许许多多
10、性性质质与与连连续续、序序列列傅傅里里叶叶变变换换相相似似，但但也也有其独特性，这主要源于它所隐含的周期性，即循环性。有其独特性，这主要源于它所隐含的周期性，即循环性。1.线性性线性性如果如果x1(n)和和x2(n)是两个有限长序列，长度分别为是两个有限长序列，长度分别为N1和和N2y(n)=ax1(n)+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。该性质说明，该性质说
11、明，DFT适用于离散线性系统适用于离散线性系统。18第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.循环位移性质循环位移性质若若x(n)X(k)成立，则成立，则x(n-n0)X(k)称称为为时时间间位位移移性性(1)或或x(n)X(k-k0)称称为为频频率率位位移移性性(2)(1)说说明明时时域域信信号号的的加加载载时时刻刻，对对信信号号DFT的的幅幅度度不产生任何影响，只在不产生任何影响，只在频域引入一线性相移频域引入一线性相移。(2)说说明明用用特特定定频频率率的的余余弦弦（或或正正弦弦）对对信信号号进进行行调调制制，其其结结果果是是信信号号的的频频谱谱发发生生了了位位移移（以以调调制
12、制频频率率为中心）。为中心）。由由于于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的唯一性的
13、唯一性由由X(k)的隐含周期性，有的隐含周期性，有X* *(N-k)=X* *(-k)，X(N)=X(0)。用同样的方法可以证明用同样的方法可以证明DFTx* *(N-n)=X* *(k)(3.2.8)22第第2章章离散傅里叶变换离散傅里叶变换(DFT)4.DFT的共轭对称性的共轭对称性如如同同任任何何实实函函数数都都可可以以分分解解成成偶偶对对称称分分量量和和奇奇对对称称分分量量一一样样，任任何何有有限限长长序序列列x(n)也也可可以以表表示示成成其其共共轭轭对称分量对称分量和和共轭反对称分量共轭反对称分量之和，之和，即即x(n)=xep(n)+xop(n),0nN-1(3.2.11)将式中
14、的将式中的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)=jImx(n)=1/2x(n)-x*(n)则则DFTxr(n)=1/2DFTx(n)+x*(n)=1/2X(k)+X*(N-k)=Xep(k)DF
15、Tjxi(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-n)，x(n)的共轭对称分量的共轭对称分量xop(n)=1/2x(n)-
16、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的实序列，且的实
17、序列，且X(k)=DFTx(n)，则，则(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)为两个实序列，构
18、成新序列为两个实序列，构成新序列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)式、式、(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的矩阵计算的矩阵计
19、算DFT计算也可以采用矩阵计算法，这样可以计算也可以采用矩阵计算法，这样可以利用计算机中的矩阵乘法子程序。利用计算机中的矩阵乘法子程序。28第第2章章离散傅里叶变换离散傅里叶变换(DFT)1.DFT的矩阵计算的矩阵计算根据根据DFT定义有定义有用一组线性方程表示为用一组线性方程表示为29第第2章章离散傅里叶变换离散傅里叶变换(DFT)令令x(n)=x(0)，x(1)，x(2)，x(N-1)TX(k)=X(0)，X(1)，X(2)，X(N-1)T则方程组可用矩阵表示为则方程组可用矩阵表示为X(k)=ANx(n)30第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.IDFT的矩阵计算的矩阵计算根
20、据根据IDFT定义有定义有类似地，可将逆变换表示为类似地，可将逆变换表示为其中其中AN*是是AN的共轭矩阵，即的共轭矩阵，即31第第2章章离散傅里叶变换离散傅里叶变换(DFT)显然，当显然，当N确定时，确定时，AN与与AN*为常数矩阵，只要为常数矩阵，只要给定给定x(n)或或X(k)就可以通过矩阵计算出就可以通过矩阵计算出X(k)或或x(n)。用计算机程序实现时，可以事先将用计算机程序实现时，可以事先将AN与与AN*存储存储在内存中。在内存中。AN与与AN*中各元素由旋转因子中各元素由旋转因子组成，利用旋组成，利用旋转因子的周期性，可将转因子的周期性，可将AN与与AN*简化。即简化。即AN与与
21、AN*中实际只包含中实际只包含N个不相同的元素：个不相同的元素：，或或，因此，只要确定出上述因此，只要确定出上述N个值，即可确定个值，即可确定AN或或AN*。32第第2章章离散傅里叶变换离散傅里叶变换(DFT)有两种确定方法：有两种确定方法：(1)定义计算定义计算(2)几何计算几何计算将单位圆从正实轴开始将单位圆从正实轴开始N等分，等分点在等分，等分点在Z平面上的平面上的坐标即确定了坐标即确定了的值。的值。对于对于AN，按按i=0N-1在在单位圆上顺时针取点单位圆上顺时针取点；对于对于AN*，按按i=0N-1在在单位圆上逆时针取点单位圆上逆时针取点。33第第2章章离散傅里叶变换离散傅里叶变换(
22、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)=0,X(-1)=2,X(0)=0,X(1)=2,(4)离散频谱与连续频谱的对比离散频谱与连续频谱的对比频域采样
23、间隔频域采样间隔f=1/T0=1/TP=1由图中可看出由图中可看出X(f)=(1/N)X(k)(f=kf)该结论证明略。该结论证明略。X(f)1/21/2-11fX(k)22-11k36第第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)=
24、2f=T37第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.2快速傅里叶变换快速傅里叶变换(FFT)频谱分析作为信号处理的基本工具已在多学科领频谱分析作为信号处理的基本工具已在多学科领域得到应用。然而域得到应用。然而DFT运算量大，使应用受到限制。运算量大，使应用受到限制。1965年，库利年，库利图基图基(Cooley-Tukey)发表了快速发表了快速计算计算DFT的方法，使的方法，使DFT得到实际应用，并由此发展得到实际应用，并由此发展成为称之为快速傅立叶变换成为称之为快速傅立叶变换(FFT)的一类算法。的一类算法。FFT仅是仅是DFT的一类特殊计算方法。它的价值在的一类特殊计算方法。它
25、的价值在于：将于：将DFT的计算时间减少的计算时间减少12个数量级（甚至性能改个数量级（甚至性能改善达善达100倍之多）。它的重要性在于：明显地证明了采倍之多）。它的重要性在于：明显地证明了采用数字方法进行频谱分析较之用模拟方法更经济。用数字方法进行频谱分析较之用模拟方法更经济。38第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.2.1FFT原理原理长度为长度为N的有限长序列的有限长序列x(n)的的DFT为为考考虑虑x(n)为为复复数数序序列列的的一一般般情情况况，对对某某一一个个k值值，直直接接按按(4.2.1)式式计计算算X(k)值值需需要要N次次复复数数乘乘法法、(N-1)次次复复数
26、数加加法法，N点点DFT的的复复乘乘次次数数为为N2，复复加加次次数数为为N(N-1)。(4.2.1)39第第2章章离散傅里叶变换离散傅里叶变换(DFT)FFT的的基基本本原原理理是是：把把N点点序序列列的的DFT逐逐次次分分解解为为若干个较短序列若干个较短序列DFT的线性组合。的线性组合。分解的效果是：分解的效果是：DFT的乘法和加法次数大大减少。的乘法和加法次数大大减少。分解的方法不同，导致不同的分解的方法不同，导致不同的FFT算法。算法。在在FFT算算法法中中，普普遍遍利利用用了了旋旋转转因因子子WNm的的周周期期性性和对称性。即周期性为和对称性。即周期性为对称性为对称性为(4.2.2)
27、40第第2章章离散傅里叶变换离散傅里叶变换(DFT)以一种序列分解法以一种序列分解法-时间抽取法为例说明时间抽取法为例说明FFT原理。原理。设设N为合数，即为合数，即N=ML，则，则N点序列可分解为点序列可分解为M个个L点的新序列，即点的新序列，即x(n)=x(0),x(1),x(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)由此，由
28、此，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=P1P2P3Pk时，按上述逐次分解方法可时，按上述逐次分解方法可得计算次数为得计算次数为复数乘法：复数乘法：N(P1+P2+P3+P
29、k)复数加法：复数加法：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章章离散傅里叶变换离散傅里叶变换(
30、DFT)则则x(n)的的DFT为为其中其中kr45第第2章章离散傅里叶变换离散傅里叶变换(DFT)由于由于X1(k)和和X2(k)均以均以N/2为周期，且为周期，且所以所以X(k)又可表示为又可表示为(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
31、(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点时域抽取点时域抽取FFT运算流图运算流图(N=8)蝶形运算，同址计算，序列倒序，系数蝶形运算，同址计算，序列倒序，系数WNr确定确
32、定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定义计算之间乘法次数比较曲线定义计算之
33、间乘法次数比较曲线53第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.频率抽取法频率抽取法设序列设序列x(n)长度为长度为N=2M，首先将，首先将x(n)前后对半分前后对半分开，得到两个子序列，其开，得到两个子序列，其DFT可表示为如下形式：可表示为如下形式：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)和和x
34、2(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程序程序#include#include#include#includemsp.hvoidmcmpdft(complexx,complexy,intn,int
35、isign)/*-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.real=0.0;for(m=0;mn;m+)ym=x0;for(k=1;kn;k+)ts.imag=t.imag*k*m;z=cexp(ts);y
36、m.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:toobtaintheDFTofComplexDatax(n)ByCooley-Tukeyradix-2DITAlgorithm.
37、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)prin
38、tf(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=n)if(isign=-1)return;for(j=0;jn;j+)xj.real=xj.real/n;xj.imag=xj.imag/n;return;for(m=0;ml;m+)for(i=m;in;i=i+2*l)z.imag=m*pisign/l;ce=cexp(z);t.real=xi+l.real*ce.real-xi+l.imag*ce.imag;t.imag=xi+l.re
39、al*ce.imag+xi+l.imag*ce.real;xi+l.real=xi.real-t.real;xi+l.imag=xi.imag-t.imag;xi.real=xi.real+t.real;xi.imag=xi.imag+t.imag;l=2*l;61第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.2.3利用利用FFT计算计算IDFTDFT和和IDFT的运算公式为：的运算公式为：由于由于对上式两边同时取共轭，得对上式两边同时取共轭，得可见，利用可见，利用FFT也可计算也可计算IDFT。nX(k)62第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.3离散卷积离散卷积由于卷积
40、运算可以描述线性时不变系统，因此它在信号由于卷积运算可以描述线性时不变系统，因此它在信号处理中具有重要作用。离散系统中的卷积用离散卷积计算。处理中具有重要作用。离散系统中的卷积用离散卷积计算。2.3.1定义定义若若x1(n)与与x2(n)是宽度为是宽度为N的有限时宽序列，则的有限时宽序列，则定义为定义为x1(n)与与x2(n)的离散卷积，记作的离散卷积，记作x1(n)* *x2(n)。因为离散信号（有限时宽序列）被看作周期序列，因此因为离散信号（有限时宽序列）被看作周期序列，因此y(n)也具有周期特性，且周期为也具有周期特性，且周期为N，故离散卷积又称作循环，故离散卷积又称作循环卷积。卷积。6
41、3第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.3.2循环卷积定理循环卷积定理若若x1(n)X1(k)，x2(n)X2(k)，则，则x1(n)* *x2(n)X1(k)X2(k)或或x1(n)x2(n)1/N(X1(k)* *X2(k)。卷积定理指出了相乘与卷积运算的关系，同时给出了卷卷积定理指出了相乘与卷积运算的关系，同时给出了卷积运算的另一途径，即积运算的另一途径，即由卷积定理也可以推论出由卷积定理也可以推论出x1(n)* *x2(n)的周期为的周期为N。DFTDFTx1(n)x2(n)X1(k)X2(k)x1(n)*x2(n)X1(k)X2(k)IDFT64第第2章章离散傅里叶变换
42、离散傅里叶变换(DFT)2.3.3循环卷积与线性卷积的关系循环卷积与线性卷积的关系设设x1(n)与与x2(n)是宽度分别为是宽度分别为N1、N2的有限时宽序列，则的有限时宽序列，则循环卷积：循环卷积：线性卷积：线性卷积：其中，循环卷积长度其中，循环卷积长度N3=maxN1，N2线性卷积长度线性卷积长度N4=N1+N2-1显然，显然，N3N且与且与N数量级相同）；数量级相同）；.对对h(n)与与xi(n)分别作分别作L(N+M-1)点的点的DFT，得到，得到H(k)与与Xi(k)；(用用FFT).对对H(k)Xi(k)求出求出L点点IDFT得得h(n)* *xi(n)=yi(n)；(用用FFT)
43、.对各段卷积求和，即对各段卷积求和，即注：该方法中，各段注：该方法中，各段yi(n)是以线性卷积计算的。是以线性卷积计算的。75第第2章章离散傅里叶变换离散傅里叶变换(DFT)图图3.4.4重叠相加法卷积示意图重叠相加法卷积示意图76第第2章章离散傅里叶变换离散傅里叶变换(DFT)重叠保留法重叠保留法仍然采用分段求卷积再组合的方法。仍然采用分段求卷积再组合的方法。该方法与重叠相加法的区别为：该方法与重叠相加法的区别为：.对序列对序列x(n)以以M为长度为长度重叠重叠分段为分段为xi(n)，其后段与前，其后段与前段有段有N-1个重叠点；个重叠点；.每段以每段以M为周期计算循环卷积为周期计算循环卷
44、积；(用用FFT).将每段得到的循环卷积结果的前将每段得到的循环卷积结果的前N-1个点去掉个点去掉(这是这是循环卷积中的混叠部分循环卷积中的混叠部分)，然后将各段剩余部分，然后将各段剩余部分(对应对应线性卷积结果线性卷积结果)首尾衔接起来，即得到最终结果。首尾衔接起来，即得到最终结果。77第第2章章离散傅里叶变换离散傅里叶变换(DFT)重叠保留法卷积示意图重叠保留法卷积示意图2M-(N-1)3M-2(N-1)78第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.4.2利用利用FFT对连续信号作频谱分析对连续信号作频谱分析所所谓谓信信号号的的谱谱分分析析就就是是计计算算信信号号的的傅傅里里叶叶
45、变变换换。连连续续信信号号与与系系统统的的傅傅里里叶叶分分析析显显然然不不便便于于直直接用计算机系统实现，使其应用受到限制。接用计算机系统实现，使其应用受到限制。DFT(FFT)是是一一种种时时域域和和频频域域均均离离散散化化的的变变换换，适适合合数数值值运运算算，成成为为分分析析离离散散信信号号和和系系统统的的有力工具。有力工具。作作为为DFT的的重重要要应应用用之之一一，就就是是利利用用FFT对对连续信号作频谱分析。连续信号作频谱分析。79第第2章章离散傅里叶变换离散傅里叶变换(DFT)实现流程为实现流程为:频率采样间隔为频率采样间隔为模拟域模拟域f=1/T0=1/NT(T为时域采样周期为
46、时域采样周期)=2/(NT)数字域数字域=2/N所以，频率分辨率即为所以，频率分辨率即为f=1/NT，f越小分辨率越高越小分辨率越高。抗混叠低抗混叠低通滤波器通滤波器(预滤波预滤波)S/H及及A/DFFTD/A再现滤波器再现滤波器(平滑滤波平滑滤波)sa(t)xa(t)x(n)w(n)xN(n)X(k)1/N(衰减因子衰减因子)X(j)80第第2章章离散傅里叶变换离散傅里叶变换(DFT)利利用用FFT分分析析连连续续信信号号频频谱谱的的好好处处是是可可以以用用计计算算机机进进行高速频谱计算，但有可能造成误差，主要有三方面原因：行高速频谱计算，但有可能造成误差，主要有三方面原因：1.混叠失真混叠
47、失真利利用用抗抗混混叠叠模模拟拟低低通通滤滤波波器器进进行行预预滤滤波波，使使xa(t)频频谱谱中中最最高高频频率率分分量量不不超超过过fh。设设S/H或或A/D的的采采样样频频率率为为fs，为了不产生频域混叠，按照采样定理，必须满足，为了不产生频域混叠，按照采样定理，必须满足fs2fh否否则则将将产产生生频频谱谱混混叠叠，称称为为混混叠叠失失真真。消消除除混混叠叠误误差差是是以引入频谱截断误差为代价的以引入频谱截断误差为代价的。81第第2章章离散傅里叶变换离散傅里叶变换(DFT)由频率分辨率由频率分辨率 f=1/NT2fh/N可看出，信号最高频率可看出，信号最高频率fh( (又称高频容量又称
48、高频容量) )与频率分辨率与频率分辨率f是相互矛盾的。在是相互矛盾的。在N N一定时，增加一定时，增加fh，使，使f增加，即分辨增加，即分辨力下降；提高分辨力力下降；提高分辨力( (即减小即减小f) )，则需减小高频容量，则需减小高频容量fh。所以，对所以，对fh和和f，保持一个不变而提高另一个性能的唯一，保持一个不变而提高另一个性能的唯一方法是增加采样点数方法是增加采样点数N N。增加采样点数增加采样点数N N的有效途径：的有效途径： (1) (1)增加观察窗口宽度增加观察窗口宽度( (记录长度记录长度)T)T0 0，当，当T T不变时，不变时，N=TN=T0 0/T/T增加；增加； (2)
49、 (2)在一定记录长度在一定记录长度T T0 0内，提高采样频率内，提高采样频率( (减小减小T)T)，使使N=TN=T0 0/T/T增加。增加。 82第第2章章离散傅里叶变换离散傅里叶变换(DFT)例例：用用频频谱谱分分析析仪仪对对模模拟拟信信号号进进行行谱谱分分析析，要要求求谱谱分分辨辨率率f5Hz，信信号号最最高高频频率率fh=2.5kHz，试试确确定定最最小小记记录录时时间间T0min，最最低低采采样样频频率率fsmin，最最少少采采样样点点数数Nmin。如如果果fh不不变变，要要求求谱谱分分辨辨率率提提高高一一倍倍，最最少少采采样样点点数数和和最最小记录时间是多少小记录时间是多少?解
50、：解：T0=1/f1/5=0.2(s)，T0min=0.2sfs2fh=22.5=5(kHz)，fsmin=5kHzN2fh/f=22.5103/5=103，Nmin=103频率分辨率提高一倍，即频率分辨率提高一倍，即f=5Hz/2，则，则Nmin=2fh/f=5103/2.5=2103T0min=1/f=1/2.5=0.4s83第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.频谱泄露频谱泄露对对时时宽宽无无限限或或长长时时宽宽信信号号的的DFT(FFT)处处理理，一一般般需需在时域加窗将其转换成有限时宽信号。在时域加窗将其转换成有限时宽信号。x(n)w(n)X(ej)* *W(ej)频频
51、域域卷卷积积造造成成：窗窗谱谱主主瓣瓣使使信信号号频频谱谱加加宽宽，窗窗谱谱旁旁瓣瓣使使信号频谱出现波纹信号频谱出现波纹(皱波皱波)，这种现象称为频谱泄露。，这种现象称为频谱泄露。泄泄露露使使被被截截信信号号频频谱谱与与原原信信号号频频谱谱之之间间出出现现误误差差，只要加窗，泄露就不可避免，这是只要加窗，泄露就不可避免，这是原理性误差原理性误差。泄泄露露导导致致频频谱谱扩扩展展，使使fh可可能能超超过过奈奈奎奎斯斯特特频频率率(fs/2)，进一步加剧混叠失真。，进一步加剧混叠失真。为为了了减减小小泄泄露露影影响响，必必须须选选择择合合适适的的窗窗函函数数(窗窗口口宽宽度，窗口形状度，窗口形状)
52、。84第第2章章离散傅里叶变换离散傅里叶变换(DFT)图图3.4.11矩形窗函数的幅度谱矩形窗函数的幅度谱85第第2章章离散傅里叶变换离散傅里叶变换(DFT)图图3.4.12加矩形窗前后的频谱加矩形窗前后的频谱86第第2章章离散傅里叶变换离散傅里叶变换(DFT)3.栅栏效应栅栏效应用用DFT(FFT)计算的频谱可以看作是连续信号频谱计算的频谱可以看作是连续信号频谱的采样值，我们只能在离散采样点上看到真实的频谱，的采样值，我们只能在离散采样点上看到真实的频谱，就好象通过栅栏看一幅图像一样，这就是栅栏效应。就好象通过栅栏看一幅图像一样，这就是栅栏效应。栅栏效应可能会造成连续频谱的某些峰值、谷值或栅
53、栏效应可能会造成连续频谱的某些峰值、谷值或细微变化被细微变化被“栅栏栅栏”遮挡，使我们不能观察遮挡，使我们不能观察(检测检测)到，到，造成分析或恢复的不准确性。造成分析或恢复的不准确性。减小这种效应的方法是，在被加窗后的信号数据末减小这种效应的方法是，在被加窗后的信号数据末端补若干零值，使端补若干零值，使FFT计算点数计算点数N增加，又不改变原有增加，又不改变原有的记录数据的记录数据(相当于窗宽不变相当于窗宽不变)。这样就可以在保持原频。这样就可以在保持原频谱形状不变的情况下，增加谱线密度，即频域采样点数谱形状不变的情况下，增加谱线密度，即频域采样点数增加，使原来看不见的频谱分量变得可见。增加
54、，使原来看不见的频谱分量变得可见。87第第2章章离散傅里叶变换离散傅里叶变换(DFT)除以上三方面外，除以上三方面外，CFT与与DFT还有两点不同：还有两点不同：(1)DFT是周期的，是周期的，CFT是非周期的是非周期的DFT一个周期一个周期CFT(k=-N/2N/2-1)(2)DFT幅值与幅值与CFT幅值不同幅值不同X(k)=NX(j)=2k/(NT)或或X(k)=NX(f)f=k/(NT)88第第2章章离散傅里叶变换离散傅里叶变换(DFT)2.4.3用用FFT作频谱计算作频谱计算(分析、测量分析、测量)1.对较长信号作频谱测量对较长信号作频谱测量由由DFT与与Z变换关系得变换关系得若实际信
55、号若实际信号x(n)长度无限或为长度无限或为L(LN)，当希望获，当希望获得有限频率点得有限频率点N上的频谱测量时，如何实现？上的频谱测量时，如何实现？设设x(n)的的Z变换为变换为则则x(n)的的N点点DFT为为89第第2章章离散傅里叶变换离散傅里叶变换(DFT)由由X(k)可确定出有限长序列可确定出有限长序列xp(n)90第第2章章离散傅里叶变换离散傅里叶变换(DFT)该式说明，对该式说明，对L点或无限长信号要实现点或无限长信号要实现N个频率点的频谱个频率点的频谱测量，应先对时间序列以测量，应先对时间序列以N为周期进行拓展，当为周期进行拓展，当LN)个等间隔频率点上计算序列的频谱，则实现方
56、个等间隔频率点上计算序列的频谱，则实现方法为：法为：定义定义则则92第第2章章离散傅里叶变换离散傅里叶变换(DFT)用增加零值样本来充实有限长序列这种简单的方用增加零值样本来充实有限长序列这种简单的方法，使我们能在环绕单位圆的一组等间隔频率点上，法，使我们能在环绕单位圆的一组等间隔频率点上，以以任意的频率分辨率任意的频率分辨率计算序列的频谱，因而无论多高计算序列的频谱，因而无论多高的频率分辨力都能达到。非常有用的方法！的频率分辨力都能达到。非常有用的方法！3.在单位圆内的某圆上作等间隔频率点的频谱测量在单位圆内的某圆上作等间隔频率点的频谱测量设设x(n)为长度是为长度是N的有限序列，欲作频谱测
57、量的圆的有限序列，欲作频谱测量的圆半径为半径为r，则，则即将信号预先乘以即将信号预先乘以r-n，再作，再作FFT。93第第2章章离散傅里叶变换离散傅里叶变换(DFT)图图3.4.7单位圆与非单位圆采样单位圆与非单位圆采样94第第2章章离散傅里叶变换离散傅里叶变换(DFT)4.周期序列的周期序列的DFT设设x(n)为周期序列，周期为周期序列，周期N，其，其N点的点的DFT为为X(k)=XN(k)(1)截取有限长度截取有限长度M=mN，m为正整数，为正整数，则则(2)截截取取有有限限长长度度MmN时时，XM(k)与与X(k)无无关关联联，可可通通过过使使截截取取长长度度逐逐次次加加倍倍计计算算XM(k)，直直至至相相邻邻两两次次计计算在允许误差范围内为止。算在允许误差范围内为止。k/m=整数整数k/m整数整数95
