3離散傅里葉變換

1第3章離散傅里葉變換(DFT)2

本章作為全書的基礎(chǔ)，主要學(xué)習(xí):

(1)DFT的定義；

(2)DFT的物理意義；

(3)DFT的基本性質(zhì)以及頻域采樣；

(4)DFT的應(yīng)用舉例等內(nèi)容。3離散傅里葉變換定義計(jì)算機(jī)只能處理有限長(zhǎng)離散序列，因而無(wú)法直接利用ZT與FT進(jìn)行數(shù)值計(jì)算。針對(duì)有限長(zhǎng)序列,還有一種更有用的數(shù)學(xué)變換,即離散傅里葉變換（DiscreteFourierTransform），使數(shù)字信號(hào)處理可以在頻域采用數(shù)字運(yùn)算的方法進(jìn)行，大大增加了數(shù)字信號(hào)處理的靈活性。4DFT的實(shí)質(zhì)：有限長(zhǎng)序列傅里葉變換的有限點(diǎn)離散采樣，即頻域離散化。DFT有多種快速算法(FastFourierTransform),因此不僅在理論上有重要意義,在各種數(shù)字信號(hào)處理算法中亦起著核心作用。從而使信號(hào)的實(shí)時(shí)處理和設(shè)備的簡(jiǎn)化得以實(shí)現(xiàn)。5DFT的定義設(shè)x(n)是一個(gè)長(zhǎng)度為M的有限長(zhǎng)序列，則定義x(n)的N點(diǎn)離散傅里葉變換為：X(k)的離散傅里葉逆變換為：6

對(duì)式中，，N稱為DFT變換區(qū)間長(zhǎng)度，N≥M。通常稱上述二式為離散傅里葉變換對(duì)。為了敘述簡(jiǎn)潔，常常用DFT［x(n)］N和IDFT［X(k)］N分別表示N點(diǎn)離散傅里葉變換和N點(diǎn)離散傅里葉逆變換。7【例】

x(n)=R4(n),

求x(n)的8點(diǎn)和16點(diǎn)DFT?！窘狻浚?）設(shè)變換區(qū)間N=8時(shí)，則：8

（2）設(shè)變換區(qū)間N=16時(shí)，則：9R4(n)的FT和DFT的幅度特性關(guān)系如下圖所示:

X(n)的幅頻特性曲線(FT曲線)X(n)的8點(diǎn)DFT曲線X(n)的16點(diǎn)DFT曲線10結(jié)論:

由此例可見(jiàn)，x(n)的離散傅里葉變換結(jié)果與變換區(qū)間長(zhǎng)度N的取值有關(guān)。在后面，對(duì)DFT與Z變換和傅里葉變換的關(guān)系及DFT的物理意義進(jìn)行討論后，上述問(wèn)題就會(huì)得到解釋。11DFT與傅里葉變換和Z變換的關(guān)系

設(shè)序列x(n)的長(zhǎng)度為M，其Z變換和N(N≥M)點(diǎn)DFT分別為：12

上二式表明序列x(n)的N點(diǎn)DFT是x(n)的Z變換在單位圓上的N點(diǎn)等間隔采樣。X(k)為x(n)的傅里葉變換。

比較上面二式可得關(guān)系式或13

DFT是X(ejω)在區(qū)間［0,2π］上的N點(diǎn)等間隔采樣。這就是DFT的物理意義。

DFT的變換區(qū)間長(zhǎng)度N不同，表示對(duì)X(ejω)在區(qū)間［0,2π］上的采樣間隔和采樣點(diǎn)數(shù)不同，所以DFT的變換結(jié)果不同。DFT的物理意義14DFT的隱含周期性

在DFT變換對(duì)中，x(n)與X(k)均為有限長(zhǎng)序列，但由于

的周期性，使DFT和IDFT式中的X(k)隱含周期性，且周期均為N。對(duì)任意整數(shù)m，總有在DFT式中，X（k)滿足：

