數(shù)字信號處理 黃海 課件第八章-離散傅里葉變換

第八章離散傅立葉變換TheDiscreteFourierTransform8.0引言幾種傅立葉變換的形式（1）傅立葉級數(shù)-----連續(xù)周期時間函數(shù)，周期為TX(jkΩT)----頻率成分的幅度，ΩT

=2π/T稱為基頻，離散序列

傅里葉級數(shù)的系數(shù)

時域：連續(xù)周期頻域：離散非周期（2）傅立葉積分x

(t)-----連續(xù)非周期時間函數(shù)X(jΩ)----連續(xù)頻域函數(shù)（頻譜）Ω表示頻率

時域：連續(xù)非周期頻域：連續(xù)非周期（3）序列的傅立葉變換x[n]-----

非周期離散序列（無限長、有限長）X(ejω)-----連續(xù)周期函數(shù)

時域：離散非周期頻域：連續(xù)周期用于實際計算（計算機）的傅立葉變換的要求：（1）時域序列-----有限長（2）其傅立葉變換-----離散序列-----有限長 時域：離散有限長頻域：離散有限長稱：離散傅立葉變換（DFT）離散傅立葉變換-------數(shù)字信號處理算法核心（基本）算法推導(dǎo)離散傅立葉變換：周期序列有限長序列之間關(guān)系第一步：周期序列的傅立葉變換-----離散傅立葉級數(shù)（DFS）第二步：周期序列有限長序列關(guān)系-----DFT8.1周期序列的表示：離散傅立葉級數(shù)定義為周期為N的周期序列，對任一整數(shù)n和r有：

考慮到：連續(xù)周期信號基頻的各次諧波（復(fù)指數(shù)函數(shù)）之和則，離散周期序列基頻為2π/N的復(fù)指數(shù)序列之和-----表示為離散傅立葉級數(shù)復(fù)指數(shù)序列：

周期序列離散傅立葉級數(shù)表示式（定義）：k為整數(shù)連續(xù)周期信號的傅立葉級數(shù)無窮多個諧波（頻率）（之和）離散周期信號的傅立葉級數(shù)l為整數(shù)，表示N個獨立周期復(fù)指數(shù)e0[n],e1[n],…,eN-1[n]則：N個獨立諧波（頻率）（之和）即：離散傅立葉級數(shù)的一半，直接構(gòu)造（定義）出，作為變換，需求出（推導(dǎo)）另一半（反變換）：對上述兩邊乘以e-j(2π/N)rn，并從n=0

到n=N-1求和，可得交換右邊求和次序，考慮到復(fù)指數(shù)的正交性：可得：即得傅立葉級數(shù)的系數(shù)：由于

--------周期序列，周期為N（對于所有k）也可以看成：有限長序列，對于k=0,…,(N-1),其它k，值為零合理性：只用到0≤k≤(N-1)的離散傅立葉級數(shù)（DFS）的表示式：時域：離散周期頻域：離散周期定義符號：DFS可表示為：記號：分析式（Analysisequation）綜合式（Synthesisequation）均為周期為N的周期序列例8.1周期脈沖串的離散傅立葉級數(shù)考慮一個周期脈沖串：周期為N的脈沖對于根據(jù)DFS定義式求出DFS系數(shù)為：再將結(jié)果代入綜合式：正交性：當(dāng)n=rN，指數(shù)序列和為1，否則為零DFS的對偶性例8.2離散傅立葉級數(shù)的對偶性令DFS的系數(shù)為一周期為N的周期脈沖串：代入DFS公式，得：與例8.1相比較，可以看到：非常相似，只相差常數(shù)因子和指數(shù)的符號例8.3周期矩形脈沖串的離散傅立葉級數(shù)周期N=10的矩形脈沖串（N=0~9）：求DFS,DFS-----離散周期時間序列的傅立葉變換（頻域表示）

有限長離散時間序列傅立葉變換（DFT）的基礎(chǔ)先討論DFS的性質(zhì)，然后導(dǎo)出DFT表示式8.2離散傅立葉級數(shù)的性質(zhì)傅立葉變換（不同形式）、拉氏變換、z變換性質(zhì)的相似性。注意點：，周期性重要差別8.2.1線性8.2.2序列的移位注意大于周期N的移位，即m≥N，若m=m1+m2N情況（無法區(qū)分）相似有頻域移位：8.2.3對偶性DFS的分析式與綜合式十分相似時域與頻域?qū)ε夹栽颍褐芷陔x散時間信號

