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

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

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

傅里葉級數的系數

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

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

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

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

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

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

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

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

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

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

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

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

即：同為離散序列

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

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

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

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

滿足不等式0<ε

<(2π/N),包含ω

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

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

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

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

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

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

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

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

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

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

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

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

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

點

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

由于DFT由DFS導出，并有 和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的序列其相應的周期序列為：求出DFS:表示只有在k=0和k=5的倍數處才有非零值，如圖所示：X(ejω)與的抽樣關系，的周期序列，X[k]可表示為：若將x[n]看成是一個N=10的有限長矩形序列，相應的周期序列為：其X(ejω)和DFS為：

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

，但對X[k]的影響很大。------信號的補零問題，截斷的誤差問題哪個X[k]準確？8.6離散傅立葉變換的性質關注點（差異性）：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)移位相對應的數學運算:(1)線性卷積,(2)周期卷積,

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

即：若則例8.8序列的循環(huán)移位與線性移位的區(qū)別在區(qū)間內移出移進8.6.3對偶性若則例8.9DFT的對偶關系長度N=10X[k]實部X[k]虛部8.6.4對稱性x[n]的共軛對稱、共軛反對稱、實數 與相應的X[k]的共軛對稱、共軛反對稱、實數之間特性注意：或對稱特性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的移位性質，相應的時間序列x3[n]是x2[n]右移n0的結果也是循環(huán)卷積的結果。如下圖（n0=1）：例8.11兩個矩形脈沖的循環(huán)卷積若L=6=N，DFT為：將X1[k]和X2[k]直接相乘，得由此可得：x2[((n-m))N]若作2L點的循環(huán)卷積，兩個序列均補L個零，即N=2L與線性卷積結果相同DFT:DFT的循環(huán)卷積性質可表示為：或式中N=L時等于18.6.6DFT性質匯總8.7用離散傅立葉變換實現線性卷積卷積的快速計算方法：利用傅立葉變換的卷積性質即，時域卷積頻域相乘（1）分別計算兩個時間序列的傅立葉變換，X1[k]，X2[k]（2）將兩個傅立葉變換相乘，X1[k]X2[k]（3）對結果進行傅立葉反變換，DFT的快速算法（FFT）上述過程的計算速度>>直接的卷積計算問題：實際問題的卷積運算------線性卷積線性系統(tǒng)的輸入輸出關系DFT的卷積（性質）------循環(huán)卷積解決：循環(huán)卷積===線性卷積8.7.1兩個有限長序列的線性卷積x1[n]-----L點長；x2[n]-----P點長線性卷積：x3[n]-----(L+P-1)點長很顯然，與DFT相應的循環(huán)卷積不同：（1）長度不同

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

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

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

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

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

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

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

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

[n]-----L點長系統(tǒ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)的輸出銜接得到輸出每一段輸入對應的系統(tǒng)輸出-------應用DFT實現脈沖響應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)卷積結果中對應于線性卷積的部分（3）每段結果最后組合成輸出y[n]L點序列與P點序列（L>P）循環(huán)卷積（P點序列補零到L長度）：即L點循環(huán)卷積：前（P-1）點不正確，其余點與線性卷積結果相等輸入序列的分段：每段長度仍為L前后段重疊（P-1）點即：每一段卷積結果yrp[n]的前面（P-1）部分必須去掉，再將結果頭尾相接組成輸出序列y

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

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

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

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

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