15實(shí)際上，任何周期為N的周期序列都可以看做長(zhǎng)度為N的有限長(zhǎng)序列x(n)的周期延拓序列，而x(n)則是的一個(gè)周期，即16

一般稱周期序列中從n=0到N－1的第一個(gè)周期為的主值區(qū)間，而主值區(qū)間上的序列稱為的主值序列。因此x(n)與的上述關(guān)系可敘述為：是x(n)的周期延拓序列，x(n)是的主值序列。17

為了以后敘述簡(jiǎn)潔，當(dāng)N大于等于序列x(n)的長(zhǎng)度時(shí)，將式用如右形式表示：式中x((n))N表示x(n)以N為周期的周期延拓序列，((n))N表示模N對(duì)n求余，即如果

n=MN+n10≤n1≤N－1,M為整數(shù)則((n))N=n1

18例如，

,則有所得結(jié)果符合下圖所示的周期延拓規(guī)律。19

如果x(n)的長(zhǎng)度為N，且，則可寫出的離散傅里葉級(jí)數(shù)表示式式中即X(k)為的主值序列。20

因此可知，有限長(zhǎng)序列x(n)的N點(diǎn)離散傅里葉變換X(k)正好是x(n)的周期延拓序列x((n))N的離散傅里葉級(jí)數(shù)系數(shù)的主值序列，即。后面要討論的頻域采樣理論將會(huì)加深對(duì)這一關(guān)系的理解。我們知道，周期延拓序列頻譜完全由其離散傅里葉級(jí)數(shù)系數(shù)確定，因此，X(k)實(shí)質(zhì)上是x(n)的周期延拓序列x((n))N的頻譜特性，這就是N點(diǎn)DFT的物理意義。21

離散傅里葉變換的基本性質(zhì)

1線性性質(zhì)如果x1(n)和x2(n)是兩個(gè)有限長(zhǎng)序列，長(zhǎng)度分別為N1和N2,且y(n)=ax1(n)+bx2(n)式中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其中X1(k)和X2(k)分別為x1(n)和x2(n)的N點(diǎn)DFT。

222循環(huán)移位性質(zhì)：

(1)序列的循環(huán)移位設(shè)x(n)為有限長(zhǎng)序列，長(zhǎng)度為N，則x(n)的循環(huán)移位定義為

y(n)=x((n+m))NRN(N)

循環(huán)移位過(guò)程如下圖所示:23循環(huán)移位過(guò)程示意圖24

(2)時(shí)域循環(huán)移位定理：設(shè)x(n)

是長(zhǎng)度為N的有限長(zhǎng)序列，y(n)為x(n)的循環(huán)移位，即

y(n)=x((n+m))NRN(n)

則

Y(k)=DFT［y(n)］

其中X(k)=DFT［x(n)］,0≤k≤N-1。

25（3）頻域循環(huán)移位定理，如果

X(k)=DFT[x(n)],0≤k≤N-1Y(k)=X((k+l))NRN(k)

則

y(n)=IDFT[Y(k)]263循環(huán)卷積定理

有限長(zhǎng)序列x1(n)和x2(n)，長(zhǎng)度分別為N1和N2，N=max[N1,N2]。x1(n)和x2(n)的N點(diǎn)DFT分別為：

X1(k)=DFT［x1(n)］

X2(k)=DFT［x2(n)］如果X(k)=X1(k)·X2(k)

則或上式所表示的運(yùn)算稱為x1(n)與x2(n)的循環(huán)卷積。27

循環(huán)卷積過(guò)程中，要求對(duì)x2(m)循環(huán)反轉(zhuǎn)，循環(huán)移位，特別是兩個(gè)N長(zhǎng)的序列的循環(huán)卷積長(zhǎng)度仍為N。顯然與一般的線性卷積不同，故稱之為循環(huán)卷積，記為28由于所以即循環(huán)卷積亦滿足交換律。29頻域循環(huán)卷積定理：