（非周期信號與它的傅立葉變換是兩類十分不同的函數(shù)）對偶性8.2.4對稱性8.2.5周期卷積若：則有：或：說明： （1）兩個序列均為同周期N

（2）求和只在一個周期上進行證明：交換求和次序由DFS的移位性質(zhì)代入上式，可得表示為：例8.4周期卷積由對稱性，若有：8.2.6周期序列DFS表示的性質(zhì)匯總8.3周期信號的傅立葉變換序列傅立葉變換的收斂性一致收斂-----序列絕對可和均方收斂-----序列平方可和周期信號------既不滿足絕對可和也不滿足平方可和將周期信號的離散傅立葉級數(shù)(并入)傅立葉變換的框架

即：同為離散序列

或：回顧第二章序列傅立葉變換的推廣：如果序列能夠表示為復(fù)指數(shù)的和則其傅立葉變換可以表示為脈沖串的形式，即：表示每個指數(shù)序列對于離散周期序列，DFS的形式為：周期信號的傅立葉變換

------頻域的脈沖幅值正比于序列DFS

系數(shù)的一個脈沖串定義：周期序列的傅立葉變換：周期，周期為N，脈沖串的間隔是2π/N的整數(shù)倍

-----周期，周期為2π。證明：將上式代入序列的傅立葉變換式其中ε

滿足不等式0<ε

<(2π/N),包含ω

=0處的脈沖，而不包括ω

=2π處的脈沖。交換求和與積分次序ω=0~2π

的積分區(qū)間-----只包括對應(yīng)于k=0,1,….(N-1)的脈沖上述的工作表明：盡管周期序列的傅立葉變換在通常意義下是不收斂的但引入脈沖函數(shù)后，可以將周期序列納入傅立葉變換分析的框架內(nèi)------傅立葉變換的擴展（如雙邊常數(shù)序列、復(fù)指數(shù)序列等）例8.5周期脈沖串的傅立葉變換周期為N的周期脈沖串：由例8.1的結(jié)果知，對所有的k，其傅立葉變換為：周期信號有限長信號之間的關(guān)系（傅立葉變換意義上）有限長信號x[n]，在0≤n≤N-1區(qū)間外x[n]=0考慮其與周期脈沖串（周期為N）的卷積：表示周期序列可以看成是由有限長序列的周期重復(fù)序列組成：周期序列的傅立葉變換可以表示為：比較周期信號傅立葉變換的定義式：可以得出：表示：DFS系數(shù)的周期序列可以看成有限長序列傅立葉變換的等間隔采樣。該有限長序列是周期序列的一個周期：上述結(jié)果也可以簡單獲得：比較可得：例8.6傅立葉級數(shù)系數(shù)與一個周期的傅立葉變換之間的關(guān)系例8.3中周期序列的一個周期為（周期N=10）：其傅立葉變換為：可以證明，在本題情況下，將ω

=2πk/10代入上式，即可滿足周期序列的傅立葉級數(shù)：與例8.3結(jié)果相同。傅立葉級數(shù)與傅立葉變換之間的關(guān)系

之間的關(guān)系：周期信號有限長信號之間的關(guān)系有限長信號x[n]，在0≤n≤N-1區(qū)間外x[n]=0考慮其與周期脈沖串（周期為N）的卷積：表示周期序列可以看成是由有限長序列的周期重復(fù)序列組成：該有限長序列是周期序列的一個周期：由：比較可得：表示：DFS系數(shù)的周期序列可以看成有限長序列傅立葉變換的等間隔采樣。例8.6傅立葉級數(shù)系數(shù)與一個周期的傅立葉變換之間的關(guān)系例8.3中周期序列的一個周期為（周期N=10）：其傅立葉變換為：可以證明，在本題情況下，將ω

=2πk/10代入上式，即可滿足周期序列的傅立葉級數(shù)：與例8.3結(jié)果相同。傅立葉級數(shù)與傅立葉變換之間的關(guān)系

