第4章離散傅里葉變換培訓(xùn)教材

離散傅里葉變換(DiscreteFourierTransform，簡稱DFT)是數(shù)字信號處理中非常重要的一種數(shù)學變換，本章主要討論DFT的定義、物理意義及基本性質(zhì)、頻率采樣和DFT應(yīng)用舉例。主要內(nèi)容包括：?周期序列的離散傅里葉級數(shù)定義及其性質(zhì)?有限長度序列的離散傅里葉變換推導(dǎo)?離散傅里葉變換的基本性質(zhì)?頻率域采樣理論?離散傅里葉變換的基本應(yīng)用

第3章離散傅里葉變換2025/1/2423.1離散傅里葉變換的定義3.2離散傅里葉變換的性質(zhì)3.3頻率域采樣3.4DFT的應(yīng)用舉例2025/1/2433.1離散傅里葉變換定義

3.1.1傅里葉變換的幾種可能形式 傅里葉變換就是建立以時間為自變量的“信號”與以頻率為自變量的“頻譜函數(shù)”之間的某種變換關(guān)系。所以，當自變量“時間”或“頻率”取連續(xù)或離散值時，就形成各種不同形式的傅里葉變換對。1、連續(xù)時間、連續(xù)頻率——傅里葉變換就是連續(xù)時間非周期信號x(t)的傅里葉變換關(guān)系,所得到的是連續(xù)的非周期的頻譜函數(shù)。2025/1/245圖3-1連續(xù)的非周期信號及其非周期、連續(xù)的頻譜密度2025/1/2462、連續(xù)時間、離散頻率——傅里葉級數(shù)

設(shè)x(t)代表一個周期為T0的周期性連續(xù)時間函數(shù)，可展成傅里葉級數(shù)，其傅里葉級數(shù)的系數(shù)為X(jkΩ0)，是離散頻率的非周期函數(shù)，和X(jkΩ0)組成變換對，表示為其中Ω0=2πF=2π/T0為離散頻譜相鄰兩譜線之間的角頻率間隔，k為諧波序號。

3-33-42025/1/247圖3-2連續(xù)的周期信號及其非周期離散譜線

這一變換對的示意圖如圖3-2所示?？梢钥闯觯瑫r域連續(xù)函數(shù)造成頻域是非周期的頻譜函數(shù)，而頻域的離散頻譜就與時域的周期時間函數(shù)相對應(yīng)。2025/1/2483、離散時間、連續(xù)頻率——序列的傅里葉變換

這正是第二章中討論過的序列（離散時間信號）的傅里葉變換，即3-53-6上面討論的三種傅里葉變換對都不適合在計算機上運算，因為它們至少在一個域(時域或頻域)中函數(shù)是連續(xù)的。因而從數(shù)字計算角度出發(fā)，我們感興趣的是時域及頻域都是離散的情況，這就是我們這里要研究的離散傅里葉變換。

2025/1/249離散傅立葉變換—有限長序列的離散頻域表示

離散傅里葉變換的定義設(shè)x(n)是一個長度為N的有限長序列，則定義x(n)的N點離散傅里葉變換為3-313-32(3-31)和(3-32)分別是有限長序列的離散傅里葉正變換和反變換。x(n)與X(k)是一個有限長序列的離散傅里葉變換對。已知其中的一個序列，就能唯一確定另一序列。離散傅里葉變換記作DFT，IDFT為逆變換。2025/1/24103.2離散傅里葉變換的性質(zhì)3.2.1線性性質(zhì)如果和是兩個有限長序列，長度分別為N1和N2。若式中a，b為任意常數(shù)，取N=max[N1,N2]，則的N點DFT為3-35其中X1(k)和X2(k)分別為x1(n)和x2(n)的N點DFT。2025/1/24113.2.2循環(huán)移位性質(zhì)

1、序列的循環(huán)移位設(shè)為x(n)有限長序列，長度為N，則的循環(huán)移位定義為3-36式(3-36)表明，將x(n)以N為周期進行周期延拓得到再將左移m位得到，最后取的主值序列，則得到有限長序列的循環(huán)移位序列y(n)。x(n)及其循環(huán)移位過程如圖3-7所示。顯然y(n)仍是長度為N有限長序列。觀察圖3-7可見，循環(huán)移位的實質(zhì)是將x(n)左移m位，而左側(cè)移出主值區(qū)的序列值又依次從右側(cè)進入主值區(qū)。2025/1/2412圖3-7循環(huán)移位過程示意圖

