第3章離散傅里葉變換3.1離散傅里葉變換的定義3.2離散傅里葉變換的性質3.3頻域采樣3.4快速傅里葉變換3.5

離散傅里葉變換的應用舉例2026/1/162第3章離散傅里葉變換本章目錄2026年1月16日3離散傅里葉變換3.1離散傅里葉變換的定義離散傅里葉變換(DiscreteFourierTransform，簡稱DFT)，解決序列傅里葉變換和z變換結果都是連續(xù)函數(shù)，無法用計算機進行處理的問題。序列經過DFT后，所得頻域函數(shù)也是離散化的，這就便于數(shù)字信號在頻域的處理運用計算機進行，大大增加了數(shù)字信號處理的靈活性3.1.1DFT定義設序列x(n)長度為M，定義x(n)的N(N≥M)點DFT為k=0，1，…，N-1(3-1)2026/1/164記WN=，WN有時也稱為旋轉因子。則式(3-1)可表示為定義X(k)的N點傅里葉逆變換x(n)=IDFT[X(k)]N=式(3-3)和(3-2)表明序列x(n)及其N點DFT結果X(k)都是長度為N的離散序列，由x(n)能唯一確定X(k)，反之亦然

k=0，1，…，N-1(3-2)n=0，1，…，N-1

(3-3)

離散傅里葉變換3.1離散傅里葉變換的定義2026/1/1653.1.2DFT與FT、ZT、DFS的關系1．DFT與FT、ZT的關系長度為M的有限長序列x(n)的N(N≥M)點的DFT、FT分別為比較以上兩式，得序列的N點的DFT是序列FT在頻率區(qū)間[0，2π]上采樣頻率間隔為2π/N的等間隔采樣。k=0，1，…，N-1k=0，1，…，N-1離散傅里葉變換3.1離散傅里葉變換的定義(3-4)

2026/1/166序列x(n)的Z變換與其DFT比較，得序列的N點的DFT是序列的z變換在單位圓上的采樣頻率間隔為2π/N的等間隔采樣。兩點結論的本質是一樣的，因為序列的傅里葉變換就是序列在單位圓上的z變換。2．DFT與DFS的關系對比DFS和DFT的定義，可以發(fā)現(xiàn)它們之間有密切的聯(lián)系。k=0，1，…，N-1離散傅里葉變換3.1離散傅里葉變換的定義(3-5)

