第2章離散傅里葉變換(DFT)課件

2.1離散傅里葉變換(DFT)2.2快速傅里葉變換(FFT)2.3離散卷積2.4FFT應用第2章離散傅里葉變換(DFT)12.1離散傅里葉變換(DFT)第2章離散傅里葉變換2.1離散傅里葉變換(DFT)

2.1.1DFT定義2.1.2DFT推導2.1.3DFT性質(zhì)2.1.4DFT的矩陣計算22.1離散傅里葉變換(DFT)2.1.1DFT2.1.1離散傅里葉變換的定義

1.定義

設x(n)是一個長度為N的有限長序列，則定義x(n)的N點離散傅里葉變換為X(k)的離散傅里葉逆變換為(3.1.2)式中，，N稱為DFT變換區(qū)間長度，通常稱(3.1.1)式和(3.1.2)式為離散傅里葉變換對。32.1.1離散傅里葉變換的定義1.定義X證明IDFT［X(k)］的唯一性。證明：把(3.1.1)式代入(3.1.2)式有為整數(shù)

為整數(shù)

所以，在變換區(qū)間上滿足下式：IDFT［X(k)］=x(n),0≤n≤N-1由此可見，(3.1.2)式定義的離散傅里葉逆變換是唯一的。4證明IDFT［X(k)］的唯一性。為整數(shù)為整數(shù)所以，在例3.1.1x(n)=R4(n)，求x(n)的8點和16點DFT。解：設變換區(qū)間N=8，則設變換區(qū)間N=16，則n16161615n5例3.1.1x(n)=R4(n)，求x(n)的8點和2.DFT的隱含周期性前面定義的DFT變換對中，x(n)與X(k)均為有限長序列，但由于的周期性，使(3.1.1)式和(3.1.2)式中的X(k)隱含了周期性，且周期為N。對任意整數(shù)m，總有均為整數(shù)所以(3.1.1)式中，X(k)滿足同理可證明(3.1.2)式中x(n+mN)=x(n)62.DFT的隱含周期性均為整數(shù)所以(3.1.1)式中，實際上，任何周期為N的周期序列都可以看作長度為N的有限長序列x(n)的周期延拓序列，而x(n)則是的一個周期，即為了敘述方便，將(3.1.5)式用如下形式表示：

(3.1.7)7實際上，任何周期為N的周期序列圖3.1.2有限長序列及其周期延拓8圖3.1.2有限長序列及其周期延拓82.1.2DFT推導

1.由Z變換推導由Z變換可知，非周期序列x(n)的Z變換為對于有限長序列x(n)(n=0,…,N-1)，X(z)的收斂區(qū)域總包括單位圓。若在單位圓的N個均分點上計算Z變換，得周期序列為92.1.2DFT推導1.由Z變換推導9

上式兩邊乘以，再對k從0~N-1求和，得這說明，長度小于或等于N的有限時寬序列可以用它的Z變換在單位圓上的N個取樣精確地表示，或有限時寬序列的DFT相當于其Z變換在單位圓等間隔點上的取樣。Z平面IR2π/N10上式兩邊乘以，再對k從0~N-1求和圖3.1.1X(k)與X(ejω)的關(guān)系

X(z)~X(ejω)~X(k)11圖3.1.1X(k)與X(ejω)的關(guān)系X(z2.由離散傅里葉級數(shù)推導

如果x(n)的長度為N，且，則可寫出的離散傅里葉級數(shù)為(3.1.8)

(3.1.9)

式中

(3.1.10)122.由離散傅里葉級數(shù)推導(3.1.8)(3.1.3.由連續(xù)傅里葉變換推導設xa(t)與Xa(jΩ)構(gòu)成傅立葉變換對，則(1)時域采樣：將xa(t)離散化其頻譜為X(ejω)，是以2π為周期的周期函數(shù)，即133.由連續(xù)傅里葉變換推導13(2)時域截斷：將xa(nT)由無限變?yōu)橛邢迺r寬x(n)x(n)=xa(nT)?w(t)其中且N=T0/T也即此時頻譜為X(ejΩT)*W(jΩ)，是Ω的連續(xù)周期函數(shù)。14(2)時域截斷：將xa(nT)由無限變?yōu)橛邢迺r寬x(n)1(3)頻域采樣：將頻譜離散化為周期序列，其時域函數(shù)為顯然，是以T0（T0=NT）為周期的序列，故其一周內(nèi)恰好為原信號xa(t)的N個采樣值。15(3)頻域采樣：將頻譜離散化15將上述求解，得令顯然完全由X(k)確定，而X(k)是以N為周期的序列，且在0~N-1區(qū)間上xa(nT)可用x(n)表示，于是16將上述求解，得16同樣，可推導出顯然，當時域采樣滿足時域采樣定理時，頻域不會發(fā)生混疊，這時，在0~N-1區(qū)間上定義的X(k)恰好表示Xa(jΩ)在帶限區(qū)域內(nèi)的采樣值；而當頻域采樣滿足頻域采樣定理時，時域才不會發(fā)生混疊，在0~N-1區(qū)間上定義的x(n)才能代表x(t)的有效采樣值。上述推導說明，離散傅立葉變換與連續(xù)傅立葉變換有密切關(guān)系。17同樣，可推導出172.1.3DFT性質(zhì)DFT有許多性質(zhì)與連續(xù)、序列傅里葉變換相似，但也有其獨特性，這主要源于它所隱含的周期性，即循環(huán)性。1.線性性如果x1(n)和x2(n)是兩個有限長序列，長度分別為N1和N2