2025/1/24132、時域循環(huán)移位定理設(shè)x(n)是長度為N的有限序列，y(n)為x(n)的循環(huán)移位，即則3-37其中證明：2025/1/2414令n+m=n’，則有由于上式中求和項以N為周期，所以對其在任一周期上的求和結(jié)果相同。將上式的求和區(qū)間改在主值區(qū)則得2025/1/24153、頻域循環(huán)移位定理如果X(k)=DFT[x(n)]，0≤k≤N-1Y(k)=X((k+l))NRN(k)則3-38式(3-38)的證明方法與時域循環(huán)定理類似，直接對Y(k)=X((k+l))NRN(k)進行IDFT即得證。2025/1/24163.2.3循環(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)則3-39或一般稱(3-39)式所表示的運算為和的循環(huán)卷積。2025/1/2417證明：直接對(3-39)式兩邊進行DFT令n-m=n’，則有2025/1/2418因為上式中以N為周期，所以對其在任一周期上的求和結(jié)果不變。因此式(3-39)的循環(huán)卷積過程如圖3-8所示。2025/1/2419圖3-8循環(huán)卷積過程示意圖2025/1/2420由于循環(huán)卷積過程中，要求對x2(m)的循環(huán)反轉(zhuǎn)，循環(huán)移位，特別是兩個N長的序列的循環(huán)卷積長度仍為N。顯然與一般的線性卷積不同，故稱之為循環(huán)卷積，記為由于所以即循環(huán)卷積亦滿足交換率。2025/1/2421作為習題請讀者證明頻域卷積定理如果x(n)=x1(n)·x2(n)則3-40或2025/1/24223.2.4復(fù)共軛序列的DFT設(shè)x*(n)是x(n)的復(fù)共軛序列，長度為NX(k)=DFT[x(n)]則

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

X(N)=X(0)證明：根據(jù)DFT的唯一性，只要證明(3-41)式右邊等于左邊即可。3-412025/1/2423證又由X(k)的隱含周期性有X(N)=X(0)用同樣的方法可以證明

DFT[x*(N-n)]=X*(k)3-422025/1/24243.2.5DFT的共軛對稱性

(1)如果x(n)=xr(n)+jxi(n)由DFT的線性性質(zhì)即可得3-493-50其中X(k)的共軛對稱分量X(k)的共軛反對稱分量(2)如果x(n)=xep(n)+xop(n)3-513-52其中2025/1/2425綜上所述：如果序列x(n)的DFT為X(k)，則x(n)的實部和虛部（包括j）的DFT分別為X(k)的共軛對稱分量和共軛反對稱分量；而x(n)的共軛對稱分量和共軛反對稱分量的DFT分別為X(k)的實部和虛部乘以j。設(shè)x(n)是長度為N的實序列，且X(k)=DFT[x(n)]，則(1)X(k)共軛對稱，即

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)3-533-543-552025/1/24263.3頻率域采樣設(shè)任意序列x(n)存在Z變換且X(z)的收斂域包含單位圓(即x(n)存在傅里葉變換)。在單位圓上對X(z)等間隔采樣N點得到3-56顯然，式(3-56)表示在區(qū)間[0，2π]上對x(n)的傅里葉變換X(ejω)的N點等間隔采樣。如果將X(k)看成長度為N的有限長序列xN(n)的DFT，即

xN(n)=IDFT[X(k)]，0≤k≤N-12025/1/2427下面推導(dǎo)序列xN(n)與原序列x(n)之間的關(guān)系，并導(dǎo)出頻域采樣定理。

由DFT和DFS的關(guān)系可知，X(k)是xN(n)以N為周期的周期延拓序列的離散傅立葉系數(shù)的主值序列，即將式(3-56)代入上式得2025/1/2428式中

所以3-573-58式(3-58)說明X(z)在單位圓上的N點等間隔采樣X(k)的IDFT為原序列x(n)以N為周期的周期延拓序列的主值序列。2025/1/2429頻域采樣定理

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

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

即可由頻域采樣X(k)恢復(fù)原序列，否則產(chǎn)生時域混疊現(xiàn)象。這就是所謂的頻域采樣定理。下面推導(dǎo)用頻域采樣X(k)表示X(z)的內(nèi)插公式和內(nèi)插函數(shù)。設(shè)序列x(n)的長度為M，在頻域0到之間等間隔采樣N點，N≥M，則有2025/1/2430式中

將上式代入X(z)的表達式中得上式中，因此3-592025/1/2431令

則3-603-61式(3-61)稱為用X(k)表示X(z)的內(nèi)插公式，φk(z)稱為內(nèi)插函數(shù)。當z=ejω時，(3-60)式和(3-61)式就成為x(n)的傅里葉變換變換X(ejω)的內(nèi)插函數(shù)和內(nèi)插公式，即2025/1/2432進一步化簡可得