之間的關(guān)系：8.4對傅立葉變換采樣非周期序列：傅立葉變換X(ejω)周期序列：其DFS的系數(shù)為X(ejω)在頻率上等間隔的采樣（前提：周期序列是非周期序列的重復(fù)疊加產(chǎn)生）討論：周期序列與非周期序列的更一般關(guān)系考慮一非周期序列x[n]，其傅立葉變換為X(ejω)序列是通過對X(ejω)在ωk=2πk/N頻率處采樣得到，即為周期序列，周期為N，也可以表示為X(z)在單位圓上的N個等間隔采樣：圖是當(dāng)N=8時的采樣點，具有周期（重復(fù)）序列樣本序列是周期為N的周期序列，可以是一個序列的離散傅立葉級數(shù)的系數(shù)序列：因為已假定存在x[n]的傅立葉變換將上式代入并將結(jié)果代入前式，可得交換求和次序，得到：式中最終可以得出：表明：是一個周期序列（x[n]與周期單位脈沖串的卷積）與對應(yīng)的周期序列：x[n]平移（無數(shù)個）相加而是x[n]X(ejω)進行采樣結(jié)果圖中，x[n]的長度為9，平移的周期N=12，平移相加后序列沒有重疊。上圖表示取N=12，x[n]X(ejω)相同序列當(dāng)N取7時平移后的結(jié)果：序列有重疊。表示：為X(ejω)的采樣（頻域），N為每個周期（2π）的采樣點數(shù)。如果N大于x[n]的長度，得到的周期序列沒有重疊（時域混疊），從中可以得到（恢復(fù)）x[n]，同樣，X(ejω)也可以從恢復(fù)得到。時域采樣頻域混疊（現(xiàn)象）-----避免混疊頻域采樣時域混疊（現(xiàn)象）-----避免混疊歸納：非周期序列x[n]傅立葉變換X(ejω)的采樣===

x[n]周期重復(fù)得到的DFS的系數(shù)如果x[n]為有限長，只要對X(ejω)的采樣點數(shù)足夠多（≥x[n]

的長度N）,則X(ejω)可以由恢復(fù)得到，同樣，X(ejω)的恢復(fù)------內(nèi)插公式利用DFS表示有限長序列-------離散傅立葉變換（DFT）須記?。海?）有限長序列x[n]

實際上代表周期序列的一個周期 （2）同時也表示離散傅立葉變換隱含著周期性8.5有限長序列的傅立葉表示：離散傅立葉變換（DFT）DFT：時域有限長序列x[n]

頻域有限長序列X[k]DFS：時域周期序列頻域周期序列

表示為：N------x[n]

的長度，也是的周期表示為：或：由DFS求和區(qū)間：可得：有DFT表示為：說明：x[n]----N

點

沒有混疊意味著上式中等號表示為“等同于”頻域之間關(guān)系

由于DFT由DFS導(dǎo)出，并有 和x[n]和X[k]隱含著周期性DFT一般解釋：（1）有限長序列x[n]

的離散傅立葉變換X[k]是其序列傅立葉變換X(ejω)

主值周期[0,2π]的抽樣。（2）有限長序列x[n]

是周期序列的一個周期一個思考問題：x[n]

無限長？x[n]

截斷？x[n]

補零？例8.7矩形脈沖的DFT一矩形序列：可以看成一個長度N≥5的任意有限長序列若作為一個N=5的序列其相應(yīng)的周期序列為：求出DFS:表示只有在k=0和k=5的倍數(shù)處才有非零值，如圖所示：X(ejω)與的抽樣關(guān)系，的周期序列，X[k]可表示為：若將x[n]看成是一個N=10的有限長矩形序列，相應(yīng)的周期序列為：其X(ejω)和DFS為：

注意X(ejω)是相同的DFT為：表明：x[n]的上述改變，不影響其傅立葉變換X(ejω)

，但對X[k]的影響很大。------信號的補零問題，截斷的誤差問題哪個X[k]準確？8.6離散傅立葉變換的性質(zhì)關(guān)注點（差異性）：DFT隱含的周期性8.6.1線性兩個有限長序列x1[n]和x2[n]的線性組合：

x3[n]=ax1[n]+bx2[n]則x3[n]的DFT為：

X3[k]=aX1[k]+bX2[k]若x1[n]-----N1

x2[n]-----N2則X3[k]的計算長度N=N3=max[N1,N2]，需補零。