y(n)=ax1(n)+bx2(n)0≤n≤N-1式中a、b為常數(shù)，N=max[N1,N2]，則y(n)的N點DFT為

Y(k)=DFT[y(n)]=aX1(k)+bX2(k),0≤k≤N-1(3.2.1)

其中X1(k)和X2(k)分別為x1(n)和x2(n)的N點DFT。該性質(zhì)說明，DFT適用于離散線性系統(tǒng)。182.1.3DFT性質(zhì)DFT2.循環(huán)位移性質(zhì)若x(n)X(k)成立，則x(n-n0)X(k)稱為時間位移性(1)或x(n)X(k-k0)稱為頻率位移性(2)(1)說明時域信號的加載時刻，對信號DFT的幅度不產(chǎn)生任何影響，只在頻域引入一線性相移。(2)說明用特定頻率的余弦（或正弦）對信號進行調(diào)制，其結(jié)果是信號的頻譜發(fā)生了位移（以調(diào)制頻率為中心）。由于x(n)與X(k)的周期性，使DFT的位移呈現(xiàn)循環(huán)特性。192.循環(huán)位移性質(zhì)19圖3.2.1循環(huán)位移過程示意圖

20圖3.2.1循環(huán)位移過程示意圖203.對稱性若x(n)X(k)成立，則x*(n)X*(-k)（復共軛序列的DFT）或x*(-n)X*(k)或(1/N)X(n)x(-k)說明DFT的時域與頻域具有對偶關(guān)系。213.對稱性21

證明：根據(jù)DFT的唯一性由X(k)的隱含周期性，有X*(N-k)=X*(-k)，X(N)=X(0)。用同樣的方法可以證明DFT［x*(N-n)］=X*(k)(3.2.8)22證明：根據(jù)DFT的唯一性由X(k)的隱含周期性，有4.DFT的共軛對稱性

如同任何實函數(shù)都可以分解成偶對稱分量和奇對稱分量一樣，任何有限長序列x(n)也可以表示成其共軛對稱分量和共軛反對稱分量之和，即x(n)=xep(n)+xop(n),0≤n≤N-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/2［x(n)+x*(N-n)］(3.2.13)xop(n)=1/2［x(n)-x*(N-n)］(3.2.14)234.DFT的共軛對稱性23