在數(shù)字濾波器的結(jié)構(gòu)與設(shè)計中，我們將會看到，頻域采樣理論及有關(guān)公式可提供一種有用的濾波器結(jié)構(gòu)和濾波器設(shè)計途徑。3-623-632025/1/24333.4DFT的應(yīng)用舉例DFT的快速算法FFT的出現(xiàn)，使DFT在數(shù)字通信、語音信號處理、圖象處理、功率譜估計、仿真、系統(tǒng)分析、雷達理論、光學、醫(yī)學、地震以及數(shù)值分析等各個領(lǐng)域都得到廣泛應(yīng)用。然而，各種應(yīng)用一般都以卷積和相關(guān)運算的具體處理為依據(jù)，或者以DFT作為連續(xù)傅里葉變換的近似為基礎(chǔ)。本節(jié)主要介紹用DFT計算卷積和相關(guān)系數(shù)的基礎(chǔ)原理以及用DFT對連續(xù)信號和序列進行譜分析等最基本的應(yīng)用。只要掌握了這兩種基本應(yīng)用的原理，就為用DFT解決數(shù)字濾波和系統(tǒng)分析等問題打下了基礎(chǔ)。2025/1/24343.4.1用DFT計算線性卷積如果且

則由時域循環(huán)卷積定理有0≤k≤L-1由此可見，循環(huán)卷積既可在時域直接計算，也可以按照圖3-10所示的計算框圖，在頻域計算。由于DFT有快速算法FFT，當N很大時，在頻域計算的速度快得多，因而常用DFT(FFT)計算循環(huán)卷積。2025/1/2435圖3-10用DFT計算循環(huán)卷積

在實際應(yīng)用中，為了分析時域離散線性非時變系統(tǒng)或者對序列進行濾波處理等，需要計算兩個序列的線性卷積。和計算循環(huán)卷積一樣，為了提高運算速度，也希望用DFT(FFT)計算線性卷積。而DFT只能用來計算循環(huán)卷積，為此導(dǎo)出線性卷積和循環(huán)卷積之間的關(guān)系以及循環(huán)卷積和線性卷積相等的條件。2025/1/2436假設(shè)h(n)和x(n)都是有限長序列，長度分別是N和M。它們的線性卷積和循環(huán)卷積分別表示如下：其中，L≥max[N，M]，，所以3-643-652025/1/2437對照式(3-64)可以看出，上式中

即3-66式(3-66)說明，yc(n)等于yl(n)以L為周期的周期延拓序列的主值序列。我們知道，yl(n)長度為N+M-1，因此只有當循環(huán)卷積長度L≥N+M-1時，yl(n)以L為周期進行周期延拓才混疊現(xiàn)象。此時取主值序列顯然滿足yc(n)=yl(n)。由此證明循環(huán)卷積等于線性卷積的條件是L≥N+M-1。圖3-11中畫出了h(n)、x(n)、h(n)*x(n)和L分別取6、8、10時h(n)×x(n)的波形。由于h(n)長度N=4，x(n)長度M=4，N+M-1=8，所以只有L≥8時，h(n)×x(n)的波形才與h(n)*x(n)相同。2025/1/2438圖3-11線性卷積與循環(huán)卷積

2025/1/2439如果取L=N+M-1，則可用DFT(FFT)計算線性卷積，計算框圖如圖3-12所示。其中DFT和IDFT通常用快速算法(FFT)來實現(xiàn)，故常稱其為快速卷積。

圖3-12用DFT計算線性卷積框圖

2025/1/2440實際上，經(jīng)常遇到兩個序列的長度相差很大的情況，例如M>>N時，直接套用上述方法是不行的。解決這個問題的方法是將長序列分段處理計算。這種分段處理法有重疊相加法和重疊保留法兩種。下面只介紹重疊相加法。設(shè)序列h(n)長度為，x(n)為無限長序列。將均勻分段，每段長度取，則式中xk(n)=x(n)·RM(n-kM)2025/1/2441于是，h(n)與x(n)的線性卷積可表示為式中

3-67式(3-67)說明，計算h(n)與x(n)的線性卷積時，可先進行分段線性卷積yk(n)=h(n)*xk(n)，然后再把分段卷積結(jié)果疊加起來即可。如圖3-13所示。每一分段卷積yk(n)的長度為N+M-1，因此yk(n)與yk+1(n)有N-1個點重疊，必須把重疊部分的yk(n)與yk+1(n)相加，才能得到完整的卷積序列y(n)。2025/1/24西安建筑科技大學信于與控制學42圖3-13重疊相加法卷積示意圖