N≥max[N1,N2]情況？8.6.2序列的循環(huán)移位（circularshift）移位:(1)通常意義的移位，(2)周期移位，(3)循環(huán)移位相對應(yīng)的數(shù)學(xué)運算:(1)線性卷積,(2)周期卷積,

(3)循環(huán)卷積定義：有限長序列x[n]，長度為Nx[n]（周期延拓）（周期移位）（截取主值周期，0≤n≤N-1）記為x1[n]

即：若則例8.8序列的循環(huán)移位與線性移位的區(qū)別在區(qū)間內(nèi)移出移進8.6.3對偶性若則例8.9DFT的對偶關(guān)系長度N=10X[k]實部X[k]虛部8.6.4對稱性x[n]的共軛對稱、共軛反對稱、實數(shù) 與相應(yīng)的X[k]的共軛對稱、共軛反對稱、實數(shù)之間特性注意：或?qū)ΨQ特性8.6.5循環(huán)卷積定義：兩個長度均為N的有限長序列x1[n]和x2[n]或為循環(huán)卷積，記為：例8.10與延遲脈沖序列的循環(huán)卷積x2[n]------長度為N的有限長序列x1[n]------延遲脈沖序列

x1[n]=δ[n-n0]，0<n0<N可以表示為：其DFT為：若將其乘以x2[n]的DFTX2[k]:由DFT的移位性質(zhì)，相應(yīng)的時間序列x3[n]是x2[n]右移n0的結(jié)果也是循環(huán)卷積的結(jié)果。如下圖（n0=1）：例8.11兩個矩形脈沖的循環(huán)卷積若L=6=N，DFT為：將X1[k]和X2[k]直接相乘，得由此可得：x2[((n-m))N]若作2L點的循環(huán)卷積，兩個序列均補L個零，即N=2L與線性卷積結(jié)果相同DFT:DFT的循環(huán)卷積性質(zhì)可表示為：或式中N=L時等于18.6.6DFT性質(zhì)匯總8.7用離散傅立葉變換實現(xiàn)線性卷積卷積的快速計算方法：利用傅立葉變換的卷積性質(zhì)即，時域卷積頻域相乘（1）分別計算兩個時間序列的傅立葉變換，X1[k]，X2[k]（2）將兩個傅立葉變換相乘，X1[k]X2[k]（3）對結(jié)果進行傅立葉反變換，DFT的快速算法（FFT）上述過程的計算速度>>直接的卷積計算問題：實際問題的卷積運算------線性卷積線性系統(tǒng)的輸入輸出關(guān)系DFT的卷積（性質(zhì)）------循環(huán)卷積解決：循環(huán)卷積===線性卷積8.7.1兩個有限長序列的線性卷積x1[n]-----L點長；x2[n]-----P點長線性卷積：x3[n]-----(L+P-1)點長很顯然，與DFT相應(yīng)的循環(huán)卷積不同：（1）長度不同

x1[n]，x2[n]-----N點長（同長度）

x3[n]-----N點長（同長度）（2）結(jié)果不同

與所取的序列長度N有關(guān)（補零）8.7.2循環(huán)卷積作為帶有混疊的線性卷積討論循環(huán)卷積計算的長度線性卷積的關(guān)系循環(huán)卷積作為線性卷積產(chǎn)生誤差的原因------時域混疊（從理論上）線性卷積：

x1[n]-----L點長；x2[n]-----P點長定義一個DFT，即對X3(ejω)的主值周期（0--2π）N點抽樣：亦即，

(L+P-1)點長均為N點長相應(yīng)的時間序列：和-------循環(huán)卷積

是否有混疊也就是X3[ejω]抽樣過程中是否保證

N≥（L+P-1）------x3[n]的長度循環(huán)卷積==線性卷積的條件（從圖示上）例8.12循環(huán)卷積作為帶有混疊的線性卷積x1[n]=x2[n]-----常數(shù)序列，長度L=P=6x3[n]長度L+P–1=11有混疊的循環(huán)卷積++=有貢獻有貢獻無貢獻很顯然，當(dāng)N=2L時，周期疊加的結(jié)果不產(chǎn)生混疊，其結(jié)果也與線性卷積相同。（此時只有x3[n]

