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

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

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

1.定義

設(shè)x(n)是一個(gè)長(zhǎng)度為N的有限長(zhǎng)序列，則定義x(n)的N點(diǎn)離散傅里葉變換為X(k)的離散傅里葉逆變換為(3.1.2)式中，，N稱為DFT變換區(qū)間長(zhǎng)度，通常稱(3.1.1)式和(3.1.2)式為離散傅里葉變換對(duì)。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點(diǎn)和16點(diǎn)DFT。解：設(shè)變換區(qū)間N=8，則設(shè)變換區(qū)間N=16，則n16161615n5例3.1.1x(n)=R4(n)，求x(n)的8點(diǎn)和2.DFT的隱含周期性前面定義的DFT變換對(duì)中，x(n)與X(k)均為有限長(zhǎng)序列，但由于的周期性，使(3.1.1)式和(3.1.2)式中的X(k)隱含了周期性，且周期為N。對(duì)任意整數(shù)m，總有均為整數(shù)所以(3.1.1)式中，X(k)滿足同理可證明(3.1.2)式中x(n+mN)=x(n)62.DFT的隱含周期性均為整數(shù)所以(3.1.1)式中，實(shí)際上，任何周期為N的周期序列都可以看作長(zhǎng)度為N的有限長(zhǎng)序列x(n)的周期延拓序列，而x(n)則是的一個(gè)周期，即為了敘述方便，將(3.1.5)式用如下形式表示：

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

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

上式兩邊乘以，再對(duì)k從0~N-1求和，得這說明，長(zhǎng)度小于或等于N的有限時(shí)寬序列可以用它的Z變換在單位圓上的N個(gè)取樣精確地表示，或有限時(shí)寬序列的DFT相當(dāng)于其Z變換在單位圓等間隔點(diǎn)上的取樣。Z平面IR2π/N10上式兩邊乘以，再對(duì)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.由離散傅里葉級(jí)數(shù)推導(dǎo)

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

(3.1.9)

式中

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

y(n)=ax1(n)+bx2(n)0≤n≤N-1式中a、b為常數(shù)，N=max[N1,N2]，則y(n)的N點(diǎ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點(diǎn)DFT。該性質(zhì)說明，DFT適用于離散線性系統(tǒng)。182.1.3DFT性質(zhì)DFT2.循環(huán)位移性質(zhì)若x(n)X(k)成立，則x(n-n0)X(k)稱為時(shí)間位移性(1)或x(n)X(k-k0)稱為頻率位移性(2)(1)說明時(shí)域信號(hào)的加載時(shí)刻，對(duì)信號(hào)DFT的幅度不產(chǎn)生任何影響，只在頻域引入一線性相移。(2)說明用特定頻率的余弦（或正弦）對(duì)信號(hào)進(jìn)行調(diào)制，其結(jié)果是信號(hào)的頻譜發(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.對(duì)稱性若x(n)X(k)成立，則x*(n)X*(-k)（復(fù)共軛序列的DFT）或x*(-n)X*(k)或(1/N)X(n)x(-k)說明DFT的時(shí)域與頻域具有對(duì)偶關(guān)系。213.對(duì)稱性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的共軛對(duì)稱性

如同任何實(shí)函數(shù)都可以分解成偶對(duì)稱分量和奇對(duì)稱分量一樣，任何有限長(zhǎng)序列x(n)也可以表示成其共軛對(duì)稱分量和共軛反對(duì)稱分量之和，即x(n)=xep(n)+xop(n),0≤n≤N-1(3.2.11)將式中的n換成N-n，并取復(fù)共軛，得到

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的共軛對(duì)稱性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)的共軛對(duì)稱分量Xop(k)=DFT[jxi(n)]，X(k)的共軛反對(duì)稱分量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)的共軛對(duì)稱分量xop(n)=1/2[x(n)-x*(N-n)]，x(n)的共軛反對(duì)稱分量則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有限長(zhǎng)實(shí)序列DFT的共軛對(duì)稱性說明：設(shè)x(n)是長(zhǎng)度為N的實(shí)序列，且X(k)=DFT[x(n)]，則(1)X(k)共軛對(duì)稱，即X(k)=X*(N-k),0≤k≤N-1(3.2.19)(2)如果x(n)=x(N-n)，則X(k)實(shí)偶對(duì)稱，即X(k)=X(N-k)(3.2.20)(3)如果x(n)=-x(N-n)，則X(k)純虛奇對(duì)稱，即X(k)=-X(N-k)(3.2.21)