2025/1/24433.4.2用DFT對信號進行譜分析所謂信號的譜分析就是計算信號的傅里葉變換。連續(xù)信號與系統(tǒng)的傅里葉分析顯然不便于直接用計算機進行計算，使其應(yīng)用受到限制，而DFT是一種時域和頻域均離散化的變換，適合數(shù)值運算，成分分析離散信號和系統(tǒng)的有力工具。1.用DFT對連續(xù)信號進行譜分析工程實際中，經(jīng)常遇到的連續(xù)信號xa(t)，其頻譜函數(shù)Xa(jΩ)也是連續(xù)函數(shù)。2025/1/2444設(shè)連續(xù)信號xa(t)持續(xù)時間和Tp，最高頻率為fc，如圖3-14所示。xa(t)的傅里葉變換為以間隔T≤1/2fc(即fs=1/T≥2fc)采樣xa(t)得=xa(nT)。設(shè)共采樣N點，并對Xa(jf)作零階近似(t=nT，dt=T)得顯然，Xa(jf)仍是f的連續(xù)周期函數(shù)，和如圖3-14(b)所示。對在區(qū)間等間隔采樣N點，采樣間隔為F，如圖3-14(c)所示。2025/1/2445參數(shù)fc、Tp、N和F滿足如下關(guān)系式：

由于NT=Tp，所以3-683-69將f=kF和(3-68)式代入中可得Xa(jf)的采樣令Xa(k)=，x(n)=xa(nT)，則3-702025/1/2446用同樣方法，由

可以推出3-71(3-70)式說明，連續(xù)信號的頻譜特性可以通過對連續(xù)信號采樣并進行DFT再乘以T的近似方法得到。時域采樣信號可由(3-71)式得出。對持續(xù)時間有限的帶限信號，在滿足時域采樣定理時，上述分析方法不丟失信息。2025/1/2447但直接由分析結(jié)果Xa(k)看不到Xa(jf)的全部頻譜特性，而只能看到N個離散采樣點的譜特性，這就是所謂的柵欄效應(yīng)。如果的持續(xù)時間無限長，上述分析中要進行截斷處理，所以會產(chǎn)生頻率混疊和泄露現(xiàn)象，從而使譜分析產(chǎn)生誤差。下面將討論上述問題產(chǎn)生的原因及改進措施。2025/1/2448圖3-14用DFT計算連續(xù)信號頻譜原理2025/1/2449理想低能濾波器的單位沖擊響應(yīng)ha(t)及其頻響函數(shù)Ha(if)如圖3-15(a)、(b)所示。圖中現(xiàn)在用DFT來分析ha(t)的頻率響應(yīng)特性。由于ha(t)的持續(xù)時間為無窮長，故要截取一段Tp，假設(shè)Tp=8s，采樣間隔T=0.25s(即采樣頻率fs=4Hz)，采樣點數(shù)N=Tp/T=32。此時頻域采樣間隔F=1/NT=0.125Hz。則

H(k)=T·DFT[h(n)],0≤k≤31其中h(n)=ha(nT)R32(n)3-712025/1/2450圖3-15用DFT計算理想低通濾波器頻響曲線2025/1/2451H(k)的曲線如圖3-15(c)所示。由圖可見，低頻部分近似理想低通頻響特性，而高頻誤差較大，且整個頻響都有波動。這些差別就是由于對ha(t)截斷所產(chǎn)生的。為減少這種截斷誤差，可適當加長Tp，增加采樣點數(shù)N或用窗函數(shù)處理后在進行DFT。有關(guān)窗函數(shù)的內(nèi)容將在FIR數(shù)字濾波器設(shè)計中詳細敘述。2025/1/2452連續(xù)信號進行譜分析對信號進行譜分析主要關(guān)心兩個問題，就是譜分析范圍和頻率分辨率。譜分析范圍受采樣速率fs的限制。為了不產(chǎn)生頻率混疊失真，通常要求信號的最高頻率fs<fs/2。頻率分辨率用采樣間隔F來描述，表示譜分析中能夠分辨的兩個頻譜分量的最小間隔。顯然F越小譜分析就越接近Ha(jf)，所以F較小時，我們稱頻率分辨率較高。下面討論用DFT對連續(xù)信號譜分析的參數(shù)選擇原則。2025/1/2453信號譜分析的參數(shù)選擇原則

在已知信號最高頻率fc（即譜分析范圍）時，為了避免在DFT運算中發(fā)生頻率混疊現(xiàn)象，要求采樣速率fs滿足下式：

fs>2fc

