數(shù)字信號處理 第三章 快速傅里葉變換 復習ppt課件

1、第3章 快速傅里葉變換 數(shù)字信號處理數(shù)字信號處理Digital Signal Processing(DSP)信息學院電子系信息學院電子系第3章 快速傅里葉變換 第3章 快速傅里葉變換 3.1 引言引言 3.2 直接計算直接計算DFT的問題及改進的途徑的問題及改進的途徑 3.3 按時間抽取按時間抽取DIT的基的基2-FFT算法算法3.4 按頻率抽取按頻率抽取DIF的基的基2-FFT算法算法3.5 N為復合數(shù)的為復合數(shù)的FFT算法算法 3.6 線性調(diào)頻線性調(diào)頻Z變換變換Chirp-Z變換變換算法算法 3.7 利用利用FFT分析時域連續(xù)信號頻譜分析時域連續(xù)信號頻譜 3.8 FFT的其他應用的其他應用

2、 第3章 快速傅里葉變換 3.1 引引 言言 DFT實現(xiàn)了時域序列的頻域離散化, 因此在數(shù)字信號處理中用途很廣 但是DFT的計算量太大，不適于實時處理，所以沒有得到真正的運用 快速傅里葉變換(FFT)就是為了縮短DFT運算時間而產(chǎn)生的, 運算時間一般可縮短一二個數(shù)量級 FFT并不是一種新的變換,而是DFT的一種快速算法第3章 快速傅里葉變換 3.2 直接計算直接計算DFT的問題及改進的途徑的問題及改進的途徑 3.2.1 直接計算直接計算DFT的運算量問題的運算量問題10)()(NnnkNWnxkXk=0, 1, , N-1 設x(n)為N點有限長序列，其DFT為 通常x(n)和WNnk都是復數(shù)

3、，因此一個X(k)需要N次復數(shù)乘法和N-1次復數(shù)加法 完成整個DFT運算則需要N2次復數(shù)乘法及N(N-1)次復數(shù)加法 由于DFT的運算次數(shù)與N2成正比, N較大時, 運算量非?？捎^第3章 快速傅里葉變換 例對一幅例對一幅NN點的二維圖像進行點的二維圖像進行DFT變換，當變換，當N=1024時時, 直接直接計算計算DFT所需復乘次數(shù)為所需復乘次數(shù)為1012次，用每秒可做次，用每秒可做10萬次復數(shù)乘法的萬次復數(shù)乘法的計算機計算需要近計算機計算需要近3000小時小時3.2.2 改善途徑改善途徑 把長序列的DFT分解成短序列的DFT運算利用系數(shù)Wnk的特性 對稱性 2*()()jnknknkNNNWe

4、W周期性 )()(NknNkNnNnkNWWW可約性 2jmnknknmkmNNmNWeW/2(/2)1,NkNkNNNWWW 其它第3章 快速傅里葉變換 3.3 按時間抽取按時間抽取DIT的基的基 -2 FFT算法算法 設序列x(n)長度為N，且滿足N=2M，M為正整數(shù)。按n的奇偶把x(n)分解為兩個N/2點的子序列： 12, 1 , 0)() 12()()2(21Nrrxrxrxrx FFT分為兩大類: 按時間抽取法(Decimation in Time) 和按頻率抽取法(Decimation in Frequency) ,本節(jié)先介紹第一種算法3.3.1 算法原理算法原理 一個N點DFT的

5、分解第3章 快速傅里葉變換 將DFT x (n)分解為DFTx1(r) 與DFTx2(r)的線性組合 10( ) ( )( )NnkNnX kDFT x nx n W12( )( )kNX kW Xk11222(21)00(2 )(21)NNrkrkNNrrxr WxrW1122221200( )( )NNrkrkNkNNrrWx r Wx r W11221200/2/2( )( )rkkrNNrrkNNNWWx rx r W12(2 )( )(21)( )xrx rxrx r代入 /2/2 1110/2 12202( )( )( )( )rkNrkNNrNrDFT x rx rDFTWx r

6、x r W第3章 快速傅里葉變換 重寫DFT12( )( )(0,1,2)/1kNXkkXNkkW X(X1(k)與X2(k)分別是x1(r)及x2(r)的N/2點DFT ) 112211/2/200112222/2/200( )( )(2 )( )( )(21)NNrkrkNNrrNNrkrkNNrrX kx r Wxr WXkx r WxrW上式為X(k)的前一半值,而后一半值可表示為212()()()0,1,/21222NkNNNNX kXkWXkkN第3章 快速傅里葉變換 12NXk121/20( )NrkNrx r W22NXk/22NkNkNNNWWWkNW 212()()()0,

7、1,/21222NkNNNNX kX kWXkkN化簡1221/20( )NNrkNrx r W1( )X k2( )Xk22NjkNNeW12()( )( )0,1,/2 12kNkNX kX kW XkN得到第3章 快速傅里葉變換 上式將N點DFT分解為兩個N/2點的DFT運算，運算過程如下圖示X2(k)X1(k)kNW1X1(k)kNWX2(k)X1(k)kNWX2(k)時間抽取法蝶形運算流圖分解后運算工作量節(jié)省了近一半12120,1,120,1,12( )( )( )( )( )2kNkNX kX kW XkNX kX kW XkNkNk 將X(k)表達式為前后兩部分,重寫如下第3章

8、快速傅里葉變換 N點DFT的一次時域抽取分解過程見下圖N=8） 第3章 快速傅里葉變換 兩個N/2點DFT的分解N點DFT分解1212( )( )( )( )( )2kNkNX kXkWXkNXkXkWXk12(2 )( )(21)( )xrx rxrx r,0,1,12Nr k X1(k)的分解的分解 由于N=2M仍是偶數(shù)，可以把每個N/2點子序列再進行分解1314(2 )( )(21)( )xlx lxlx l134134/2/2( )( )( )( )( )4kNkNXkXkXkNXkXkWXWk,0,1,14Nr k第3章 快速傅里葉變換 1314(2 )( )(21)( )xlx l

9、xlx l134134/2/2( )( )( )( )( )4kNkNXkXkXkNXkXkWXWkN/2點DFT分解,0,1,14Nr k X1(k)分解圖示分解圖示2222/2/2jkjkkkNNNNWeeW第3章 快速傅里葉變換 X2(k)的分解圖示的分解圖示)()(4)()()(62/5262/52kXWkXkNXkXWkXkXkNkN,0,1,14Nr k2526(2 )( )(21)( )xlx lxlx l第3章 快速傅里葉變換 N點DFT的第二次時域抽取分解圖N=8）第3章 快速傅里葉變換 N點DFT的第二次時域抽取分解圖N=8）DFT4點NX3(0)X3(1)x3(0) x1

10、(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4點NX4(0)X4(1)x4(0) x1(1) x(2)x4(1) x1(3) x(6)X1(2)X1(3)110NW2NWX(0)X(1)X(2)X(3)DFT4點NX5(0)X5(1)x5(0) x2(0) x(1)x5(1) x2(2) x(5)X2(0)X2(1)DFT4點NX6(0)X6(1)x6(0) x2(1) x(3)x6(1) x2(3) x(7)X2(2)X2(3)11X(4)X(5)X(6)X(7)0NW1NW2NW3NW11110NW2NW第3章 快速傅里葉變換 上式不需要乘法, 類似可求出X4

11、(k)，X5(k)，X6(k) 四個N/4點DFT的計算 X3(k)的分解的分解0021NWW 032032(0)(0)(4)(1)(0)(4)XxW xXxW x0303(0)(0)(4)(1)(0)(4)NNXxW xXxW x第3章 快速傅里葉變換 完整的N=8 DIT-FFT運算流圖x(0)X(0)x(4)X(1)10NWx(2)X(2)x(6)X(3)10NW0NW2NW11x(1)X(4)x(5)X(5)10NWx(3)X(6)x(7)X(7)10NW0NW2NW110NW1NW2NW3NW1111由于輸入序列在時域上進行奇偶分解，故稱為“按時間抽取法” N=2M點的FFT共進行M

12、級運算，每級由N/2個蝶形運算組成第3章 快速傅里葉變換 3.3.2 DIT-FFT算法與直接計算算法與直接計算DFT運算量的比較運算量的比較 直接計算DFT與FFT算法的計算量之比為 22222NNNlog Nlog NN越大，F(xiàn)FT的優(yōu)點越為明顯例例3-2 P109 3000h-2m第3章 快速傅里葉變換 3.3.3 按時間抽取的按時間抽取的FFT算法的特點算法的特點1. 1. 原位運算同址運算）原位運算同址運算） 定義：利用同一存貯單元存貯蝶形運算輸入、輸出數(shù)據(jù)的方法 DIT-FFT的運算規(guī)律 同一級中，每個蝶形的兩個輸入數(shù)據(jù)只對計算本蝶形有用，可采用原位運算，則全部運算過程只需要N個存

13、儲單元 1rNWXm 1(k)Xm 1( j)Xm(k) Xm 1(k) Xm 1( j)Xm( j) Xm 1(k) Xm 1( j)rNWrNW第3章 快速傅里葉變換 2. 倒位序規(guī)律 （ N=2M） 輸入序列的排序為N的二進制倒位序，輸出序列則為自然順序N8時的輸入輸出值第3章 快速傅里葉變換 3. 蝶形運算兩節(jié)點的“間隔” 對N=2M點FFT，當輸入為倒位序， 輸出為正常順序時，其第m級運算，每個蝶形的兩節(jié)點“間隔為2m-1 x(0)X(0)x(4)X(1)10NWx(2)X(2)x(6)X(3)10NW0NW2NW11x(1)X(4)x(5)X(5)10NWx(3)X(6)x(7)X

14、(7)10NW0NW2NW110NW1NW2NW3NW1111x(0), x(1)x(0), x(2)x(0), x(4)第3章 快速傅里葉變換 3.3.4 按時間抽取的按時間抽取的FFT算法的其他形式流圖算法的其他形式流圖 對于任何流圖，只要保持各節(jié)點所連的支路及傳輸系數(shù)不變，則不論節(jié)點位置怎么排列所得流圖總是等效的將左圖x(4)與 x(1) , x(6)與x(3)對調(diào)第3章 快速傅里葉變換 時間抽取、 輸入自然順序、 輸出倒位序的FFT流圖特點 數(shù)據(jù)存放的方式不同 取用系數(shù)的順序不同第3章 快速傅里葉變換 3.4 按頻率抽取按頻率抽取DIF的基的基 -2 FFT算法算法 3.4.1 算法原

15、理算法原理10( )( )NnkNnX kx n W將長度為N=2M的序列x(n)前后對半分開, 其N點DFT可表示為1122200( )2NNNnknkNNnnNx n Wx nWk=0, 1, , N-1 12/20( )2NNknkNNnNx nx nWW統(tǒng)一求和區(qū)間11202( )( )NNnknkNNNnnx n Wx n W第3章 快速傅里葉變換 按k的奇偶可將X(k)分為兩部分: 1220(2 )( )2NnrNnNXrx nx nW12, 1 , 0Nr/21,( 1)1kNkNkWk 偶數(shù) 奇數(shù) 式中k=0, 1, , N-1 12/20( )( )2NNknkNNnNX k

16、x nx nWW k取偶數(shù)時120/2( )2nrNNnNx nx nWx(n)前后兩部分和的N/2點DFT第3章 快速傅里葉變換 k取奇數(shù)時12(21)0(21)( )2NnrNnNXrx nx nW12, 1 , 0Nr2120/( )2nnrNnNNNx nx nWWx(n)前后兩部分差再乘以WNn后的N/2點DFT12/20( )2(2 )NnrNnNXnrxWx n k取偶數(shù)時令12( )2( )2( )( )nNNx nx nNx nxx nnWnx12, 1 , 0Nr代入上式第3章 快速傅里葉變換 1x(n)x(n N / 2)nNWx(n) x(n N / 2)x(n) x(

17、n N / 2)nNW上式表明, X(k)按k的奇偶分為兩組,其偶(奇)數(shù)組是x1(n)(x2(n)的N/2點DFT. x1(n), x2(n)與x(n)間的關系也可用下面蝶形運算流圖表示式中12( )2( )2( )( )nNNx nx nNx nxx nnWnx/2 11/20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx n WXrx n W得到第3章 快速傅里葉變換 按頻率抽取的N點DFT第一次分解(N=8) /2 11/20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx n WXrx n W式中12( )2( )2( )( )nNNx

18、nx nNx nxx nnWnx第3章 快速傅里葉變換 與DIT-FFT一樣，由于N/2仍為偶數(shù)，繼續(xù)將每個N/2點DFT輸出再分解為偶數(shù)組與奇數(shù)組,直到第M次N=2M） 按頻率抽取完整的N點DFT運算流圖 (N=8) 第3章 快速傅里葉變換 3.4.2 DIF-FFT與與DIT-FFT的聯(lián)系的聯(lián)系 DIF的基本蝶形與DIT的基本蝶形互為轉(zhuǎn)置DIT蝶形運算流圖DIF蝶形運算流圖第3章 快速傅里葉變換 兩種FFT運算方法等價 DIT-FFTDIF-FFT 第3章 快速傅里葉變換 3.4.3 IDFT的高效算法的高效算法FFT算法同樣可以用于 IDFT，稱為快速傅里葉反變換(IFFT)比較DFT和

19、IDFT的運算公式:1010( ) ( )( )1( )( )( )NknNnNknNkX kDFT x nx n Wx nIDFT X kX k WN第3章 快速傅里葉變換 左圖為在DIF-FFT流圖上改動后，得到的DIT-IFFT運算流圖第3章 快速傅里葉變換 3.4.3 IDFT的高效算法的高效算法上述IFFT算法需要改動FFT的程序和參數(shù)才能實現(xiàn)。也可以利用DFT的性質(zhì)，直接用FFT程序來完成IDFT的運算101( )( )NknNkx nX k WN知101( )( )NknNkx nXk WN 兩邊取共軛1( )( )x nDFT XkN(1)DFT XNk兩邊再取共軛第3章 快速

20、傅里葉變換 3.5 N為復合數(shù)的為復合數(shù)的FFT算法算法 第3章 快速傅里葉變換 3.6 線性調(diào)頻線性調(diào)頻Z變換變換Chirp-Z變換算法變換算法 vFFT算法用于計算有限長序列的z變換X(z)在z平面單位圓上N個等間隔抽樣點zk上的采樣值v實際應用中在很多情況下并不一定需要計算全部頻譜值,而僅需對某一頻帶內(nèi)的信號頻譜作較密集的分析v另外，采樣也不一定局限于單位圓上，而需要計算出某一螺旋線上的等角度間隔的采樣值v 例如語音信號分析時，往往在靠近語音信號序列z變換的極點的螺旋線上進行采樣，可以使語音信號的共振峰變得更尖銳，便于精確確定共振峰頻率第3章 快速傅里葉變換 3.6 線性調(diào)頻線性調(diào)頻Z變

21、換變換Chirp-Z變換變換算法算法 v線性調(diào)頻z變換就是利用FFT快速計算螺旋線采樣的算法ooooABX(ej)RezRezjImzjImzAB(a)(b)X(ej) 沿單位圓采樣 沿AB弧采樣 第3章 快速傅里葉變換 3.6.1 算法基本原理算法基本原理為適應z可以沿Z平面更一般的路徑取值，沿Z平面上的一段螺線作等分角的采樣，采樣點zk為 10)()(NnnznxzX設有限長序列x(n)的Z變換為 式中: A和W都是任意復數(shù), 設0000jjAA eWW ezk=AW-k k=0, 1, , M-1 M為采樣點的總數(shù)0000jjkkkzA eWe綜合上式得到 00()00jkkAWe第3章

22、 快速傅里葉變換 )(00000000kjkjkkjkeWAeWeAz zk參數(shù)的物理意義 0jImzRezo0A01.0zM1A0W01z0(M I)0螺線采樣 A0: 起始采樣點z0的矢量半徑0: 起始采樣點z0的相角0: 兩相鄰采樣點之間的角度差 W0: 表示螺線的伸展率序列的DFT是Chirp-Z變換的特例第3章 快速傅里葉變換 1100()( )( )NNnnnkkknnX zx n zx n A W 0kM-1 將zk=AW-k代入x(n)的Z變換變換表達式中,得到 Chirp-Z變換公式 Chirp-Z變換的FFT 算法直接計算Chirp-Z變換公式的計算量很大, 但可以將其轉(zhuǎn)換

23、為卷積形式, 從而利用FFT算法, 提高運算速度 第3章 快速傅里葉變換 將公式中的nk做一變換2221() 2nknkkn Chirp-Z變換公式的卷積形式1100()( )( )NNnnnkkknnX zx n zx n A W 0kM-1 代入公式, 整理后得到222()12220() ( )knk nNnknX zWx n A WW(卷積形式 )與卷積公式比較 10( )( )( ) ()Nng kh kg n h kn2222( )( )( )nnng nx n A Wh nW當X(zk)可表示成卷積形式第3章 快速傅里葉變換 )()()(22khkgWzXkkk=0, 1, , M

24、-1 卷積形式的Chirp-Z公式可采用FFT算法，從而提高運算速度x(n)2/ 2 )(nWnh2/ 2nnWAg(n)h(n)1 / h(n)X(zn) Chirp-Z變換的計算框圖如下第3章 快速傅里葉變換 3.6.2 Chirp-Z變換的特點變換的特點輸入序列和輸出序列長度不需要相等, 且二者均可為素數(shù) 分析頻率點zk的起始點z0及相鄰兩點的夾角0是任意的(即頻率分辨率是任意的)， 因此可從任意頻率上開始， 對輸入數(shù)據(jù)進行窄帶高分辨率的譜分析 譜分析路徑可以是螺旋形的 Chirp-Z變換在一定條件下就是序列的DFT 與標準DFT(FFT)算法相比較， Chirp-Z變換有以下特點:第3

25、章 快速傅里葉變換 3.7 利用利用FFT分析時域連續(xù)信號頻譜分析時域連續(xù)信號頻譜 3.7.1 基本步驟基本步驟 時域連續(xù)信號離散傅里葉分析的處理步驟如下圖示 LPFsc(t)Ha(j)xc(t)A / Dx(n)w(n)v(n)DFTV(k)頻譜分析是指計算信號各個頻率的幅值, 相位和功率 處理過程分析第3章 快速傅里葉變換 LPF : 避免在模擬信號轉(zhuǎn)換成序列時, 可能出現(xiàn)的頻譜混疊現(xiàn)象TmjTjXTeXmcj21)(LPFsc(t)Ha(j)xc(t)A / Dx(n)w(n)v(n)DFTV(k)A/D: 時域離散化,得到采樣序列x(n)，其頻譜用X(ej)表示第3章 快速傅里葉變換

26、DFT(FFT)運算: 加窗后的DFT是 102)()(NnnkNjenvkV0kN-1 LPFsc(t)Ha(j)xc(t)A / Dx(n)w(n)v(n)DFTV(k)w(n): 窗函數(shù).為進行FFT，須對x(n)加窗處理，即v(n)=x(n)w(n)第3章 快速傅里葉變換 對連續(xù)信號進行譜分析時，主要關心兩個問題：即譜分析范圍與頻率分辨率 譜分析范圍與頻率分辨率 譜分析范圍(所能分析的最高頻率)受采樣頻率的限制 頻率分辨率用頻率采樣間隔F描述，表示譜分析中能夠分辨的兩個頻譜分量最小間隔。F較小時，稱頻率分辨率較高第3章 快速傅里葉變換 有限長序列v(n)=x(n)w(n)的DFT相當于

27、v(n)FT的等間隔采樣 kNjeVkV2)()(V(k)是sc(t)的離散頻率函數(shù)， V(k)的第k點對應的模擬頻率為: NTkTk22kkkfNT 譜分析范圍與頻率分辨率顯然，數(shù)字域頻率間隔=2/N 對應的模擬域譜線間距應為 NfNTFs1( fs 為采樣頻率) 譜線間距: 即頻譜分辨率，指可分辨兩頻率的最小間距第3章 快速傅里葉變換 NfNTFs1( fs 為采樣頻率) T為采樣時間間隔(s) fs為采樣頻率(Hz) F為譜線間距,頻譜分辨率(Hz) tp為截取連續(xù)時間信號的樣本長度, 又稱記錄長度(s) DFT對連續(xù)信號譜分析時，參數(shù)間的關系及選擇原則例 時間序列v(n)=(1.1)n

28、R16(n)與16點的DFT 的如下圖所示第3章 快速傅里葉變換 參數(shù)間的關系11psptNTfFNNTt 參數(shù)的選擇(T、tp和N)實際應用中, 根據(jù)信號最高頻率fh和頻譜分辨率F的要求來確定三個參數(shù) DFT對連續(xù)信號譜分析時，參數(shù)間的關系及選擇原則第3章 快速傅里葉變換 采樣周期T的選擇：1 2hTf為保證采樣信號不失真應滿足，fs2fh，即周期T11psptNTfFNNTt說明：信號的譜分析范圍 fh與頻率分辨率F存在矛盾關系解釋：如果保持采樣點數(shù)N不變，而提高譜的分辨率(F減小)， 必須降低采樣速率fs ，從而引起譜分析范圍 fh 減少解決方法：如維持fs不變, 為提高分辨率，可以考慮

29、增加采樣點數(shù)N與觀察時間Tp第3章 快速傅里葉變換 N的選擇由頻譜分辨率F和T確定）1sfNFFT11psptNTfFNNTt 最小記錄長度tp的選擇由N, T確定）1ptNTF第3章 快速傅里葉變換 例例 一頻譜分析器，其采樣點數(shù)必須是一頻譜分析器，其采樣點數(shù)必須是2的整數(shù)冪，知的整數(shù)冪，知 頻率分辨率頻率分辨率10 Hz; 信號最高頻率信號最高頻率4kHz。試求。試求(1) 最小記錄長度最小記錄長度tp；(2) 最大采樣間隔最大采樣間隔T即最小采樣頻率即最小采樣頻率)；(3) 在一個記錄中的最少點數(shù)在一個記錄中的最少點數(shù)N 1 211hspTffNFFTtNTF解題思路知 F=10 Hz,

30、 fh=4 kHz1ptNTF(1)1 2hTf(2)1sfNFFT(3)取 2mN 第3章 快速傅里葉變換 由信號的時域波形圖估計最高頻率 最高頻率1/(2*相鄰峰谷間的最小距離) 信號最高頻率fh的估計tt3t4ot1t2x(t)例：如下圖示)(214Hztfh第3章 快速傅里葉變換 3.7.2 利用利用FFT對連續(xù)信號進行傅里葉分析時可能造成的誤差對連續(xù)信號進行傅里葉分析時可能造成的誤差1. 頻譜混疊失真頻譜混疊失真 當時域采樣頻率不滿足fs2fh 時，會產(chǎn)生頻譜混疊失真 對于FFT，頻率函數(shù)也要采樣成離散序列，因此為兼顧fh與F，必要時需增加記錄長度的點數(shù)N一般取 fs=(2.53.0

31、) fh 第3章 快速傅里葉變換 3.7.2 利用利用FFT對連續(xù)信號進行傅里葉分析時可能造成的誤差對連續(xù)信號進行傅里葉分析時可能造成的誤差2. 柵欄效應柵欄效應利用FFT計算頻譜，只能得到有限點的頻譜采樣值，而采樣點間的頻譜函數(shù)是不知道的，這就像通過一個“柵欄觀看信號頻譜,只能在離散點上看到信號頻譜，稱之為“柵欄效應”。由于柵欄效應，有可能漏掉(擋住)大的頻譜分量第3章 快速傅里葉變換 減小柵欄效應的方法： 增加頻域采樣點數(shù)N，通過在時域數(shù)據(jù)末端添加零點，使一個周期內(nèi)的點數(shù)增加，但并不改變原有的記錄數(shù)據(jù) 說明：補零不能提高頻率分辨率2. 柵欄效應柵欄效應第3章 快速傅里葉變換 cos(n/4

32、) 頻譜 3. 由截斷效應引起的頻譜泄漏與譜間干擾由截斷效應引起的頻譜泄漏與譜間干擾實際中的序列x(n)有可能是無限長的，為進行DFT運算，x(n)需要進行加窗處理變成有限長序列，截斷后序列的頻譜與原序列頻譜必然有差別, 主要表現(xiàn)為泄漏與譜間干擾矩形窗函數(shù)的幅度譜 加矩形窗后的頻譜 第3章 快速傅里葉變換 泄漏：截斷后的序列不再是單一譜線，而是向附近展寬。泄漏使頻譜變模糊，使譜分辨率降低譜間干擾：主譜線兩邊形成很多旁瓣，將引起不同頻率分量間的干擾。特別是強信號譜的旁瓣可能湮沒弱信號的主譜線加矩形窗后的頻譜 cos(n/4) 頻譜 第3章 快速傅里葉變換 加矩形窗后的頻譜 減小兩種影響的措施：c

33、os(n/4) 頻譜 增加窗的時域?qū)挾萅 可使頻域主瓣變窄 采用其它緩變的窗代替矩陣窗，可使旁瓣能量更小，從而減少譜間干擾 N一定時，旁瓣越小的窗函數(shù)，其主瓣就越寬。因此只能以降低譜分辨率為代價，換取譜間干擾的減小第3章 快速傅里葉變換 3.7.3 頻譜分析的應用頻譜分析的應用)()()(1kjXkXkXR實信號x(n)的頻譜是共軛偶對稱的，故只要求出k在0, 1, N/2上的X(k)即可。 將X(k)寫成極坐標形式 )(arg| )(|)(kXjekXkX式中，|X(k)|稱為幅頻譜，argX(k)稱為相頻譜。 頻譜圖 一個長度為N的時域離散序列x(n)，其DFT可表示為 由上式繪成的圖形稱

34、為頻譜圖。從圖中可以知道信號存在哪些頻率分量第3章 快速傅里葉變換 實際也常用功率譜表示，主要用于分析帶有噪聲干擾的信號NkXkPSD2| )(|)( 功率譜 頻率軸幾種定標方式的對應關系oooooN / 4N / 2k / (rad / s)f / Hzf / rad0.5fs / 2s / 2第3章 快速傅里葉變換 例例 用頻譜分析下列時域信號的組成用頻譜分析下列時域信號的組成( fs=32 Hz )對序列作32點DFT，|X(k)|如右圖示。頻率分辨率 F=fs/N=1Hz 2 10120102030(a )(b )0051015816nkx(n )|X (k)| 2 101201020

35、30(a )(b )0051015816nkx (n )|X (k)|第3章 快速傅里葉變換 3.8 FFT的其它應用的其它應用 3.8.1 線性卷積的線性卷積的FFT算法算法快速卷積快速卷積 1. FFT的快速卷積法利用圓周卷積的的快速卷積法利用圓周卷積的FFT計算線性卷積）計算線性卷積）補L N個零點L點DFT補L M個零點L點DFTL點IDFTy(n)h(n)x(n) FFT計算y(n)的步驟 求H(k)=DFTh(n) 求X(k)=DFTx(n) 計算Y(k)=X(k)H(k); 求y(n)=IDFTY(k) 第3章 快速傅里葉變換 運算量的比較直接線性卷積和FFT法計算線性卷積） x

36、(n)與h(n)點數(shù)差不多時, 有如下結果(KM為兩種卷積運算量比值)M=L8163264128256512102420484096Km0.572 0.9411.62.785.928.821629.2453.999.9當M=L且M超過32以后，M越長， FFT法的優(yōu)勢越明顯 x(n)與h(n)點數(shù)相差很大時采用FFT運算時，要求長序列全部輸入，短序列補充很多零點，這樣既不經(jīng)濟，運算時間也長。解決的方法是將長序列分段計算，即重疊相加法與重疊保留法第3章 快速傅里葉變換 設h(n)的點數(shù)為M，長序列x(n)可被分成為若干長度為L點的段0)()(nxnxiiLn(i+1)L-1 其他n i=0, 1

37、, 輸入序列表示 0)()(iinxnx 2. 重疊相加法重疊相加法x(n)和h(n)的線性卷積等于00( )( )( )( )( )( )iiiiy nx nh nx nh ny n第3章 快速傅里葉變換 計算N點FFT， H(k)=DFTh(n) （ N=2mL+M-1 ）計算N點FFT，Xi(k)=DFTxi(n) （ N=2mL+M-1 ）相乘，Yi(k)=Xi(k)H(k)計算N點IFFT，yi(n)=IDFTYi(k) 計算步驟)()(0nynyii將各段yi(n)（包括重疊部分相加 xi(n)與yi(n)序列長度不同, 導致相鄰兩段輸出有若干點重疊，應該將重疊部分相加后再和不重疊的部分共同組成輸出y(n) 第3章 快速傅里葉變換 h ( n )0N 1M 1x ( n )0L2 L3 LnnnnnL 10 x0( n )N 10 x1( n )L2 L 1L N 13 L 10 x2( n )2 L2 L N 1 重疊相加法卷積圖示 h ( n )0N 1M 1x ( n )0L2 L3 LnnnnnL 10 x0( n )N 10 x1( n )L2 L 1L