26有限長(zhǎng)實(shí)序列DFT的共軛對(duì)稱性說明：26

利用DFT的共軛對(duì)稱性，通過計(jì)算一個(gè)N點(diǎn)DFT，可以得到兩個(gè)不同實(shí)序列的N點(diǎn)DFT。設(shè)x1(n)和x2(n)為兩個(gè)實(shí)序列，構(gòu)成新序列x(n)如下：x(n)=x1(n)+jx2(n)對(duì)x(n)進(jì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的共軛對(duì)稱性，通過計(jì)算2.1.4DFT的矩陣計(jì)算DFT計(jì)算也可以采用矩陣計(jì)算法，這樣可以利用計(jì)算機(jī)中的矩陣乘法子程序。282.1.4DFT的矩陣計(jì)算DFT1.DFT的矩陣計(jì)算根據(jù)DFT定義有用一組線性方程表示為291.DFT的矩陣計(jì)算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ì)算根據(jù)IDFT定義有類似地，可將逆變換表示為其中[AN*]是[AN]的共軛矩陣，即312.IDFT的矩陣計(jì)算31顯然，當(dāng)N確定時(shí)，[AN]與[AN*]為常數(shù)矩陣，只要給定[x(n)]或[X(k)]就可以通過矩陣計(jì)算出[X(k)]或[x(n)]。用計(jì)算機(jī)程序?qū)崿F(xiàn)時(shí)，可以事先將[AN]與[AN*]存儲(chǔ)在內(nèi)存中。[AN]與[AN*]中各元素由旋轉(zhuǎn)因子組成，利用旋轉(zhuǎn)因子的周期性，可將[AN]與[AN*]簡(jiǎn)化。即[AN]與[AN*]中實(shí)際只包含N個(gè)不相同的元素：，，，……，或，，，……，因此，只要確定出上述N個(gè)值，即可確定[AN]或[AN*]。32顯然，當(dāng)N確定時(shí)，[AN]與[AN有兩種確定方法：(1)定義計(jì)算(2)幾何計(jì)算將單位圓從正實(shí)軸開始N等分，等分點(diǎn)在Z平面上的坐標(biāo)即確定了的值。對(duì)于[AN]，按i=0~N-1在單位圓上順時(shí)針取點(diǎn)；對(duì)于[AN*]，按i=0~N-1在單位圓上逆時(shí)針取點(diǎn)。33有兩種確定方法：33以N=8為例計(jì)算[AN]與[AN*]。顯然有，34以N=8為例計(jì)算[AN]與[AN*]。34于是35于是35例：計(jì)算x(t)=cos(2πt)的頻譜。解:(1)對(duì)x(t)采樣根據(jù)采樣定理，余弦信號(hào)一周至少采3個(gè)點(diǎn)，取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ù)頻譜的對(duì)比頻域采樣間隔fδ=1/T0=1/TP=1由圖中可看出X(f)=(1/N)X(k)(f=kfδ)該結(jié)論證明略。X(f)1/21/2-11fX(k)22-11k36例：計(jì)算x(t)=cos(2πt)的頻譜。X(f)1/21/

時(shí)域

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

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

Ω=2πfω=ΩT37

2.2

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

P3·

·

·

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

P3+

·

·

·

+

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

P3+

·

·

·

+