2026/1/167比較上述兩式，容易看出X(k)正是的主值序列，或者說，是主值序列X(k)以N為周期進行延拓所得序列，即k=0，1，…，N-1-∞<k<∞(3-8）

(3-9)X(k)=RN(k)

離散傅里葉變換3.1離散傅里葉變換的定義2026/1/168式(3-6)和(3-7)表明x(n)以N為周期的延拓序列的DFS主值序列3．DFT的矩陣表示將式(3-2)所示DFT寫成矩陣形式X=DNx(3-10)X=[X(0)，X(1)，…，X(N-2)，X(N-1)]T(3-11)x=[x(0)，x(1)，…，x(N-2)，x(N-1)]T(3-12)DN稱為N點DFT矩陣，定義為

離散傅里葉變換3.1離散傅里葉變換的定義2026/1/169式(3-3)所示IDFT也可以表示成矩陣形式x=DN-1X(3-14)(3-13)

離散傅里葉變換3.1離散傅里葉變換的定義2026/1/1610DN-1稱為N點IDFT矩陣，定義為

(3-15)

離散傅里葉變換3.1離散傅里葉變換的定義2026/1/1611比較式(3-13)和(3-11)可得4．用MATLAB計算序列DFT用MATLAB計算DFT主要調用函數(shù)fft，其調用格式如下xk=fft(xn，N);例3-1分別計算X[R8(n)]在頻率區(qū)間[0，2π]上的32點和64點等間隔采樣，并繪制頻率特性圖(3-16)

離散傅里葉變換3.1離散傅里葉變換的定義2026/1/1612解：請參考92頁計算程序fex3_1.m。結果如下圖所示。

(a)32點DFT幅頻特性(b)32點DFT幅頻特性圖3-1R8(n)的32點和64點DFT頻率特性離散傅里葉變換3.1離散傅里葉變換的定義2026/1/1613離散傅里葉變換3.2離散傅里葉變換的性質1．DFT隱含的周期性長度為M的序列x(n)，其離散傅里葉正反變換由式(3-2)和(3-3)定義了X(k)和x(n)在變化區(qū)間(0≤n≤N-1)上的N個值。如果使-∞<k<∞，則X(k+mN)=X(k)(3-17)證明因為而2026/1/16142．線性性質(請讀者直接用DFT定義證明該性質)3．循環(huán)移位性質

(1)序列的循環(huán)移位離散傅里葉變換3.2離散傅里葉變換的性質圖3-2循環(huán)移位過程示意圖2026/1/1615(2)時域循環(huán)移位定理設x(n)是長度為N的有限序列，y(n)為x(n)的循環(huán)移位，即y(n)=x((n+m))NRN(n)，N≥MX(k)=DFT[x(n)]N，0≤k≤N-1則Y(k)=DFT[y(n)]N=證明

(3-21)

0≤k≤N-1

令l=n+m，代入上式得

離散傅里葉變換3.2離散傅里葉變換的性質2026/1/1616因為是以N為周期的所以Y(k)=DFT[y(n)]N=(3)頻域循環(huán)移位定理設X(k)=DFT[x(n)]，0≤k≤N-1，Y(k)=X((k+l))NRN(k)則y(n)=IDFT[Y(k)]=(3-22)

直接對Y(k)=X((k+l))NRN(k)進行F-1T即可證明式(3-22)。離散傅里葉變換3.2離散傅里葉變換的性質2026/1/16174．循環(huán)卷積定理(1)有限長序列的循環(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)則x(n)=IDFT[X(k)]=(3-23a)

或x(n)=IDFT[X(k)]=

離散傅里葉變換3.2離散傅里葉變換的性質(3-23b)

2026/1/1618證明：直接對(3-21)式兩邊進行DFTX(k)=DFT[x(n)]

令n-m=n’，則有離散傅里葉變換3.2離散傅里葉變換的性質2026/1/1619式中以N為周期，所以對其在任一周期上的求和結果不變。因此=X1(k)X2(k)，0≤k≤N-1

(3-22)

命題得證。式(3-21)稱為循環(huán)卷積定理

(2)頻域循環(huán)卷積定理如果x(n)=x1(n)x2(n)則

X(k)=DFT[x(n)]=

(3-25a)

離散傅里葉變換3.2離散傅里葉變換的性質2026/1/16205．復共軛序列的DFT設x*(n)是x(n)的復共軛序列，長度為N，且X(k)=DFT[x(n)]則DFT[x*(n)]=X*(N-k)，0≤k≤N-1

(3-26)其中X(N)=X(0)。 證明：由X(k)的隱含周期性有X(N)=X(0)用同樣的方法可以證明

DFT[x*(N-n)]N=X*(k)，0≤k≤N-1

(3-27)離散傅里葉變換3.2離散傅里葉變換的性質2026/1/16216．DFT的共軛對稱性(1)有限長共軛對稱序列和共軛反對稱序列 若有限長序列xep(n)滿足xep(n)=x*ep(N-n)，0≤n≤N-1(3-28)則稱xep(n)為共軛對稱序列。如果有限長序列xop(n)滿足xop(n)=

-x*op(N-n)，0≤n≤N-1(3-29)則稱xep(n)為共軛反對稱序列。二者均指序列對n=N/2點共軛對稱或共軛反對稱。如圖3-4所示。離散傅里葉變換3.2離散傅里葉變換的性質2026/1/1622任何實函數(shù)都可以分解成偶對稱和奇對稱分量的性質類似，任何有限長序列x(n)都可以表示成其共軛對稱分量和共軛反對稱分量之和，即x(n)=xep(n)+xop(n)，0≤n≤N-1(3-30)將上式中的n換成N-n，并取復共軛，再將式(3-26)和(3-27)代入得到

圖3-4共軛對稱與共軛反對稱序列示意圖

離散傅里葉變換3.2離散傅里葉變換的性質2026/1/1623x*(N-n)=x*ep(N-n)+x*op(N-n)=xep(n)-xop(n)

(3-31)式(3-30)加減(3-31)式可得xep(n)=[x(n)+x*(N-n)]

(3-32)

xop(n)=[x(n)-x*(N-n)]

(3-33)

(2)DFT的共軛對稱性質①若將序列x(n)表示為實部與虛部之和，即x(n)=xr(n)+jxi(n)(3-34)將x(n)的DFT表示為共軛對稱和共軛反對稱量部分之和，即X(k)=Xep(k)+Xop(k)則Xep(k)=DFT[xr(n)]N(3-35)

Xop(k)=DFT[jxi(n)]N(3-36）

離散傅里葉變換3.2離散傅里葉變換的性質2026/1/1624 ②如果將序列x(n)表示為實部與虛部之和，即x(n)=xep(n)+xop(n)x(n)的DFT表示為實部與虛部和，即X(k)=Xr(k)+jXi(k)則Xr(k)=DFT[xep(n)]N(3-42)jXi(k)=DFT[xop(n)]N(3-43)6．離散帕斯瓦爾定理設x(n)是長度為N的實序列，且X(k)=DFT[x(n)]N，則

(3-47)

離散傅里葉變換3.2離散傅里葉變換的性質2026/1/1625離散傅里葉變換3.3頻域采樣1．頻域采樣 設任意序列x(n)存在z變換且X(z)的收斂域包含單位圓（即x(n)存在傅里葉變換）。在單位圓上以2π/N為間隔對X(z)進行等間隔采樣得到必然是一個周期序列的DFS系數(shù)。2．頻域采樣定理根據式(2-11)可得

(3-48)

2026/1/1626=IDFS[]將式(3-46)代入上式，得所以

=IDFS[]=(3-49)

XN(k)=RN(k)=

0≤k≤N-1

(3-51)離散傅里葉變換3.3頻域采樣2026/1/1627式(3-51)表明XN(k)是對X(z)在單位圓上的N點等間隔采樣，也是對X(ejω)在頻率區(qū)間[0，2π]上的N點等間隔采樣，所得采樣序列的IDFT為原序列x(n)以N為周期的周期延拓序列的主值序列。綜上所述，如果序列x(n)的長度為M，對X(ejω)在頻率區(qū)間[0，2π]上的N點等間隔采樣得到的采樣序列XN(k)，則只有當頻域采樣點數(shù)N≥M時，才能由頻域采樣序列XN(k)恢復時域序列x(n)=IDFT[X(k)]即可由頻域采樣X(k)恢復原序列，否則產生時域混疊現(xiàn)象。這就是所謂的頻域采樣定理。離散傅里葉變換3.3頻域采樣2026/1/16283.頻域內插公式設序列x(n)的長度為M，在頻域0到2π之間等間隔采樣N點，N≥M，則有0≤k≤N-1

x(n)=IDFT[X(k)]=

將上式代入X(z)的表達式中得離散傅里葉變換3.3頻域采樣2026/1/1629式中，因此令

則

式(3-56)稱為用X(k)表示X(z)的內插公式，φk(z)稱為內插函數(shù)。離散傅里葉變換3.3頻域采樣(3-54)(3-55)(3-56)2026/1/1630離散傅里葉變換3.4快速傅里葉變換

信號處理中兩個最基本、最常用的運算：離散傅里葉變換和卷積運算目前已研究出許許多多不同F(xiàn)FT算法3.4.1直接計算DFT的問題及改進的途徑1．DFT的運算量設x(n)為N點有限長序列，其DFT為考察式(3-59)可知每計算一個X(k)值，需要N次復數(shù)乘法，以及(N-1)次復數(shù)加法。k=0，1，2，3，4……N-1

(3-59)

2026/1/1631而復數(shù)運算實際上是由實數(shù)運算來完成的，式(3-54)可寫成(3-60）

由式(3-60)可整個DFT運算共需要4N2次實數(shù)乘法和N×2(2N-1)=2N(2N-1)次實數(shù)加法。

離散傅里葉變換3.4快速傅里葉變換

2026/1/16322．減少運算工作量的途徑仔細觀察DFT的運算可看出減少DFT運算量的途徑之一：將N點DFT分解為幾個較短的DFT運算。例如，將點DFT分解為M個N/M點DFT，則復數(shù)乘法運算量為(N/M)2M=N2/M，減少到原來的1/M。減少DFT運算量的途徑之二：利用系數(shù)的兩個固有特性，即的對稱性和周期性來有效地減少DFT的運算量。離散傅里葉變換3.4快速傅里葉變換

2026/1/1633(1)的對稱性

使DFT運算中有些項可以合并

(2)的周期性

將長序列的DFT分解為短序列的DFT。

由此可得出快速傅里葉變換算法基本上可以分成兩大類，即按時間抽取(DIT，DecimationInTime)快速算法按頻率抽取(DIF，DecimationInFrequency

)快速算法離散傅里葉變換3.4快速傅里葉變換

2026/1/16343.4.2DIT基2FFT算法1．DIT基2FFT算法原理設序列x(n)的長度為N=2L，L為整數(shù)。若不滿足這個條件，可補加上若干零值點來滿足這一要求。這種N為2的整數(shù)冪的FFT，也稱基-2FFT。將N=2L的序列x(n)(n=0，1，2，3，4……N-1)先按n的奇偶分成兩組r=0，1，2，3，4,…,-1-1

(3-61)

離散傅里葉變換3.4快速傅里葉變換

2026/1/1635得由于，上式可表示成式中X1(k)及X2(k)分別是x1(r)及x2(r)的N/2點DFT

離散傅里葉變換3.4快速傅里葉變換

(3-62)

2026/1/1636用X1(k)，X2(k)來表達全部X(k)值，還必須應用系數(shù)的周期性，可得同理可得再考慮到的周期性式(3-65)、(3-66)、(3-67)代入到式(3-62)，可將X(k)表達為前后兩部分前半部分(3-66)

(3-65)

(3-67)

k=0，1，2，3，4，-1(3-68)

離散傅里葉變換3.4快速傅里葉變換

2026/1/1637后半部分式(3-68)和(3-69)表明，只要求出0~(N/2-1)區(qū)間的所有X1(k)和X2(k)值，即可求出0~(N-1)區(qū)間內的所有X(k)值，這就大大節(jié)省了運算。式(3-68)和(3-69)的運算可以用圖3-5的蝶形信號流圖符號表示。k=0，1，2，3，4，-1(3-69)

圖3-5時間抽取法蝶形運算流圖符號

離散傅里葉變換3.4快速傅里葉變換

2026/1/1638采用上述表示法，可將上面討論分解過程表示于圖3-6中，此圖表示N=23=8的情況，輸出值X(0)~X(3)由式(3-68)給出輸出值X(4)~X(7)由式(3-69)給出圖3-6按時間抽取，將一個N點DFT分解為兩個N/2點DTF

離散傅里葉變換3.4快速傅里葉變換

2026/1/1639由于N=2L，因而仍是偶數(shù)，進一步把每個點子序列再按其奇偶部分分解為兩個點的子序列。l=0，1，2，3，4，-1(3-70)

仿照前面的方法和步驟可得

k=0，1，2，3，4，-1且

k=0，1，2，3，4，-1X2(k)也可進行同樣的分解

k=0，1，2，3，4，-1離散傅里葉變換3.4快速傅里葉變換

2026/1/1640圖3-8按時間抽取，將一個N點DFT分解為四個N/4點DFT(N=8)離散傅里葉變換3.4快速傅里葉變換

2026/1/1641上述方法和步驟一直進行下去，最后剩下的是2點DFT，這些兩點DFT都可用一個蝶形結表示。這種方法的每一步分解都是按輸入序列在時間上的次序是屬于偶數(shù)還是屬于奇數(shù)來分解為兩個更短的子序列，稱為“按時間抽取法”(DIT)。8點DFT分解圖如圖3-7所示。2．運算量復乘數(shù)復加數(shù)(3-75)

(3-76)

離散傅里葉變換3.4快速傅里葉變換

2026/1/1642直接計算DFT與FFT算法的計算量之比為(3-77)

圖3-10直接計算DFT與FFT算法所需乘法次數(shù)的比較離散傅里葉變換3.4快速傅里葉變換

2026/1/16433.4.3DIF基2FFT算法按頻率抽取(DIF)的FFT算法(桑德-圖基算法)原理與DIT快速算法類似，也是通過不斷的分組操作，將長序列分解為短序列在計算DFT來實現(xiàn)快速計算。不同之處是把待變換x(n)按照前半部分和后半部分進行分組，從而達到快速計算目的。結果序列X(k)(也是N點序列)是按其正順序的輸出序列。離散傅里葉變換3.4快速傅里葉變換

2026/1/16443.4.4離散傅里葉反變換的快速計算方法將IDFT公式(3-80)取共軛(3-82)

式(3-77)說明，只要先將X(k)取共軛，就可以直接利用FFT子程序，最后再將運算結果取一次共軛，并乘以1/N，即得到x(n)值。FFT和IFFT運算就可很方便地共用一個子程序，大大方便了程序設計。

離散傅里葉變換3.4快速傅里葉變換

2026/1/1645離散傅里葉變換3.5離散傅里葉變換的應用舉例

3.5.1用DFT計算線性卷積若序列y(n)是序列x1(n)和x2(n)的循環(huán)卷積，則則根據時域循環(huán)卷積定理有Y(k)=DFT[y(n)]=X1(k)X2(k)，0≤k≤L-1

循環(huán)卷積既可在時域直接計算，也可以按照圖3-13所示的框圖在頻域計算。圖3-13用DFT計算循環(huán)卷積

2026/1/1646對于線性時不變系統(tǒng)來說設h(n)和x(n)都是有限長序列，長度分別是N和M。

h(n)和x(n)的線性卷積和循環(huán)卷積分別表示為其中，L≥max[N，M]，，所以(3-83)

(3-84)

離散傅里葉變換3.5離散傅里葉變換的應用舉例

2026/1/1647對照式(3-78)可以看出，上式中即

(3-85)

式(3-85)表明yc(n)等于yl(n)以L為周期的周期延拓序列的主值序列。yl(n)長度為N+M-1，因此只有當循環(huán)卷積長度L≥N+M-1時，yl(n)以L為周期進行周期延拓才無混疊現(xiàn)象。因此，循環(huán)卷積與線性卷積相等的條件是L≥N+M-1。離散傅里葉變換3.5離散傅里葉變換的應用舉例

2026/1/1648圖3-16重疊相加法卷積示意圖離散傅里葉變換3.5離散傅里葉變換的應用舉例

2026/1/16493.5.2用DFT對信號進行譜分析信號的譜分析就是計算信號的傅里葉變換，可以用DFT對時域離散信號和連續(xù)信號進行譜分析。對于連續(xù)信號和系統(tǒng)，可以通過時域采樣，應用DFT進行譜分析。1．用DFT對連續(xù)信號進行譜分析在對連續(xù)信號進行譜分析時，主要關心兩個性能指標：譜分析范圍和頻譜分辨率。在已知信號的最高頻率fc（譜分析范圍）時，為了避免在DFT運算中發(fā)生頻譜混疊現(xiàn)象，要求采樣頻率fs滿足但是考慮到時域信號截斷可能會引起頻譜展寬，工程上可以適當增大信號的采樣頻率，可選擇3～5倍的fc作為采樣頻率。頻譜分辨率F=fs/N離散傅里葉變換3.5離散傅里葉變換的應用舉例

(3-93)

2026/1/1650離散傅里葉變換3.5離散傅里葉變換的應用舉例

圖3-17用DFT分析連續(xù)信號頻譜的示意圖2026/1/1651如果維持fs不變，為提高頻譜分辨率，可以增大采樣點數(shù)N，因為NT=Tp，T=fs?1，只有延長對信號的觀察時間才能增大N，Tp和N可以按照如下公式進行選擇。離散傅里葉變換3.5離散傅里葉變換的應用舉例

(3-94)

(3-95)

2026/1/1652例3-3用DFT分析連續(xù)非周期信號的頻譜，信號的最高頻率為1.25kHz，序列長度N必須為2的整數(shù)次冪，要求頻譜分辨率F≤5Hz，試確定：（1）最短的信號記錄時間Tp；（2）最大的采樣間隔T；