對結(jié)果有貢獻）N=2L=12，在0≤n≤N-1內(nèi)結(jié)果一樣。8.7.3用DFT實現(xiàn)線性時不變系統(tǒng)系統(tǒng)輸入：x

[n]-----L點長系統(tǒng)脈沖響應(yīng)：h

[n]-----P點長系統(tǒng)輸出：-----(L+P-1)點長x

[n]，h

[n]

均補零到(L+P-1)點長X

[k]H

[k]y

[n]

許多實際情況：（1）輸入無限長，或很長（2）輸出延遲要小直接用DFT進行線性卷積運算不能滿足要求解決的方法：塊卷積

-----對輸入進行分段計算系統(tǒng)的輸出銜接得到輸出每一段輸入對應(yīng)的系統(tǒng)輸出-------應(yīng)用DFT實現(xiàn)脈沖響應(yīng)h[n]長度P輸入序列x[n]分段長度LL>P輸入序列可表示為：輸出的卷積運算可表示為：其中：xr[n]非零點（長度）------Lh[n]非零點（長度）------Pyr[n]非零點（長度）------L+P-1可用N

≥L+P-1點DFT計算注意：xr[n]的起點：0，L，2L，3L，…

每一個yr[n]重疊（P-1）點，須參與求和運算稱為重疊相加法（overlap-addmethod）分段卷積塊卷積的另一種算法------重疊保留法（overlap-savemethod）（1）P點h[n]與L點xr[n]的L點循環(huán)卷積（2）保留循環(huán)卷積結(jié)果中對應(yīng)于線性卷積的部分（3）每段結(jié)果最后組合成輸出y[n]L點序列與P點序列（L>P）循環(huán)卷積（P點序列補零到L長度）：即L點循環(huán)卷積：前（P-1）點不正確，其余點與線性卷積結(jié)果相等輸入序列的分段：每段長度仍為L前后段重疊（P-1）點即：每一段卷積結(jié)果yrp[n]的前面（P-1）部分必須去掉，再將結(jié)果頭尾相接組成輸出序列y

[n]：式中8.8離散余弦變換（DCT）信號變換-------信號分解： 一組（可以是無窮）函數(shù)的線性組合如DFT，一組指數(shù)序列（函數(shù)）的線性組合（加權(quán)和）X(ejω)即為加權(quán)系數(shù)------物理意義不同的函數(shù)組------不同的信號變換存在無窮多個不同的函數(shù)組--------具有無窮多個不同的信號變換傅立葉變換只是其中具有特殊意義的一種變換這種函數(shù)組------基函數(shù)（basisfunction）對應(yīng)于矢量分解中的基矢量矢量空間（線性代數(shù)）-------函數(shù)空間（泛函）基函數(shù)（序列）特性： 正交性（最主要特性之一）

DFT是典型的一種由上述的理論與思想，一般類有限長變換可以表示為：很顯然，DFT可以看成其中的一個例子式中φk[n]為基序列，它們相互正交：對應(yīng)于DFT，基序列φk[n]=ej2πkn/N尋找一組基序列（當(dāng)x[n]為實序列時）：（1）基序列本身是實序列；（2）變換序列A[k]也是實序列。8.8.1DCT的定義參考DFT的推導(dǎo)：有限長序列周期序列頻域關(guān)系表示（恢復(fù)）原序列DCT:（根據(jù)DFT的實偶對稱性質(zhì)）（實質(zhì)：DFT的一種特殊形式）有限長序列周期的對稱序列能夠唯一恢復(fù)原有限長序列構(gòu)成周期的對稱序列方式------多種-----不同種類的DCT例一個N=4點序列的例子：原4點序列作為周期對稱序列的前4點-------周期可以不同周期:(2N-2)=6關(guān)于n=0和n=(N-1)=3偶對稱周期:

2N=8關(guān)于n=-1/2和n=7/2偶對稱（半樣本點對稱）周期:

4N=16關(guān)于n=0和n=8偶對稱4種類型的周期延拓分別對應(yīng)于4種離散余弦變換，即DCT-1，DCT-2，DCT-3和DCT-4常用：DCT-1和DCT-2周期:

4N=16關(guān)于n=-1/2和n=15/2偶對稱（半樣本點對稱）8.8.2DCT-1和DCT-2的定義周期延拓：N點序列