如果x(n)=x1(n)x2(n)

則30

直接計(jì)算循環(huán)卷積較麻煩。計(jì)算機(jī)中采用矩陣相乘或快速傅里葉變換（FFT）的方法計(jì)算循環(huán)卷積。下面介紹用矩陣計(jì)算循環(huán)卷積的公式。31

當(dāng)n=0,1,2,…,L－1時(shí)，由x(n)形成的序列為：{x(0),x(1),…,x(L－1)}。循環(huán)移位后可得下面的矩陣：32上面矩陣稱為x(n)的L點(diǎn)“循環(huán)卷積矩陣”，其特點(diǎn)是:（1）第1行是序列{x(0),x(1),…,x(L－1)}的循環(huán)倒相序列。注意，如果x(n)的長(zhǎng)度M<L，則需要在x(n)末尾補(bǔ)L－M個(gè)零后，再形成第一行的循環(huán)倒相序列。（2）第1行以后的各行均是前一行向右循環(huán)移1位形成的。（3）矩陣的各主對(duì)角線上的序列值均相等。有了上面介紹的循環(huán)卷積矩陣，就可以寫出y(n)c的矩陣形式如下:3334按照上式，可以在計(jì)算機(jī)上用矩陣相乘的方法計(jì)算兩個(gè)序列的循環(huán)卷積，這里關(guān)鍵是先形成循環(huán)卷積矩陣。上式中如果h(n)的長(zhǎng)度N<L，則需要在h(n)末尾補(bǔ)L－N個(gè)零?！纠?/p>

計(jì)算下面給出的兩個(gè)長(zhǎng)度為4的序列h(n)與x(n)的4點(diǎn)和8點(diǎn)循環(huán)卷積。35

【解】

按照上式寫出h(n)與x(n)的4點(diǎn)循環(huán)卷積矩陣形式為h(n)與x(n)的8點(diǎn)循環(huán)卷積矩陣形式為36374復(fù)共軛序列的DFT

設(shè)x*(n)是x(n)的復(fù)共軛序列，長(zhǎng)度為NX(k)=DFT［x(n)］則

DFT［x*(n)］=X*(N-k),0≤k≤N-1

且

X(N)=X(0)385DFT的共軛對(duì)稱性（1）有限長(zhǎng)共軛對(duì)稱序列和共軛反對(duì)稱序列

為了區(qū)別于傅里葉變換中所定義的共軛對(duì)稱(或共軛反對(duì)稱)序列，下面用xep(n)和xop(n)分別表示有限長(zhǎng)共軛對(duì)稱序列和共軛反對(duì)稱序列，則二者滿足如下定義式：

xep(n)=x*ep(N-n),0≤n≤N-1xop(n)=-x*op(N-n),0≤n≤N-1

當(dāng)N為偶數(shù)時(shí)，將上式中的n換成N/2-n可得到：39

上式更清楚地說(shuō)明了有限長(zhǎng)序列共軛對(duì)稱性的含義。如下圖所示。圖中*表示對(duì)應(yīng)點(diǎn)為序列取共軛后的值。40共軛對(duì)稱與共軛反對(duì)稱序列示意圖41

如同任何實(shí)函數(shù)都可以分解成偶對(duì)稱分量和奇對(duì)稱分量一樣，任何有限長(zhǎng)序列x(n)都可以表示成其共軛對(duì)稱分量和共軛反對(duì)稱分量之和，即

x(n)=xep(n)+xop(n),0≤n≤N-1

將上式中的n換成N-n，并取復(fù)共軛，可得到

x*(N-n)=x*ep(N-n)+x*op(N-n)=xep(n)-xop(n)xep(n)=1/2［x(n)+x*(N-n)］