(1)如果x(n)=xr(n)+jxi(n)其中xr(n)=Re[x(n)]=1/2[x(n)+x*(n)]jxi(n)=jIm[x(n)]=1/2[x(n)-x*(n)]則DFT[xr(n)]=1/2DFT[x(n)+x*(n)］=1/2[X(k)+X*(N-k)]=Xep(k)DFT[jxi(n)]=1/2DFT[x(n)-x*(n)]=1/2[X(k)-X*(N-k)]=Xop(k)由DFT的線性性質(zhì)可得

X(k)=DFT[x(n)]=Xep(k)+Xop(k)(3.2.16)其中Xep(k)=DFT[xr(n)]，X(k)的共軛對稱分量Xop(k)=DFT[jxi(n)]，X(k)的共軛反對稱分量24(1)如果x(n)=xr(n)+jxi(n)(2)如果x(n)=xep(n)+xop(n)，0≤n≤N-1(3.2.17)其中xep(n)=1/2[x(n)+x*(N-n)]，x(n)的共軛對稱分量xop(n)=1/2[x(n)-x*(N-n)]，x(n)的共軛反對稱分量則DFT[xep(n)]=1/2DFT[x(n)+x*(N-n)]=1/2[X(k)+X*(k)]=Re[X(k)]DFT[xop(n)]=1/2DFT[x(n)-x*(N-n)]=1/2[X(k)-X*(k)]=jIm[X(k)]因此X(k)=DFT[x(n)]=XR(k)+jXI(k)(3.2.18)其中XR(k)=Re[X(k)]=DFT[xep(n)]jXI(k)=jIm[X(k)]=DFT[xop(n)]

25(2)如果x(n)=xep(n)+xop(n)，0≤n有限長實序列DFT的共軛對稱性說明：設x(n)是長度為N的實序列，且X(k)=DFT[x(n)]，則(1)X(k)共軛對稱，即X(k)=X*(N-k),0≤k≤N-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有限長實序列DFT的共軛對稱性說明：26

利用DFT的共軛對稱性，通過計算一個N點DFT，可以得到兩個不同實序列的N點DFT。設x1(n)和x2(n)為兩個實序列，構(gòu)成新序列x(n)如下：x(n)=x1(n)+jx2(n)對x(n)進行DFT，得到X(k)=DFT[x(n)]=Xep(k)+Xop(k)由(3.2.16)式、(3.2.13)式、(3.2.14)式得到

Xep(k)=DFT[x1(n)]=1/2[X(k)+X*(N-k)]Xop(k)=DFT[jx2(n)]=1/2[X(k)-X*(N-k)]

所以

X1(k)=DFT[x1(n)]=1/2[X(k)+X*(N-k)]X2(k)=DFT[x2(n)]=-j1/2[X(k)-X*(N-k)]27利用DFT的共軛對稱性，通過計算2.1.4DFT的矩陣計算DFT計算也可以采用矩陣計算法，這樣可以利用計算機中的矩陣乘法子程序。282.1.4DFT的矩陣計算DFT1.DFT的矩陣計算根據(jù)DFT定義有用一組線性方程表示為291.DFT的矩陣計算29令[x(n)]=[x(0)，x(1)，x(2)，…，x(N-1)]T

[X(k)]=[X(0)，X(1)，X(2)，…，X(N-1)]T則方程組可用矩陣表示為

[X(k)]=[AN][x(n)]30令[x(n)]=[x(0)，x(1)2.IDFT的矩陣計算根據(jù)IDFT定義有類似地，可將逆變換表示為其中[AN*]是[AN]的共軛矩陣，即312.IDFT的矩陣計算31顯然，當N確定時，[AN]與[AN*]為常數(shù)矩陣，只要給定[x(n)]或[X(k)]就可以通過矩陣計算出[X(k)]或[x(n)]。用計算機程序?qū)崿F(xiàn)時，可以事先將[AN]與[AN*]存儲在內(nèi)存中。[AN]與[AN*]中各元素由旋轉(zhuǎn)因子組成，利用旋轉(zhuǎn)因子的周期性，可將[AN]與[AN*]簡化。即[AN]與[AN*]中實際只包含N個不相同的元素：，，，……，或，，，……，因此，只要確定出上述N個值，即可確定[AN]或[AN*]。32顯然，當N確定時，[AN]與[AN有兩種確定方法：(1)定義計算(2)幾何計算將單位圓從正實軸開始N等分，等分點在Z平面上的坐標即確定了的值。對于[AN]，按i=0~N-1在單位圓上順時針取點；對于[AN*]，按i=0~N-1在單位圓上逆時針取點。33有兩種確定方法：33以N=8為例計算[AN]與[AN*]。顯然有，34以N=8為例計算[AN]與[AN*]。34于是35于是35例：計算x(t)=cos(2πt)的頻譜。解:(1)對x(t)采樣根據(jù)采樣定理，余弦信號一周至少采3個點，取N=4，則[x(n)]=[1,0,-1,0]T

(2)求X(k)(3)將X(k)的觀察區(qū)間位移到-N/2~N/2-1，得X(-2)=0,X(-1)=2,X(0)=0,X(1)=2,(4)離散頻譜與連續(xù)頻譜的對比頻域采樣間隔fδ=1/T0=1/TP=1由圖中可看出X(f)=(1/N)X(k)(f=kfδ)該結(jié)論證明略。X(f)1/21/2-11fX(k)22-11k36例：計算x(t)=cos(2πt)的頻譜。X(f)1/21/

時域

頻域非周期，連續(xù)x(t)X(jΩ)或X(f)非周期，連續(xù)無限長序列x(n)X(ejω)周期，連續(xù)周期N(T0)，序列x(n)X(k)周期N(1/T=fs),離散

時域采樣間隔Tt=nTf=k(1/T0)頻域采樣間隔1/T0=kfδfδX(f)=(1/N)X(k)(f=kfδ)

Ω=2πfω=ΩT37

2.2

快速傅里葉變換(FFT)頻譜分析作為信號處理的基本工具已在多學科領域得到應用。然而DFT運算量大，使應用受到限制。1965年，庫利—圖基(Cooley-Tukey)發(fā)表了快速計算DFT的方法，使DFT得到實際應用，并由此發(fā)展成為稱之為快速傅立葉變換(FFT)的一類算法。FFT僅是DFT的一類特殊計算方法。它的價值在于：將DFT的計算時間減少1~2個數(shù)量級（甚至性能改善達100倍之多）。它的重要性在于：明顯地證明了采用數(shù)字方法進行頻譜分析較之用模擬方法更經(jīng)濟。382.2快速傅里葉變換(FFT)2.2.1FFT原理長度為N的有限長序列x(n)的DFT為考慮x(n)為復數(shù)序列的一般情況，對某一個k值，直接按(4.2.1)式計算X(k)值需要N次復數(shù)乘法、(N-1)次復數(shù)加法，N點DFT的復乘次數(shù)為N2，復加次數(shù)為N(N-1)。(4.2.1)392.2.1FFT原理(4.2.1)39FFT的基本原理是：把N點序列的DFT逐次分解為若干個較短序列DFT的線性組合。分解的效果是：DFT的乘法和加法次數(shù)大大減少。分解的方法不同，導致不同的FFT算法。在FFT算法中，普遍利用了旋轉(zhuǎn)因子WNm的周期性和對稱性。即周期性為對稱性為(4.2.2)40FFT的基本原理是：把N點序列的D以一種序列分解法----時間抽取法為例說明FFT原理。設N為合數(shù)，即N=M·L，則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以一種序列分解法----時間抽取法為例說明FFT原理由此，DFT可寫為式中，復數(shù)乘法次數(shù)：ML2+NM=N(M+L)復數(shù)加法次數(shù)：ML(L-1)+N(M-1)=N(M+L-2)當L、M均大于1時，有N(M+L)<N2N(M+L-2)<N(N-1)即分解減少了計算次數(shù)。42由此，DFT可寫為42若L也為合數(shù)的話，則上述分解可繼續(xù)，從而使計算次數(shù)進一步降低。當N=P1·P2·

P3·

·

·

Pk時，按上述逐次分解方法可得計算次數(shù)為復數(shù)乘法：N(P1+P2+

P3+

·

·

·

+

Pk)復數(shù)加法：N(P1+P2+

P3+

·

·

·

+

Pk-k)當Pi各不相同時，按上述逐次分解方法得到的FFT算法稱為混基FFT；當Pi=r(即N=rk)時，得到的FFT算法稱為基rFFT；當r=2時，得到常用的基2FFT。43若L也為合數(shù)的話，則上述分解可繼續(xù)2.2.2基2FFT1.時間抽取法設序列x(n)的長度為N，且滿足按n的奇偶把x(n)分解為兩個N/2點的子序列為自然數(shù)

442.2.2基2FFT為自然數(shù)44則x(n)的DFT為其中kr45則x(n)的DFT為kr45由于X1(k)和X2(k)均以N/2為周期，且所以X(k)又可表示為(4.2.7)(4.2.8)

圖4.2.1蝶形運算符號46由于X1(k)和X2(k)均以N/2為周期，且(4.2.7)圖4.2.2N點DFT的一次時域抽取分解圖(N=8)47圖4.2.2N點DFT的一次時域抽取分解圖(N=8)4與第一次分解相同，將x1(r)按奇偶分解成兩個N/4長的子序列x3(l)和x4(l)，即那么，X1(k)又可表示為同理，由X3(k)和X4(k)的周期性和WmN/2的對稱性得：1(4.2.9)(4.2.10)48與第一次分解相同，將x1(r)按奇偶用同樣的方法可計算出其中(4.2.11)49用同樣的方法可計算出(4.2.11)49圖4.2.3N點DFT的第二次時域抽取分解圖(N=8)

50圖4.2.3N點DFT的第二次時域抽取分解圖(N=8)圖4.2.4N點時域抽取FFT運算流圖(N=8)蝶形運算，同址計算，序列倒序，系數(shù)WNr確定51圖4.2.4N點時域抽取FFT運算流圖(N=8)51算法復雜度：設P(N)表示N點DFT所需復數(shù)乘法計算次數(shù)，Q(N)表示N點DFT所需復數(shù)加法計算次數(shù)，則按時間抽取法得到當將DFT最終分解為2點時，P(2)=1，Q(2)=2。將此初始條件帶入上式遞歸求解得取N=1024，基2FFT速度比DFT提高200倍。52算法復雜度：52圖4.2.5FFT算法與DFT定義計算之間乘法次數(shù)比較曲線

53圖4.2.5FFT算法與DFT定義計算之間乘法次數(shù)比較曲2.頻率抽取法設序列x(n)長度為N=2M，首先將x(n)前后對半分開，得到兩個子序列，其DFT可表示為如下形式：542.頻率抽取法54將X(k)分為偶數(shù)與奇數(shù)組，當k取偶數(shù)(k=2r,r=0,1,…,N/2-1)時當k取奇數(shù)(k=2r+1,r=0,1,…,N/2-1)時偶數(shù)奇數(shù)(4.2.15)?(4.2.14)rn55偶數(shù)奇數(shù)(4.2.15)?(4.2.14)rn55將x1(n)和x2(n)分別代入(4.2.14)和(4.2.15)式，可得(4.2.16)圖4.2.10DIF―FFT蝶形運算流圖符號

56將x1(n)和x2(n)分別代入(4.2.14)和(4.2.圖4.2.12DIF―FFT二次分解運算流圖(N=8)

57圖4.2.12DIF―FFT二次分解運算流圖(N=8)圖4.2.13DIF―FFT運算流圖(N=8)

58圖4.2.13DIF―FFT運算流圖(N=8)583.DFT程序#include<stdio.h>#include<stdlib.h>#include<math.h>#include"msp.h"voidmcmpdft(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.real=0.0;for(m=0;m<n;m++){y[m]=x[0];for(k=1;k<n;k++){ts.imag=t.imag*k*m;z=cexp(ts);y[m].real+=x[k].real*z.real-x[k].imag*z.imag;y[m].imag+=x[k].real*z.imag+x[k].imag*z.real;}if(isign==1){y[m].real/=n;y[m].imag/=n;}}}593.DFT程序complext,ts,z;4.FFT程序#include<stdio.h>#include<stdlib.h>#include<math.h>#include"msp.h"voidmcmpfft(complexx[],intn,intisign){/*----------------------------------------------------------Routinemcmpfft:toobtaintheDFTofComplexDatax(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;i<=16;i++){ nn=pow(2,i); if(n==nn)break; } if(i>16) { printf("Nisnotapowerof2!\n"); return; } z.real=0.0;pisign=4*isign*atan(1.);mr=0;for(m=1;m<n;m++){l=n;while(mr+l>=n)l=l/2;mr=mr%l+l;if(mr<=m)continue;604.FFT程序complext,z,ce;60t.real=x[m].real;t.imag=x[m].imag;x[m].real=x[mr].real;x[m].imag=x[mr].imag;x[mr].real=t.real;x[mr].imag=t.imag;}/*------------------------------------------------------*/ l=1; while(1) { if(l>=n) { if(isign==-1) return; for(j=0;j<n;j++) { x[j].real=x[j].real/n; x[j].imag=x[j].imag/n; } return; } for(m=0;m<l;m++) { for(i=m;i<n;i=i+2*l) { z.imag=m*pisign/l; ce=cexp(z); t.real=x[i+l].real*ce.real-x[i+l].imag*ce.imag;t.imag=x[i+l].real*ce.imag+x[i+l].imag*ce.real; x[i+l].real=x[i].real-t.real; x[i+l].imag=x[i].imag-t.imag; x[i].real=x[i].real+t.real; x[i].imag=x[i].imag+t.imag;} } l=2*l; }}61t.real=x[m].real;t2.2.3利用FFT計算IDFTDFT和IDFT的運算公式為：

由于

對上式兩邊同時取共軛，得可見，利用FFT也可計算IDFT。nX(k)622.2.3利用FFT計算IDFTnX(k)622.3離散卷積由于卷積運算可以描述線性時不變系統(tǒng)，因此它在信號處理中具有重要作用。離散系統(tǒng)中的卷積用離散卷積計算。2.3.1定義若x1(n)與x2(n)是寬度為N的有限時寬序列，則定義為x1(n)與x2(n)的離散卷積，記作x1(n)*x2(n)。因為離散信號（有限時寬序列）被看作周期序列，因此y(n)也具有周期特性，且周期為N，故離散卷積又稱作循環(huán)卷積。632.3離散卷積由于卷積運算可2.3.2循環(huán)卷積定理若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))。卷積定理指出了相乘與卷積運算的關(guān)系，同時給出了卷積運算的另一途徑，即由卷積定理也可以推論出x1(n)*x2(n)的周期為N。DFTDFTx1(n)x2(n)X1(k)X2(k)x1(n)*x2(n)X1(k)?X2(k)IDFT642.3.2循環(huán)卷積定理DFTDFTx1(n)x2(n)X2.3.3循環(huán)卷積與線性卷積的關(guān)系設x1(n)與x2(n)是寬度分別為N1、N2的有限時寬序列，則循環(huán)卷積：線性卷積：其中，循環(huán)卷積長度N3=max{N1，N2}線性卷積長度N4=N1+N2-1顯然，N3<N4可以證明也即循環(huán)卷積是線性卷積以循環(huán)卷積長度進行周期化并疊加（時域混疊）的結(jié)果。652.3.3循環(huán)卷積與線性卷積的關(guān)系652.3.4利用循環(huán)卷積求解線性卷積實際信號處理中，特別是分析處理模擬系統(tǒng)時，我們經(jīng)常需要獲得線性卷積，而利用計算機這類數(shù)字設備只能實現(xiàn)循環(huán)卷積，所以需要解決用循環(huán)卷積求解線性卷積的問題。662.3.4利用循環(huán)卷積求解線性卷積66

兩個有限長序列的線性卷積從循環(huán)卷積與線性卷積的關(guān)系可知，如果將循環(huán)卷積的長度定義為線性卷積有效結(jié)果的長度，即取N3≥N4=N1+N2-1則循環(huán)卷積一個周期內(nèi)的序列值與線性卷積完全相同。這樣，通過周期擴展，就可以用循環(huán)卷積的計算結(jié)果表示線性卷積，稱此為擴展周期法。這可以理解為：將時域x1(n)與x2(n)補零至N4長度，導致其頻譜采樣間隔變小，采樣精度提高，從而減小(消除)了由頻譜X1(k)?X2(k)確定的時域卷積序列x1(n)*x2(n)中的混疊現(xiàn)象，使得循環(huán)卷積與線性卷積結(jié)果一致。67兩個有限長序列的線性卷積67因此，對兩個有限長序列計算線性卷積的方法為：ⅰ.確定循環(huán)卷積的計算長度，即N≥N1+N2-1其中，N1與N2分別為序列x1(n)與x2(n)長度(即周期)；ⅱ.將x1(n)與x2(n)分別補零至長度為N；ⅲ.對x1(n)與x2(n)分別求出N點的DFT為X1(k)與X2(k)；ⅳ.計算X1(k)?X2(k)；ⅴ.求X1(k)?X2(k)的N點IDFT為x1(n)*x2(n)，該結(jié)果即為線性卷積。注：算法中的DFT與IDFT均可利用FFT求解；ⅲ~ⅴ也可以通過直接計算N長度的離散卷積所替代。68因此，對兩個有限長序列計算線性卷積的方法為：68例：已知h=[1,2,-1,1]，x=[1,1,2,1,2,2,1,1]，求y=h*x。解：y=[1,3,3,5,3,7,4,3,3,0,1]Ly=8+4-1=11

x0x1x2x3x4

h0h0x0h0x1h0x2h0x3h0x4

h1h1x0h1x1h1x2h1x3h1x4h2h2x0h2x1h2x2h2x3h2x4h3h3x0h3x1h3x2h3x3h3x4線性卷積表h\x11212211111212211222424422-1-1-1-2-1-2-2-1-111121221169例：已知h=[1,2,-1,1]，x0

x0x1x2x3x4000h0h0x0h0x1h0x2h0x3h0x4000h10h1x0h1x1h1x2h1x3h1x400h200

h2x0h2x1h2x2h2x3h2x40h3000

h3x0h3x1h3x2h3x3h3x4y0y1y2y3y4y5y6y7h\x11212211000111212211000202242442200-100-1-1-2-1-2-2-1-10100011212211yn1335374330170x0x1x圖3.4.2線性卷積與循環(huán)卷積

71圖3.4.2線性卷積與循環(huán)卷積712.4FFT應用

DFT快速算法FFT的出現(xiàn)，使DFT在數(shù)字通信、語言信號處理、圖像處理、功率譜估計、仿真、系統(tǒng)分析、雷達理論、光學、醫(yī)學、地震以及數(shù)值分析等各個領域都得到廣泛應用。722.4FFT應用DFT快

2.4.1利用FFT進行分段卷積在實際信號處理中，被卷積的兩個序列之一可能是無限長序列或長度比另一序列長很多。利用擴展循環(huán)卷積周期的方法，可能不是有效的和實際的。ⅰ.擴展周期法意味著，整個較長的序列在進行卷積之前必須完全出現(xiàn)；ⅱ.由于整個序列完全出現(xiàn)之前不進行卷積處理，導致輸出有較長的延遲；ⅲ.如果N1+N2-1太大，因需要大量的存儲單元及對FFT算法實際的考慮，使卷積計算已不現(xiàn)實；如果N1+N2-1無窮大，卷積計算已不可能。732.4.1利用FFT進行分段卷積73有兩種方法用來解決上述問題：重疊相加法，重疊保留法。

重疊相加法設序列h(n)長度為N，x(n)為無限長序列。將x(n)均勻分段，每段長度取M，則于是，h(n)與x(n)的線性卷積可表示為(3.4.4)k=074有兩種方法用來解決上述問題：重疊相加法，重疊保留法。(3.若每段卷積yi(n)按線性卷積長度計算，則yi(n)結(jié)果相加即為線性卷積y(n)。該方法歸納為：ⅰ.將序列x(n)以M為長度順序分段為xi(n)（M的經(jīng)驗選擇：M>N且與N數(shù)量級相同）；ⅱ.對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)ⅳ.對各段卷積求和，即注：該方法中，各段yi(n)是以線性卷積計算的。75若每段卷積yi(n)按線性卷積長度計算，則yi(n)結(jié)果相加圖3.4.4重疊相加法卷積示意圖76圖3.4.4重疊相加法卷積示意圖76重疊保留法仍然采用分段求卷積再組合的方法。該方法與重疊相加法的區(qū)別為：ⅰ.對序列x(n)以M為長度重疊分段為xi(n)，其后段與前段有N-1個重疊點；ⅱ.每段以M為周期計算循環(huán)卷積；(用FFT)ⅲ.將每段得到的循環(huán)卷積結(jié)果的前N-1個點去掉(這是循環(huán)卷積中的混疊部分)，然后將各段剩余部分(對應線性卷積結(jié)果)首尾銜接起來，即得到最終結(jié)果。77重疊保留法77重疊保留法卷積示意圖2M-(N-1)3M-2(N-1)78重疊保留法卷積示意圖2M-(N-1)3M-

2.4.2利用FFT對連續(xù)信號作頻譜分析所謂信號的譜分析就是計算信號的傅里葉變換。連續(xù)信號與系統(tǒng)的傅里葉分析顯然不便于直接用計算機系統(tǒng)實現(xiàn)，使其應用受到限制。DFT(FFT)是一種時域和頻域均離散化的變換，適合數(shù)值運算，成為分析離散信號和系統(tǒng)的有力工具。作為DFT的重要應用之一，就是利用FFT對連續(xù)信號作頻譜分析。

792.4.2利用FFT對連續(xù)信號作頻譜分析79實現(xiàn)流程為:頻率采樣間隔為模擬域fδ=1/T0=1/NT(T為時域采樣周期)

Ωδ=2π/(NT)

數(shù)字域ωδ=2π/N所以，頻率分辨率即為fδ=1/NT，fδ越小分辨率越高?？够殳B低通濾波器(預濾波)S/H及A/DFFTD/A再現(xiàn)濾波器(平滑濾波)sa(t)xa(t)x(n)w(n)xN(n)X(k)1/N(衰減因子)X(jΩ)80實現(xiàn)流程為:抗混疊低通濾波器S/H及A/DFFTD/A再現(xiàn)濾利用FFT分析連續(xù)信號頻譜的好處是可以用計算機進行高速頻譜計算，但有可能造成誤差，主要有三方面原因：1.混疊失真利用抗混疊模擬低通濾波器進行預濾波，使xa(t)頻譜中最高頻率分量不超過fh。設S/H或A/D的采樣頻率為fs，為了不產(chǎn)生頻域混疊，按照采樣定理，必須滿足fs≥2fh否則將產(chǎn)生頻譜混疊，稱為混疊失真。消除混疊誤差是以引入頻譜截斷誤差為代價的。81利用FFT分析連續(xù)信號頻譜的好處是由頻率分辨率fδ=1/NT≥2fh/N可看出，信號最高頻率fh(又稱高頻容量)與頻率分辨率fδ是相互矛盾的。在N一定時，增加fh，使fδ增加，即分辨力下降；提高分辨力(即減小fδ)，則需減小高頻容量fh。所以，對fh和fδ，保持一個不變而提高另一個性能的唯一方法是增加采樣點數(shù)N。增加采樣點數(shù)N的有效途徑：(1)增加觀察窗口寬度(記錄長度)T0，當T不變時，N=T0/T增加；(2)在一定記錄長度T0內(nèi)，提高采樣頻率(減小T)，使N=T0/T增加。82由頻率分辨率82例：用頻譜分析儀對模擬信號進行譜分析，要求譜分辨率fδ≤5Hz，信號最高頻率fh=2.5kHz，試確定最小記錄時間T0min，最低采樣頻率fsmin，最少采樣點數(shù)Nmin。如果fh不變，要求譜分辨率提高一倍，最少采樣點數(shù)和最小記錄時間是多少?解：T0=1/fδ≥1/5=0.2(s)，T0min=0.2sfs≥2fh=2×2.5=5(kHz)，fsmin=5kHzN≥2fh/fδ=2×2.5×103/5=103，Nmin=103頻率分辨率提高一倍，即fδ=5Hz/2，則Nmin=2fh/fδ=5×103/2.5=2×103

T0min=1/fδ=1/2.5=0.4s83例：用頻譜分析儀對模擬信號進行譜分析，要求譜分辨率fδ≤52.頻譜泄露對時寬無限或長時寬信號的DFT(FFT)處理，一般需在時域加窗將其轉(zhuǎn)換成有限時寬信號。x(n)?w(n)X(ejω)*W(ejω)頻域卷積造成：窗譜主瓣使信號頻譜加寬，窗譜旁瓣使信號頻譜出現(xiàn)波紋(皺波)，這種現(xiàn)象稱為頻譜泄露。泄露使被截信號頻譜與原信號頻譜之間出現(xiàn)誤差，只要加窗，泄露就不可避免，這是原理性誤差。泄露導致頻譜擴展，使fh可能超過奈奎斯特頻率(fs/2)，進一步加劇混疊失真。為了減小泄露影響，必須選擇合適的窗函數(shù)(窗口寬度，窗口形狀)。842.頻譜泄露84

圖3.4.11矩形窗函數(shù)的幅度譜

85圖3.4.11矩形窗函數(shù)的幅度譜85圖3.4.12加矩形窗前后的頻譜

86圖3.4.123.柵欄效應用DFT(FFT)計算的頻譜可以看作是連續(xù)信號頻譜的采樣值，我們只能在離散采樣點上看到真實的頻譜，就好象通過柵欄看一幅圖像一樣，這就是柵欄效應。柵欄效應可能會造成連續(xù)頻譜的某些峰值、谷值或細微變化被“柵欄”遮擋，使我們不能觀察(檢測)到，造成分析或恢復的不準確性。減小這種效應的方法是，在被加窗后的信號數(shù)據(jù)末端補若干零值，使FFT計算點數(shù)N增加，又不改變原有的記錄數(shù)據(jù)(相當于窗寬不變)。這樣就可以在保持原頻譜形狀不變的情況下，增加譜線密度，即頻域采樣點數(shù)增加，使原來看不見的頻譜分量變得可見。873.柵欄效應87除以上三方面外，CFT與DFT還有兩點不同：(1)DFT是周期的，CFT是非周期的DFT一個周期CFT(k=-N/2~N/2-1)(2)DFT幅值與CFT幅值不同X(k)=N·X(jΩ)Ω=2πk/(NT)

或

X(k)=N·X(f)f=k/(NT)88除以上三方面外，CFT與DFT還有兩點不同：882.4.3用FFT作頻譜計算(分析、測量)1.對較長信號作頻譜測量由DFT與Z變換關(guān)系得若實際信號x(n)長度無限或為L(L>N)，當希望獲得有限頻率點N上的頻譜測量時，如何實現(xiàn)？設x(n)的Z變換為則x(n)的N點DFT為892.4.3用FFT作頻譜計算(分析、測量)89由X(k)可確定出有限長序列xp(n)90由X(k)可確定出有限長序列xp(n)90該式說明，對L點或無限長信號要實現(xiàn)N個頻率點的頻譜測量，應先對時間序列以N為周期進行拓展，當L<N時，周期化的結(jié)果xp(n)無混疊，否則xp(n)含有混疊。令時域樣本數(shù)L滿足L=N?M其中N為希望的頻率樣本數(shù)，M為大于1的整數(shù)，則希望的頻譜為上式也說明，頻域較大的采樣間隔會造成時域信號混疊。91該式說明，對L點或無限長信號要實現(xiàn)N個頻率點的頻譜測2.對較短信號作頻譜測量設x(n)為長度是N的有限序列，若希望在單位圓上L(L>N)個等間隔頻率點上計算序列的頻譜，則實現(xiàn)方法為：定義則922.對較短信號作頻譜測量92用增加零值樣本來充實有限長序列這種簡單的方法，使我們能在環(huán)繞單位圓的一組等間隔頻率點上，以任意的頻率分辨率計算序列的頻譜，因而無論多高的頻率分辨力都能達到。非常有用的方法！3.在單位圓內(nèi)的某圓上作等間隔頻率點的頻譜測量設x(n)為長度是N的有限序列，欲作頻譜測量的圓半徑為r，則即將信號預先乘以r-n，再作FFT。93用增加零值樣本來充實有限長序列這種簡圖3.4.7單位圓與非單位圓采樣94圖3.4.7單位圓與非單位圓采樣944.周期序列的DFT設x(n)為周期序列，周期N，其N點的DFT為X(k)=XN(k)(1)截取有限長度M=mN，m為正整數(shù)，則(2)截取有限長度M≠mN時，XM(k)與X(k)無關(guān)聯(lián)，可通過使截取長度逐次加倍計算XM(k)，直至相鄰兩次計算在允許誤差范圍內(nèi)為止。k/m=整數(shù)k/m≠整數(shù)

954.周期序列的DFTk/m=整數(shù)k/m≠整數(shù)952.1離散傅里葉變換(DFT)2.2快速傅里葉變換(FFT)2.3離散卷積2.4FFT應用第2章離散傅里葉變換(DFT)962.1離散傅里葉變換(DFT)第2章離散傅里葉變換2.1離散傅里葉變換(DFT)

2.1.1DFT定義2.1.2DFT推導2.1.3DFT性質(zhì)2.1.4DFT的矩陣計算972.1離散傅里葉變換(DFT)2.1.1DFT2.1.1離散傅里葉變換的定義

1.定義

設x(n)是一個長度為N的有限長序列，則定義x(n)的N點離散傅里葉變換為X(k)的離散傅里葉逆變換為(3.1.2)式中，，N稱為DFT變換區(qū)間長度，通常稱(3.1.1)式和(3.1.2)式為離散傅里葉變換對。982.1.1離散傅里葉變換的定義1.定義X證明IDFT［X(k)］的唯一性。證明：把(3.1.1)式代入(3.1.2)式有為整數(shù)

為整數(shù)

所以，在變換區(qū)間上滿足下式：IDFT［X(k)］=x(n),0≤n≤N-1由此可見，(3.1.2)式定義的離散傅里葉逆變換是唯一的。99證明IDFT［X(k)］的唯一性。為整數(shù)為整數(shù)所以，在例3.1.1x(n)=R4(n)，求x(n)的8點和16點DFT。解：設變換區(qū)間N=8，則設變換區(qū)間N=16，則n16161615n100例3.1.1x(n)=R4(n)，求x(n)的8點和2.DFT的隱含周期性前面定義的DFT變換對中，x(n)與X(k)均為有限長序列，但由于的周期性，使(3.1.1)式和(3.1.2)式中的X(k)隱含了周期性，且周期為N。對任意整數(shù)m，總有均為整數(shù)所以(3.1.1)式中，X(k)滿足同理可證明(3.1.2)式中x(n+mN)=x(n)1012.DFT的隱含周期性均為整數(shù)所以(3.1.1)式中，實際上，任何周期為N的周期序列都可以看作長度為N的有限長序列x(n)的周期延拓序列，而x(n)則是的一個周期，即為了敘述方便，將(3.1.5)式用如下形式表示：

(3.1.7)102實際上，任何周期為N的周期序列圖3.1.2有限長序列及其周期延拓103圖3.1.2有限長序列及其周期延拓82.1.2DFT推導

1.由Z變換推導由Z變換可知，非周期序列x(n)的Z變換為對于有限長序列x(n)(n=0,…,N-1)，X(z)的收斂區(qū)域總包括單位圓。若在單位圓的N個均分點上計算Z變換，得周期序列為1042.1.2DFT推導1.由Z變換推導9

上式兩邊乘以，再對k從0~N-1求和，得這說明，長度小于或等于N的有限時寬序列可以用它的Z變換在單位圓上的N個取樣精確地表示，或有限時寬序列的DFT相當于其Z變換在單位圓等間隔點上的取樣。Z平面IR2π/N105上式兩邊乘以，再對k從0~N-1求和圖3.1.1X(k)與X(ejω)的關(guān)系

X(z)~X(ejω)~X(k)106圖3.1.1X(k)與X(ejω)的關(guān)系X(z2.由離散傅里葉級數(shù)推導

如果x(n)的長度為N，且，則可寫出的離散傅里葉級數(shù)為(3.1.8)

(3.1.9)

式中

(3.1.10)1072.由離散傅里葉級數(shù)推導(3.1.8)(3.1.3.由連續(xù)傅里葉變換推導設xa(t)與Xa(jΩ)構(gòu)成傅立葉變換對，則(1)時域采樣：將xa(t)離散化其頻譜為X(ejω)，是以2π為周期的周期函數(shù)，即1083.由連續(xù)傅里葉變換推導13(2)時域截斷：將xa(nT)由無限變?yōu)橛邢迺r寬x(n)x(n)=xa(nT)?w(t)其中且N=T0/T也即此時頻譜為X(ejΩT)*W(jΩ)，是Ω的連續(xù)周期函數(shù)。109(2)時域截斷：將xa(nT)由無限變?yōu)橛邢迺r寬x(n)1(3)頻域采樣：將頻譜離散化為周期序列，其時域函數(shù)為顯然，是以T0（T0=NT）為周期的序列，故其一周內(nèi)恰好為原信號xa(t)的N個采樣值。110(3)頻域采樣：將頻譜離散化15將上述求解，得令顯然完全由X(k)確定，而X(k)是以N為周期的序列，且在0~N-1區(qū)間上xa(nT)可用x(n)表示，于是111將上述求解，得16同樣，可推導出顯然，當時域采樣滿足時域采樣定理時，頻域不會發(fā)生混疊，這時，在0~N-1區(qū)間上定義的X(k)恰好表示Xa(jΩ)在帶限區(qū)域內(nèi)的采樣值；而當頻域采樣滿足頻域采樣定理時，時域才不會發(fā)生混疊，在0~N-1區(qū)間上定義的x(n)才能代表x(t)的有效采樣值。上述推導說明，離散傅立葉變換與連續(xù)傅立葉變換有密切關(guān)系。112同樣，可推導出172.1.3DFT性質(zhì)DFT有許多性質(zhì)與連續(xù)、序列傅里葉變換相似，但也有其獨特性，這主要源于它所隱含的周期性，即循環(huán)性。1.線性性如果x1(n)和x2(n)是兩個有限長序列，長度分別為N1和N2

y(n)=ax1(n)+bx2(n)0≤n≤N-1式中a、b為常數(shù)，N