Pk-k)當(dāng)Pi各不相同時(shí)，按上述逐次分解方法得到的FFT算法稱為混基FFT；當(dāng)Pi=r(即N=rk)時(shí)，得到的FFT算法稱為基rFFT；當(dāng)r=2時(shí)，得到常用的基2FFT。43若L也為合數(shù)的話，則上述分解可繼續(xù)2.2.2基2FFT1.時(shí)間抽取法設(shè)序列x(n)的長(zhǎng)度為N，且滿足按n的奇偶把x(n)分解為兩個(gè)N/2點(diǎn)的子序列為自然數(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蝶形運(yùn)算符號(hào)46由于X1(k)和X2(k)均以N/2為周期，且(4.2.7)圖4.2.2N點(diǎn)DFT的一次時(shí)域抽取分解圖(N=8)47圖4.2.2N點(diǎn)DFT的一次時(shí)域抽取分解圖(N=8)4與第一次分解相同，將x1(r)按奇偶分解成兩個(gè)N/4長(zhǎng)的子序列x3(l)和x4(l)，即那么，X1(k)又可表示為同理，由X3(k)和X4(k)的周期性和WmN/2的對(duì)稱性得：1(4.2.9)(4.2.10)48與第一次分解相同，將x1(r)按奇偶用同樣的方法可計(jì)算出其中(4.2.11)49用同樣的方法可計(jì)算出(4.2.11)49圖4.2.3N點(diǎn)DFT的第二次時(shí)域抽取分解圖(N=8)

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

53圖4.2.5FFT算法與DFT定義計(jì)算之間乘法次數(shù)比較曲2.頻率抽取法設(shè)序列x(n)長(zhǎng)度為N=2M，首先將x(n)前后對(duì)半分開，得到兩個(gè)子序列，其DFT可表示為如下形式：542.頻率抽取法54將X(k)分為偶數(shù)與奇數(shù)組，當(dāng)k取偶數(shù)(k=2r,r=0,1,…,N/2-1)時(shí)當(dāng)k取奇數(shù)(k=2r+1,r=0,1,…,N/2-1)時(shí)偶數(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蝶形運(yùn)算流圖符號(hào)

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

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

58圖4.2.13DIF―FFT運(yùn)算流圖(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計(jì)算IDFTDFT和IDFT的運(yùn)算公式為：

由于

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

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

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

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

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

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

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

Ωδ=2π/(NT)

數(shù)字域ωδ=2π/N所以，頻率分辨率即為fδ=1/NT，fδ越小分辨率越高?？够殳B低通濾波器(預(yù)濾波)S/H及A/DFFTD/A再現(xiàn)濾波器(平滑濾波)sa(t)xa(t)x(n)w(n)xN(n)X(k)1/N(衰減因子)X(jΩ)80實(shí)現(xiàn)流程為:抗混疊低通濾波器S/H及A/DFFTD/A再現(xiàn)濾利用FFT分析連續(xù)信號(hào)頻譜的好處是可以用計(jì)算機(jī)進(jìn)行高速頻譜計(jì)算，但有可能造成誤差，主要有三方面原因：1.混疊失真利用抗混疊模擬低通濾波器進(jìn)行預(yù)濾波，使xa(t)頻譜中最高頻率分量不超過fh。設(shè)S/H或A/D的采樣頻率為fs，為了不產(chǎn)生頻域混疊，按照采樣定理，必須滿足fs≥2fh否則將產(chǎn)生頻譜混疊，稱為混疊失真。消除混疊誤差是以引入頻譜截?cái)嗾`差為代價(jià)的。81利用FFT分析連續(xù)信號(hào)頻譜的好處是由頻率分辨率fδ=1/NT≥2fh/N可看出，信號(hào)最高頻率fh(又稱高頻容量)與頻率分辨率fδ是相互矛盾的。在N一定時(shí)，增加fh，使fδ增加，即分辨力下降；提高分辨力(即減小fδ)，則需減小高頻容量fh。所以，對(duì)fh和fδ，保持一個(gè)不變而提高另一個(gè)性能的唯一方法是增加采樣點(diǎn)數(shù)N。增加采樣點(diǎn)數(shù)N的有效途徑：(1)增加觀察窗口寬度(記錄長(zhǎng)度)T0，當(dāng)T不變時(shí)，N=T0/T增加；(2)在一定記錄長(zhǎng)度T0內(nèi)，提高采樣頻率(減小T)，使N=T0/T增加。82由頻率分辨率82例：用頻譜分析儀對(duì)模擬信號(hào)進(jìn)行譜分析，要求譜分辨率fδ≤5Hz，信號(hào)最高頻率fh=2.5kHz，試確定最小記錄時(shí)間T0min，最低采樣頻率fsmin，最少采樣點(diǎn)數(shù)Nmin。如果fh不變，要求譜分辨率提高一倍，最少采樣點(diǎn)數(shù)和最小記錄時(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例：用頻譜分析儀對(duì)模擬信號(hào)進(jìn)行譜分析，要求譜分辨率fδ≤52.頻譜泄露對(duì)時(shí)寬無限或長(zhǎng)時(shí)寬信號(hào)的DFT(FFT)處理，一般需在時(shí)域加窗將其轉(zhuǎn)換成有限時(shí)寬信號(hào)。x(n)?w(n)X(ejω)*W(ejω)頻域卷積造成：窗譜主瓣使信號(hào)頻譜加寬，窗譜旁瓣使信號(hào)頻譜出現(xiàn)波紋(皺波)，這種現(xiàn)象稱為頻譜泄露。泄露使被截信號(hào)頻譜與原信號(hào)頻譜之間出現(xiàn)誤差，只要加窗，泄露就不可避免，這是原理性誤差。泄露導(dǎo)致頻譜擴(kuò)展，使fh可能超過奈奎斯特頻率(fs/2)，進(jìn)一步加劇混疊失真。為了減小泄露影響，必須選擇合適的窗函數(shù)(窗口寬度，窗口形狀)。842.頻譜泄露84

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

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

86圖3.4.123.柵欄效應(yīng)用DFT(FFT)計(jì)算的頻譜可以看作是連續(xù)信號(hào)頻譜的采樣值，我們只能在離散采樣點(diǎn)上看到真實(shí)的頻譜，就好象通過柵欄看一幅圖像一樣，這就是柵欄效應(yīng)。柵欄效應(yīng)可能會(huì)造成連續(xù)頻譜的某些峰值、谷值或細(xì)微變化被“柵欄”遮擋，使我們不能觀察(檢測(cè))到，造成分析或恢復(fù)的不準(zhǔn)確性。減小這種效應(yīng)的方法是，在被加窗后的信號(hào)數(shù)據(jù)末端補(bǔ)若干零值，使FFT計(jì)算點(diǎn)數(shù)N增加，又不改變?cè)械挠涗洈?shù)據(jù)(相當(dāng)于窗寬不變)。這樣就可以在保持原頻譜形狀不變的情況下，增加譜線密度，即頻域采樣點(diǎn)數(shù)增加，使原來看不見的頻譜分量變得可見。873.柵欄效應(yīng)87除以上三方面外，CFT與DFT還有兩點(diǎn)不同：(1)DFT是周期的，CFT是非周期的DFT一個(gè)周期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還有兩點(diǎn)不同：882.4.3用FFT作頻譜計(jì)算(分析、測(cè)量)1.對(duì)較長(zhǎng)信號(hào)作頻譜測(cè)量由DFT與Z變換關(guān)系得若實(shí)際信號(hào)x(n)長(zhǎng)度無限或?yàn)長(zhǎng)(L>N)，當(dāng)希望獲得有限頻率點(diǎn)N上的頻譜測(cè)量時(shí)，如何實(shí)現(xiàn)？設(shè)x(n)的Z變換為則x(n)的N點(diǎn)DFT為892.4.3用FFT作頻譜計(jì)算(分析、測(cè)量)89由X(k)可確定出有限長(zhǎng)序列xp(n)90由X(k)可確定出有限長(zhǎng)序列xp(n)90該式說明，對(duì)L點(diǎn)或無限長(zhǎng)信號(hào)要實(shí)現(xiàn)N個(gè)頻率點(diǎn)的頻譜測(cè)量，應(yīng)先對(duì)時(shí)間序列以N為周期進(jìn)行拓展，當(dāng)L<N時(shí)，周期化的結(jié)果xp(n)無混疊，否則xp(n)含有混疊。令時(shí)域樣本數(shù)L滿足L=N?M其中N為希望的頻率樣本數(shù)，M為大于1的整數(shù)，則希望的頻譜為上式也說明，頻域較大的采樣間隔會(huì)造成時(shí)域信號(hào)混疊。91該式說明，對(duì)L點(diǎn)或無限長(zhǎng)信號(hào)要實(shí)現(xiàn)N個(gè)頻率點(diǎn)的頻譜測(cè)2.對(duì)較短信號(hào)作頻譜測(cè)量設(shè)x(n)為長(zhǎng)度是N的有限序列，若希望在單位圓上L(L>N)個(gè)等間隔頻率點(diǎn)上計(jì)算序列的頻譜，則實(shí)現(xiàn)方法為：定義則922.對(duì)較短信號(hào)作頻譜測(cè)量92用增加零值樣本來充實(shí)有限長(zhǎng)序列這種簡(jiǎn)單的方法，使我們能在環(huán)繞單位圓的一組等間隔頻率點(diǎn)上，以任意的頻率分辨率計(jì)算序列的頻譜，因而無論多高的頻率分辨力都能達(dá)到。非常有用的方法！3.在單位圓內(nèi)的某圓上作等間隔頻率點(diǎn)的頻譜測(cè)量設(shè)x(n)為長(zhǎng)度是N的有限序列，欲作頻譜測(cè)量的圓半徑為r，則即將信號(hào)預(yù)先乘以r-n，再作FFT。93用增加零值樣本來充實(shí)有限長(zhǎng)序列這種簡(jiǎn)圖3.4.7單位圓與非單位圓采樣94圖3.4.7單位圓與非單位圓采樣944.周期序列的DFT設(shè)x(n)為周期序列，周期N，其N點(diǎn)的DFT為X(k)=XN(k)(1)截取有限長(zhǎng)度M=mN，m為正整數(shù)，則(2)截取有限長(zhǎng)度M≠mN時(shí)，XM(k)與X(k)無關(guān)聯(lián)，可通過使截取長(zhǎng)度逐次加倍計(jì)算XM(k)，直至相鄰兩次計(jì)算在允許誤差范圍內(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應(yīng)用第2章離散傅里葉變換(DFT)962.1離散傅里葉變換(DFT)第2章離散傅里葉變換2.1離散傅里葉變換(DFT)

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

1.定義

設(shè)x(n)是一個(gè)長(zhǎng)度為N的有限長(zhǎng)序列，則定義x(n)的N點(diǎn)離散傅里葉變換為X(k)的離散傅里葉逆變換為(3.1.2)式中，，N稱為DFT變換區(qū)間長(zhǎng)度，通常稱(3.1.1)式和(3.1.2)式為離散傅里葉變換對(duì)。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點(diǎn)和16點(diǎn)DFT。解：設(shè)變換區(qū)間N=8，則設(shè)變換區(qū)間N=16，則n16161615n100例3.1.1x(n)=R4(n)，求x(n)的8點(diǎn)和2.DFT的隱含周期性前面定義的DFT變換對(duì)中，x(n)與X(k)均為有限長(zhǎng)序列，但由于的周期性，使(3.1.1)式和(3.1.2)式中的X(k)隱含了周期性，且周期為N。對(duì)任意整數(shù)m，總有均為整數(shù)所以(3.1.1)式中，X(k)滿足同理可證明(3.1.2)式中x(n+mN)=x(n)1012.DFT的隱含周期性均為整數(shù)所以(3.1.1)式中，實(shí)際上，任何周期為N的周期序列都可以看作長(zhǎng)度為N的有限長(zhǎng)序列x(n)的周期延拓序列，而x(n)則是的一個(gè)周期，即為了敘述方便，將(3.1.5)式用如下形式表示：

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

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

上式兩邊乘以，再對(duì)k從0~N-1求和，得這說明，長(zhǎng)度小于或等于N的有限時(shí)寬序列可以用它的Z變換在單位圓上的N個(gè)取樣精確地表示，或有限時(shí)寬序列的DFT相當(dāng)于其Z變換在單位圓等間隔點(diǎn)上的取樣。Z平面IR2π/N105上式兩邊乘以，再對(duì)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.由離散傅里葉級(jí)數(shù)推導(dǎo)

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

(3.1.9)

式中

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

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