xop(n)=1/2［x(n)-x*(N-n)］42（2）DFT的共軛對(duì)稱性①x(n)的實(shí)部和虛部（包括j）的DFT分別為X(k)的共軛對(duì)稱分量和共軛反對(duì)稱分量證明：如果x(n)=xr(n)+jxi(n)

其中

xr=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)43

同理可得

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)

其中

Xep(k)=DFT［xr(n)］,X(k)的共軛對(duì)稱分量

Xop(k)=DFT［jxi(n)］,X(k)的共軛反對(duì)稱分量44②x(n)的共軛對(duì)稱分量和共軛反對(duì)稱分量的DFT分別為X(k)的實(shí)部和虛部乘以j

證明：如果x(n)=xep(n)+rop(n)，0≤n≤N-1

其中

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)］45DFT［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)其中XR(k)=Re［X(k)］=DFT［xep(n)］

jXI(k)=jIm［X(k)］=DFT［xop(n)］46

綜上所述，可總結(jié)出DFT的共軛對(duì)稱性質(zhì)：如果序列x(n)的DFT為X(k)，則x(n)的實(shí)部和虛部（包括j）的DFT分別為X(k)的共軛對(duì)稱分量和共軛反對(duì)稱分量；而x(n)的共軛對(duì)稱分量和共軛反對(duì)稱分量的DFT分別為X(k)的實(shí)部和虛部乘以j。

47

設(shè)x(n)是長(zhǎng)度為N的實(shí)序列，且X(k)=DFT[x(n)]，則

(1)X(k)=X*(N-k),0≤k≤N-1(2)如果x(n)=x(N-n)，則X(k)實(shí)偶對(duì)稱，即

X(k)=X(N-k)(3)如果x(n)=-x(N-n)，則X(k)純虛奇對(duì)稱，即

X(k)=-X(N-k)48

實(shí)際中經(jīng)常需要對(duì)實(shí)序列進(jìn)行DFT，利用上述對(duì)稱性質(zhì)，可減少DFT的運(yùn)算量，提高運(yùn)算效率。例如，計(jì)算實(shí)序列的N點(diǎn)DFT時(shí)，當(dāng)N=偶數(shù)時(shí)，只需計(jì)算X(k)的前面N/2+1點(diǎn)，而N=奇數(shù)時(shí)，只需計(jì)算X(k)的前面(N+1)/2點(diǎn)，其他點(diǎn)按照上在的公式即可求得。例如，X(N-1)=X*(1),X(N-2)=X*(2),…這樣可以減少近一半運(yùn)算量。49

【例】利用DFT的共軛對(duì)稱性，設(shè)計(jì)一種高效算法，通過(guò)計(jì)算一個(gè)N點(diǎn)DFT，就可以計(jì)算出兩個(gè)實(shí)序列x1(n)和x2(n)的N點(diǎn)DFT。

【解】構(gòu)造新序列x(n)=x1(n)+jx2(n)，對(duì)x(n)進(jìn)行DFT，得到：50由上式得到：所以，由X(k)可以求得兩個(gè)實(shí)序列x1(n)和x2(n)的N點(diǎn)DFT：51頻率域采樣

設(shè)任意序列x(n)的Z變換為且X(z)收斂域包含單位圓(即x(n)存在傅里葉變換)。在單位圓上對(duì)X(z)等間隔采樣N點(diǎn)得到xN(n)=IDFT［X(k)］，0≤n≤N-152

由DFT與DFS的關(guān)系可知，X(k)是xN(n)以N為周期的周期延拓序列(n)的離散傅里葉級(jí)數(shù)系數(shù)的主值序列，即53式中為整數(shù)其它m所以54

如果序列x(n)的長(zhǎng)度為M，則只有當(dāng)頻域采樣點(diǎn)數(shù)N≥M時(shí)，才有

xN(n)=IDFT［X(k)］=x(n)

即可由頻域采樣X(jué)(k)恢復(fù)原序列x(n)，否則產(chǎn)生時(shí)域混疊現(xiàn)象。這就是所謂的頻域采樣定理。55