按照式(3-69)，譜分辨率F=fs/N，如果保持采樣點數(shù)N不變，要提高譜的分辨率，必須降低采樣速率，采樣速率的降低會引起譜分析范圍減少；如維持fs不變，為提高譜的分辨率可以增加采樣點數(shù)N，因為NT=Tp，T=1/fs-1，只有增加對信號的觀察時間，才能增加N，Tp和N可按照下式選擇：3-723-733-742025/1/2454例3-1對實信號進行譜分析，要求譜分辨率F≤10Hz，信號最高頻率fc=2.5kHz，試確定最小記錄時間TPmin，最大的采樣間隔Tmax，最少的采樣點數(shù)Nmin。如果fc不變，要求譜分辨率增加一倍，最少的采樣點數(shù)和最小的記錄時間是多少?解：因此TPmin=0.1s，因為要求fs≥2fc，所以2025/1/24552.用DFT對序列進行譜分析已知道單位圓上的Z變換就是序列傅里葉變換，即為使頻率分辨率提高一倍，F(xiàn)=5Hz，要求X(ejω)是ω的連續(xù)周期函數(shù)。如果對序列x(n)進行N點DFT，得到X(k)，X(k)是在區(qū)間[0，2π]上對X(ejω)的N點等間隔采樣。因此序列的傅里葉變換可利用DFT(FFT)來計算。2025/1/2456對周期為N的周期序列，其頻譜函數(shù)為其中

由DFT的隱含周期性知道，截取的主值序列x(n)=RN(n)，并進行N點DFT得到所以可用X(k)表示的頻譜結(jié)構(gòu)。2025/1/2457如果截取長度M等于的整數(shù)個周期，即M=mN，m為正整數(shù)，則令n=n’+rN，r=0，1，...，m-1，n’=0，1，...，N-1，則2025/1/2458由此可見，XM(k)也能表示的頻譜結(jié)構(gòu)，只是在k=rm時，XM(rm)=，表示的r次諧波譜線，其幅度擴大m倍，而其它k值時，XM(k)=0。當然，X(r)與XM(rm)對應(yīng)點頻率是相等的。所以，只要截取的整數(shù)個周期進行DFT，就可得到它的頻譜結(jié)構(gòu)，達到譜分析的目的。因為所以2025/1/2459如果的周期預(yù)先不知道，可先截取M點進行DFT，即

再將截取長度擴大一倍，截取比較XM(k)和X2M(k)，如果二者的主譜差別滿足分析誤差要求，則已以XM(k)或X2M(k)近似表示的頻譜，否則，繼續(xù)將截取長度加倍，直至前后兩次分析所得主譜頻率差別滿足誤差要求。設(shè)最后截取長度為rM，則XrM(k0)表示點的譜線強度。2025/1/2460實際應(yīng)用中，并非整個單位圓上的頻譜都很有意義。

例如，對于窄帶信號，往往只希望對信號所在的一段頻段進行譜分析，這時便希望采樣能密集地在著段頻帶內(nèi)進行，而帶外部分可完全不管。有時希望采樣點不局限于單位圓上。例如，語音信號處理中，常常需要知道系統(tǒng)極點所對應(yīng)的頻率，如果極點位置偏離單位圓較遠，則其單位圓上的頻譜就很平滑，如圖3-16(a)所示，這時很難從中識別出極點對應(yīng)的頻率。如果使采樣點軌跡接近這些極點的弧線或圓周進行，則采樣結(jié)果將會在極點對應(yīng)的頻率上出現(xiàn)明顯的尖峰，如圖3-16(b)所示，這樣就能準確地測定出極點頻率。2025/1/2461圖3-16單位圓與非單位圓采樣2025/1/2462對均勻分布在以原點為圓心的任何圓上的N點頻譜采樣，可用DFT（FFT）計算，而沿螺旋弧線采樣，則要用線性調(diào)頻Z變換（Chirp-Z變換，簡稱CZT）計算。例如，要求計算序列在半徑為r的圓上的頻譜，那么N個等間隔采樣點為k=0,1,2,…,N-1，zk點的頻譜分量為2025/1/2463令，則上式表明，要計算x(n)在半徑為r的圓上的等間隔頻譜分量，可以先對x(n)乘以r-n，再計算N點DFT(FFT)即可得到。若要求x(n)分布在該圓的有限角度內(nèi)N點等間隔頻譜分量，可以通過尾部補零的方法，仍按式(3-75)用DFT分析整個圓上的等間隔頻譜，最后只取所需角度內(nèi)的頻譜分量即可。顯然這種方法的計算量大，下面要介紹的Chirp-Z變換可使這種譜分析的運算量大大減少。3-752025/1