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

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

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

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

4、W周期性 )()(NknNkNnNnkNWWW可約性 2jmnknknmkmNNmNWeW/2(/2)1,NkNkNNNWWW 其它第3章 快速傅里葉變換 3.3 按時(shí)間抽取按時(shí)間抽取DIT的基的基 -2 FFT算法算法 設(shè)序列x(n)長(zhǎng)度為N，且滿足N=2M，M為正整數(shù)。按n的奇偶把x(n)分解為兩個(gè)N/2點(diǎn)的子序列： 12, 1 , 0)() 12()()2(21Nrrxrxrxrx FFT分為兩大類: 按時(shí)間抽取法(Decimation in Time) 和按頻率抽取法(Decimation in Frequency) ,本節(jié)先介紹第一種算法3.3.1 算法原理算法原理 一個(gè)N點(diǎ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點(diǎn)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化簡(jiǎn)1221/20( )NNrkNrx r W1( )X k2( )Xk22NjkNNeW12()( )( )0,1,/2 12kNkNX kX kW XkN得到第3章 快速傅里葉變換 上式將N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)的DFT運(yùn)算，運(yùn)算過(guò)程如下圖示X2(k)X1(k)kNW1X1(k)kNWX2(k)X1(k)kNWX2(k)時(shí)間抽取法蝶形運(yùn)算流圖分解后運(yùn)算工作量節(jié)省了近一半12120,1,120,1,12( )( )( )( )( )2kNkNX kX kW XkNX kX kW XkNkNk 將X(k)表達(dá)式為前后兩部分,重寫如下第3章

8、快速傅里葉變換 N點(diǎn)DFT的一次時(shí)域抽取分解過(guò)程見(jiàn)下圖N=8） 第3章 快速傅里葉變換 兩個(gè)N/2點(diǎn)DFT的分解N點(diǎn)DFT分解1212( )( )( )( )( )2kNkNX kXkWXkNXkXkWXk12(2 )( )(21)( )xrx rxrx r,0,1,12Nr k X1(k)的分解的分解 由于N=2M仍是偶數(shù)，可以把每個(gè)N/2點(diǎn)子序列再進(jìn)行分解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點(diǎn)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點(diǎn)DFT的第二次時(shí)域抽取分解圖N=8）第3章 快速傅里葉變換 N點(diǎn)DFT的第二次時(shí)域抽取分解圖N=8）DFT4點(diǎn)NX3(0)X3(1)x3(0) x1

10、(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4點(diǎn)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點(diǎn)NX5(0)X5(1)x5(0) x2(0) x(1)x5(1) x2(2) x(5)X2(0)X2(1)DFT4點(diǎn)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) 四個(gè)N/4點(diǎn)DFT的計(jì)算 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運(yùn)算流圖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由于輸入序列在時(shí)域上進(jìn)行奇偶分解，故稱為“按時(shí)間抽取法” N=2M點(diǎn)的FFT共進(jìn)行M

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

13、儲(chǔ)單元 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） 輸入序列的排序?yàn)镹的二進(jìn)制倒位序，輸出序列則為自然順序N8時(shí)的輸入輸出值第3章 快速傅里葉變換 3. 蝶形運(yùn)算兩節(jié)點(diǎn)的“間隔” 對(duì)N=2M點(diǎn)FFT，當(dāng)輸入為倒位序， 輸出為正常順序時(shí)，其第m級(jí)運(yùn)算，每個(gè)蝶形的兩節(jié)點(diǎn)“間隔為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 按時(shí)間抽取的按時(shí)間抽取的FFT算法的其他形式流圖算法的其他形式流圖 對(duì)于任何流圖，只要保持各節(jié)點(diǎn)所連的支路及傳輸系數(shù)不變，則不論節(jié)點(diǎn)位置怎么排列所得流圖總是等效的將左圖x(4)與 x(1) , x(6)與x(3)對(duì)調(diào)第3章 快速傅里葉變換 時(shí)間抽取、 輸入自然順序、 輸出倒位序的FFT流圖特點(diǎn) 數(shù)據(jù)存放的方式不同 取用系數(shù)的順序不同第3章 快速傅里葉變換 3.4 按頻率抽取按頻率抽取DIF的基的基 -2 FFT算法算法 3.4.1 算法原