推導(dǎo)用頻域采樣X(jué)(k)表示X(z)的內(nèi)插公式和內(nèi)插函數(shù)。設(shè)序列x(n)長(zhǎng)度為M，在頻域0~2π之間等間隔采樣N點(diǎn)，N≥M，則有式中

56

將上式代入X(z)的表示式中得57

上式中=1，因此

上式稱為用X(k)表示X(z)的內(nèi)插公式，φk(z)稱為內(nèi)插函數(shù)。當(dāng)z=ejω時(shí)，上式就成為x(n)的傅里葉變換X(ejω)的內(nèi)插函數(shù)和內(nèi)插公式，即58進(jìn)一步化簡(jiǎn)可得

59例長(zhǎng)度為26的三角形序列，編寫MATLAB程序驗(yàn)證頻域采樣定理60DFT的應(yīng)用舉例

DFT的快速算法FFT的出現(xiàn)，使DFT在數(shù)字通信、語(yǔ)言信號(hào)處理、圖像處理、功率譜估計(jì)、仿真、系統(tǒng)分析、雷達(dá)理論、光學(xué)、醫(yī)學(xué)、地震以及數(shù)值分析等各個(gè)領(lǐng)域都得到廣泛應(yīng)用。611用DFT計(jì)算線性卷積如果0≤k≤L-1則由時(shí)域循環(huán)卷積定理有

Y(k)=DFT[y(n)]=X1(k)X2(k),0≤k≤L-162

由此可見(jiàn)，循環(huán)卷積既可在時(shí)域直接計(jì)算，也可以按照下圖所示的計(jì)算框圖，在頻域計(jì)算。由于DFT有快速算法FFT，當(dāng)N很大時(shí)，在頻域計(jì)算的速度快得多，因而常用DFT(FFT)計(jì)算循環(huán)卷積。用DFT計(jì)算循環(huán)卷積63

在實(shí)際應(yīng)用中，為了分析時(shí)域離散線性非移變系統(tǒng)或者對(duì)序列進(jìn)行濾波處理等，需要計(jì)算兩個(gè)序列的線性卷積，與計(jì)算循環(huán)卷積一樣，為了提高運(yùn)算速度，也希望用DFT(FFT)計(jì)算線性卷積。而DFT只能直接用來(lái)計(jì)算循環(huán)卷積，為此導(dǎo)出線卷積和循環(huán)卷積之間的關(guān)系以及循環(huán)卷積與線性卷積相等的條件。

64

假設(shè)h(n)和x(n)都是有很長(zhǎng)序列，長(zhǎng)度分別是N和M。它們的線性卷積和循環(huán)卷積分別表示如下：其中，L≥max［N,M］65通過(guò)推導(dǎo)得：只有當(dāng)L≥N+M-1時(shí)，線性卷積和循環(huán)卷積相等。下圖是兩序列x(n)與h(n)的線性卷積與循環(huán)卷積的運(yùn)算結(jié)果比較圖

66線性卷積與循環(huán)卷積

67用DFT計(jì)算線性卷積框圖計(jì)算線性卷積68重疊相加法分段卷積對(duì)信號(hào)進(jìn)行譜分析69時(shí)域采樣DFT是x(n)的傅里葉變換X(ejw)在頻率區(qū)間[0，2π]上的N點(diǎn)等間隔采樣。對(duì)信號(hào)進(jìn)行譜分析柵欄效應(yīng)70上述分析方法不丟失信息，即可由X(k)恢復(fù)Xa(j?)或xa(t)，但直接由分析結(jié)果X(k)看不到Xa(j?)的全部頻譜特性，而只能看到N個(gè)離散采樣點(diǎn)的譜線，這就是所謂的柵欄效應(yīng)。對(duì)信號(hào)進(jìn)行譜分析截?cái)嘈?yīng)371低頻部分近似理想低通頻響特性，