3離散傅里葉變換

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

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

(1)DFT的定義；

(2)DFT的物理意義；

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

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

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

x(n)=R4(n),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18例如，

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

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

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

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

1線性性質(zhì)如果x1(n)和x2(n)是兩個有限長序列，長度分別為N1和N2,且y(n)=ax1(n)+bx2(n)式中a、b為常數(shù)，即N=max［N1,N2］，則y(n)的N點DFT為

Y(k)=DFT[y(n)]=aX1(k)+bX2(k),0≤k≤N-1其中X1(k)和X2(k)分別為x1(n)和x2(n)的N點DFT。

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

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

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

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

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

是長度為N的有限長序列，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)卷積定理

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

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

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

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

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

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

則30

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

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

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

【解】

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

設x*(n)是x(n)的復共軛序列，長度為NX(k)=DFT［x(n)］則

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

且

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

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

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

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

上式更清楚地說明了有限長序列共軛對稱性的含義。如下圖所示。圖中*表示對應點為序列取共軛后的值。40共軛對稱與共軛反對稱序列示意圖41

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

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

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

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的共軛對稱性①x(n)的實部和虛部（包括j）的DFT分別為X(k)的共軛對稱分量和共軛反對稱分量證明：如果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)的共軛對稱分量

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

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

其中

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)］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的共軛對稱性質(zhì)：如果序列x(n)的DFT為X(k)，則x(n)的實部和虛部（包括j）的DFT分別為X(k)的共軛對稱分量和共軛反對稱分量；而x(n)的共軛對稱分量和共軛反對稱分量的DFT分別為X(k)的實部和虛部乘以j。

47

設x(n)是長度為N的實序列，且X(k)=DFT[x(n)]，則

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

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

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

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

【例】利用DFT的共軛對稱性，設計一種高效算法，通過計算一個N點DFT，就可以計算出兩個實序列x1(n)和x2(n)的N點DFT。

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

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

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

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

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

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

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

56

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

上式中=1，因此

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

59例長度為26的三角形序列，編寫MATLAB程序驗證頻域采樣定理60DFT的應用舉例

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

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

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

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

64

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

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

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