15、理算法原理10( )( )NnkNnX kx n W將長(zhǎng)度為N=2M的序列x(n)前后對(duì)半分開(kāi), 其N點(diǎ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ù)時(shí)120/2( )2nrNNnNx nx nWx(n)前后兩部分和的N/2點(diǎn)DFT第3章 快速傅里葉變換 k取奇數(shù)時(shí)12(21)0(21)( )2NnrNnNXrx nx nW12, 1 , 0Nr2120/( )2nnrNnNNNx nx nWWx(n)前后兩部分差再乘以WNn后的N/2點(diǎn)DFT12/20( )2(2 )NnrNnNXnrxWx n k取偶數(shù)時(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點(diǎn)DFT. x1(n), x2(n)與x(n)間的關(guān)系也可用下面蝶形運(yùn)算流圖表示式中12( )2( )2( )( )nNNx nx nNx nxx nnWnx/2 11/20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx n WXrx n W得到第3章 快速傅里葉變換 按頻率抽取的N點(diǎ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ù)將每個(gè)N/2點(diǎn)DFT輸出再分解為偶數(shù)組與奇數(shù)組,直到第M次N=2M） 按頻率抽取完整的N點(diǎn)DFT運(yùn)算流圖 (N=8) 第3章 快速傅里葉變換 3.4.2 DIF-FFT與與DIT-FFT的聯(lián)系的聯(lián)系 DIF的基本蝶形與DIT的基本蝶形互為轉(zhuǎn)置DIT蝶形運(yùn)算流圖DIF蝶形運(yùn)算流圖第3章 快速傅里葉變換 兩種FFT運(yùn)算方法等價(jià) DIT-FFTDIF-FFT 第3章 快速傅里葉變換 3.4.3 IDFT的高效算法的高效算法FFT算法同樣可以用于 IDFT，稱為快速傅里葉反變換(IFFT)比較DFT和

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

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

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

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

23、為卷積形式, 從而利用FFT算法, 提高運(yùn)算速度 第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當(dāng)X(zk)可表示成卷積形式第3章 快速傅里葉變換 )()()(22khkgWzXkkk=0, 1, , M

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

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

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

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

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

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

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

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

32、) 頻譜 3. 由截?cái)嘈?yīng)引起的頻譜泄漏與譜間干擾由截?cái)嘈?yīng)引起的頻譜泄漏與譜間干擾實(shí)際中的序列x(n)有可能是無(wú)限長(zhǎng)的，為進(jìn)行DFT運(yùn)算，x(n)需要進(jìn)行加窗處理變成有限長(zhǎng)序列，截?cái)嗪笮蛄械念l譜與原序列頻譜必然有差別, 主要表現(xiàn)為泄漏與譜間干擾矩形窗函數(shù)的幅度譜 加矩形窗后的頻譜 第3章 快速傅里葉變換 泄漏：截?cái)嗪蟮男蛄胁辉偈菃我蛔V線，而是向附近展寬。泄漏使頻譜變模糊，使譜分辨率降低譜間干擾：主譜線兩邊形成很多旁瓣，將引起不同頻率分量間的干擾。特別是強(qiáng)信號(hào)譜的旁瓣可能湮沒(méi)弱信號(hào)的主譜線加矩形窗后的頻譜 cos(n/4) 頻譜 第3章 快速傅里葉變換 加矩形窗后的頻譜 減小兩種影響的措施：c

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

34、為頻譜圖。從圖中可以知道信號(hào)存在哪些頻率分量第3章 快速傅里葉變換 實(shí)際也常用功率譜表示，主要用于分析帶有噪聲干擾的信號(hào)NkXkPSD2| )(|)( 功率譜 頻率軸幾種定標(biāo)方式的對(duì)應(yīng)關(guān)系oooooN / 4N / 2k / (rad / s)f / Hzf / rad0.5fs / 2s / 2第3章 快速傅里葉變換 例例 用頻譜分析下列時(shí)域信號(hào)的組成用頻譜分析下列時(shí)域信號(hào)的組成( fs=32 Hz )對(duì)序列作32點(diǎn)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的其它應(yīng)用的其它應(yīng)用 3.8.1 線性卷積的線性卷積的FFT算法算法快速卷積快速卷積 1. FFT的快速卷積法利用圓周卷積的的快速卷積法利用圓周卷積的FFT計(jì)算線性卷積）計(jì)算線性卷積）補(bǔ)L N個(gè)零點(diǎn)L點(diǎn)DFT補(bǔ)L M個(gè)零點(diǎn)L點(diǎn)DFTL點(diǎn)IDFTy(n)h(n)x(n) FFT計(jì)算y(n)的步驟 求H(k)=DFTh(n) 求X(k)=DFTx(n) 計(jì)算Y(k)=X(k)H(k); 求y(n)=IDFTY(k) 第3章 快速傅里葉變換 運(yùn)算量的比較直接線性卷積和FFT法計(jì)算線性卷積） x

36、(n)與h(n)點(diǎn)數(shù)差不多時(shí), 有如下結(jié)果(KM為兩種卷積運(yùn)算量比值)M=L8163264128256512102420484096Km0.572 0.9411.62.785.928.821629.2453.999.9當(dāng)M=L且M超過(guò)32以后，M越長(zhǎng)， FFT法的優(yōu)勢(shì)越明顯 x(n)與h(n)點(diǎn)數(shù)相差很大時(shí)采用FFT運(yùn)算時(shí)，要求長(zhǎng)序列全部輸入，短序列補(bǔ)充很多零點(diǎn)，這樣既不經(jīng)濟(jì)，運(yùn)算時(shí)間也長(zhǎng)。解決的方法是將長(zhǎng)序列分段計(jì)算，即重疊相加法與重疊保留法第3章 快速傅里葉變換 設(shè)h(n)的點(diǎn)數(shù)為M，長(zhǎng)序列x(n)可被分成為若干長(zhǎng)度為L(zhǎng)點(diǎn)的段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章 快速傅里葉變換 計(jì)算N點(diǎn)FFT， H(k)=DFTh(n) （ N=2mL+M-1 ）計(jì)算N點(diǎn)FFT，Xi(k)=DFTxi(n) （ N=2mL+M-1 ）相乘，Yi(k)=Xi(k)H(k)計(jì)算N點(diǎn)IFFT，yi(n)=IDFTYi(k) 計(jì)算步驟)()(0nynyii將各段yi(n)（包括重疊部分相加 xi(n)與yi(n)序列長(zhǎng)度不同, 導(dǎo)致相鄰兩段輸出有若干點(diǎn)重疊，應(yīng)該將重疊部分相加后再和不重疊的部分共同組成輸出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