現(xiàn)代時域測量第三章

1、fuping第三章 快速變換與卷積o 引言引言o 快速傅立葉變換o IDFT算法o 實輸入序列的FFT算法o N為組合數(shù)的FFT算法o FFT用于時域測量中應注意的問題o FFT在頻譜分析中的應用o FFT卷積o 其他變換fuping引言o變換的目的為了簡化n 對數(shù)變換：o乘、除加、減n 傅立葉、拉普拉斯變換、Z變換：o卷積乘fuping引言o分析離散系統(tǒng)Z變換、DFTn 理論分析o Z變換n 實際運算o DFT的各種快速算法fuping引言oDFTn 分析有限長序列最有力工具之一n 理論上有重要意義n 是各種快速算法的基礎(chǔ)fuping引言o 1807年傅立葉提出“任何周期信號都可用正弦函數(shù)級

2、數(shù)表示”傅立葉變換o 1965年圖基(J.W.Tuky)和庫利(T.W.Cooly) 在計算數(shù)學上發(fā)表了著名的“機器計算傅立葉級數(shù)的一種算法” 論文后，桑德（G.Sand） 圖基等快速算法相繼出現(xiàn)，經(jīng)人們改進，形成FFT ，使DFT的運算效率提高個數(shù)量級傅立葉變換具有實用意義傅立葉變換具有實用意義o 1976年維諾格蘭（Winograd）算法乘法次數(shù)為FFT的1/3o 1984年，法國的杜哈梅爾（P.Dohamel）和霍爾曼（H.Hollmann）提出的分裂基快速算法，使運算效率進一步提高 fuping引言o DFT用完備的正交函數(shù)系（三角函數(shù)）的線性組合逼近待分析變換的函數(shù)o 其他完備正交函

3、數(shù)系其他變換：沃爾什變換、數(shù)論變換等o 基2的FFT算法，有明確的物理意義，測量中最先得到應用o 卷積計算問題，如何利用快速變換計算卷積o 要求：1、掌握各種快速算法的原理 2、如何利用這些變換處理測量中的問題fuping第三章 快速變換與卷積o 引言o 快速傅立葉變換快速傅立葉變換o IDFT算法o 實輸入序列的FFT算法o N為組合數(shù)的FFT算法o FFT用于時域測量中應注意的問題o FFT在頻譜分析中的應用o FFT卷積o 其他變換fuping離散傅里葉變換DFT10:( )( )0,1,1NknNnDFTX kx n WkN101:( )( )0,1,1NknNkIDFTx nX k

4、WnNN2jNNWenx(n)、WN復數(shù)n每個X(k)N次復數(shù)X，N-1次復數(shù)+ nN個X(k) N2次復數(shù)X，N（N-1）次復數(shù)+ fupingDFT的矩陣表示法fuping離散傅里葉變換DFTnN=10 100次復數(shù)XnN=1024 1048576次復數(shù)Xn實時處理 計算速度要求高 n問題 如何減少計算量？fupingknNWo 可以利用 的特性簡化計算，減少計算量n 周期性：n 對稱性：如()k N nknNNWW()*()k N nknknNNNWWW2jNNWefupingknNWo 利用 的特性簡化計算快速算法FFTn 時間抽取算法n 頻率抽取算法fuping時間抽取算法o 原始算

5、法（庫利圖基提出）按在時域上輸入序列次序的奇偶來抽?。ǚ纸猓r間抽?。―ecimation-In-Time，簡稱DIT） p 基本原理p DFT的計算量正比于N2，N小，計算量也就小 p 將大點數(shù)DFT分解成若干小點數(shù)DFT組合，減少運算p 按時間序列奇偶抽取按時間序列奇偶抽取fuping時間抽取算法10:( )( )0,1,1NknNnDFTX kx n WkN/2 12(21)0( ) (2 )(21)0,1,1NnknkNNnX kxn WxnWkN通常取N=2M，將x x(2n) 和x(2n+1) 2jNNWefuping時間抽取算法/2 12(21)0( ) (2 )(21)0,1,

6、1NnknkNNnX kxn WxnWkN2/2NNWW/2 1/2 1/2/200( )(2 )(21)( )( )NNnkknkkNNNeNonnX kxn WWxnWXkWXkXe(k) Xo(k) 利用fuping時間抽取算法/2 1/2 1/2/200( )(2 )(21)( )( )NNnkknkkNNNeNonnX kxn WWxnWXkWXk/2k NkNNWW ( )( )( )(/2)( )( )0,1,/2 1keNokeNoX kXkWXkX kNXkWXkkN只有N/2個點Xe(k) Xo(k) fuping時間抽取算法計算量( )( )( )(/2)( )( )0,

7、1,/2 1keNokeNoX kXkWXkX kNXkWXkkN乘法：N2/4+ N2/4+N/2=N(N+1)/2次加法：(N/2)(N/2-1)+ (N/2)(N/2-1)+N/2+N/2=N2/2次進一步分解將進一步減少運算次數(shù)進一步分解將進一步減少運算次數(shù)fupingp 蝶形運算圖fupingp 蝶形運算圖kNW( )( )keNoX kWXk( )( )keNoX kWXk( )eX k( )oXkfuping以8點FFT為例fupingfupingfupingx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X

8、(7)共log2N級運算，每一級有N/2個蝶形運算，需N/2次乘法運算， N次加法運算因此，共需（N/2）log2N次乘，Nlog2N次加計算量fupingo 特點與規(guī)律n 蝶形運算o共有M=log2N級運算o每次N/2個蝶形運算o不論是復乘還是復加，計算量都與Nlog2N成正比，而直接運算時則與N2成正比o例N=2048，N2=4194304，(N/2)log2N=11264，N2/(N/2)log2N=392.4fupingo 特點與規(guī)律n 原位運算o 當數(shù)據(jù)輸入到存儲器中以后，每一級運算的結(jié)果仍然儲存在同一組存儲器中，直到最后輸出，中間無需其它存儲器，這叫原位計算 o 這種原位運算結(jié)構(gòu)可

9、節(jié)省存儲單元，降低設(shè)備成本，還可節(jié)省找地址的時間 fupingo 特點與規(guī)律n 正序輸出，倒序輸入（碼位倒序）自然順序二進碼表示碼位倒置碼位倒置順序0000000010011004201001023011110641000011510110156110011371111117fupingo 特點與規(guī)律n 蝶形類型隨迭代次數(shù)成倍增加 o 觀察8點FFT的三次迭代運算 o 第一級迭代，只有一種類型的蝶形運算系數(shù)W08 o 第二級迭代，有二種類型的蝶形運算系數(shù)W08 、W28，參加運算的兩個數(shù)據(jù)點間隔為2。 o 第三級迭代，有四類蝶形運算系數(shù)W08 、 W18 、 W28 、 W38 ，參加運算的兩

10、個數(shù)據(jù)點間隔為4。 o 所以，每次迭代的蝶形類型比上一次蝶代增加一倍，數(shù)據(jù)點間隔也增大一倍。fuping頻率抽取算法o 桑德提出，稱為桑德圖基算法按在頻域上輸入序列次序的奇偶來抽取（分解）頻率抽取(Decimation-In-Frequency,簡稱DIF）p 基本原理p DFT的計算量正比于N2，N小，計算量也就小 p 將大點數(shù)DFT分解成若干小點數(shù)DFT組合，減少運算p 時間序列對半分時間序列對半分fuping頻率抽取算法通常取N=2M，將x 按前后對半分開 式中 fuping頻率抽取算法將X ( k )分解成偶數(shù)組與奇數(shù)組，當k取偶數(shù)時， 當k取奇數(shù)時 fuping頻率抽取算法令 則 f

11、uping頻率抽取算法12( )( )(/2)( ) ( )(/2)0,1,/2 1nNx nx nx nNx nx nx nNWnNnNW( )x n(/2)x nN( )(/2)x nx nN ( )(/2)nNx nx nNWp 蝶形運算圖fupingp 信號流圖蝶形運算圖x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)o 特點與規(guī)律n 蝶形運算o共有M=log2N級運算o每次N/2個蝶形運算n 正序輸入，倒序輸出o 倒序：碼位倒序n 原位運算o 節(jié)省存儲單元n 蝶形類型隨迭代次數(shù)成倍減少fuping第三章

12、快速變換與卷積o 引言o 快速傅立葉變換o IDFT算法算法o 實輸入序列的FFT算法o N為組合數(shù)的FFT算法o FFT用于時域測量中應注意的問題o FFT在頻譜分析中的應用o FFT卷積o 其他變換fupingIDFT算法o 與DFT相比多系數(shù)1/N，WNnk WN-nk可以將分析DFT算法用于IDFT101:( )( )( )0,1,1NknNkIDFTx nIDFT X kX k WnNN10:( )( )0,1,1NknNnDFTX kx n WkNfupingIDFT算法o 只要把DFT運算中的每一個系數(shù)WNnk 改為WN-nk ，再乘以常數(shù)1/N，則以上所討論的時間抽取或頻率抽取

13、的FFT運算均可直接進行IDFT運算，當然，蝶形中的系數(shù)WNnk 應改為WN-nk101:( )( )( )0,1,1NknNkIDFTx nIDFT X kX k WnNN10:( )( )0,1,1NknNnDFTX kx n WkNfupingIDFT算法o 也可以直接利用DFT算法n X(k)取共軛，即虛部乘-1n 調(diào)用FFT計算n 再取共軛n 乘以1/N，得x(n)101:( )( )( )0,1,1NknNkIDFTx nIDFT X kX k WnNN1*011( )( )( )NnkNkx nXk WDFT XkNNfuping第三章 快速變換與卷積o 引言o 快速傅立葉變換o

14、 IDFT算法o 實輸入序列的實輸入序列的FFT算法算法o N為組合數(shù)的FFT算法o FFT用于時域測量中應注意的問題o FFT在頻譜分析中的應用o FFT卷積o 其他變換fuping實輸入序列FFTo FFT均為復序列，o 實際測量采樣數(shù)據(jù)均為實數(shù)，o 利用FFT，省一半內(nèi)存，速度提高一倍o 兩種方法：n 同時計算兩個實序列的FFT算法n 用N點變換計算2N個樣本點的變換fuping實輸入序列FFTo 同時計算兩個實序列的FFT算法設(shè)x1(n),x2(n)是彼此獨立的兩個N點實序列,構(gòu)造復序列 x(n) = x1(n) + jx2(n) , 則 X(k)=X1(k)+jX2(k) fupin

15、g實輸入序列FFT因為實序列的FFT的實部是偶函數(shù)，虛部是奇函數(shù)即：X1(k) = X1e(k) + jX1o(k) , X2(k) = X2e(k) + jX2o(k) X(k) =X1e(k) + jX1o(k) + jX2e(k) + jX2o(k) = X1e(k) - X2o(k) + jX2e(k) + jX1o(k) 另外： X(k) =Xr(k) + jXi(k) =1/2Xr(k)+Xr(N-k)+1/2Xr(k)-Xr(N-k) +j/2Xi(k)+Xi(N-k)+j/2Xi(k)-Xi(N-k)所以： X1(k) = X1e(k) +jX1o(k) = 1/2Xr(k)+

16、Xr(N-k)+ j/2Xi(k)-Xi(N-k) X2(k) = X2e(k) +jX2o(k) = 1/2Xi(k)+Xi(N-k) - j/2Xr(k)-Xr(N-k)fuping實輸入序列FFTo 用N點變換計算2N個樣本點的變換設(shè)x(n)是2N點的實序列將x(n)分為偶數(shù)組x1(n)和奇數(shù)組x2(n) x1(n)=x(2n) n=0,1,N-1 x2(n)=x(2n+1) n=0,1,N-1 然后將x1(n)及x2(n)組成一個復序列： y(n) =x1(n)+jx2(n) 通過N點FFT運算可得到 Y(k)=X1(k)+jX2(k) = Yr(k)+j Yi(k)fuping實輸入

17、序列FFT根據(jù)前面的討論，得到 21112(21)22200011/122120012( )( )(2 )(21)( )( )( )( )( )(cossin)( )( )()( )()( ) cos2222NNNnknknkNNNnnnNNnkknkj k NNNNnniirrrX kx n Wxn WxnWx n WWx n WX keXkkkX kjXkNNY kY NkY kY NkY kkN()sin22( )()( )()( )() sincos222222riiiirrY NkkNY kY NkY kY NkY kY NkkkjNNfuping實輸入序列FFT122122/121

18、2()( )( )( )( )( )( )( ) (cossin)( )( )()( )()( )() cossin222222( )()( )() sin2222k NNkNj k NiirrrriiiiX kNX kWX kX kWX kX keX kkkX kjX kNNY kY N kY kY N kY kY N kkkNNY kY N kY kY N kYkjN( )()cos22rrkY N kkN(k=0,1,N-1)fuping第三章 快速變換與卷積o 引言o 快速傅立葉變換o IDFT算法o 實輸入序列的FFT算法o N為組合數(shù)的為組合數(shù)的FFT算法算法o FFT用于時域測量

19、中應注意的問題o FFT在頻譜分析中的應用o FFT卷積o 其他變換fupingN為組合數(shù)的FFT算法o基2的FFT算法，即N=2M，使用最多，優(yōu)點是程序簡單，效率高，使用方便。實際應用時，序列長度N一般人為確定，可取N=2M。 o如N不能人為確定，N不是2M，處理方法有兩種: n補零： 將x(n)補零，使N=2M。例如N=30，補上x(30)=x(31)=0兩點，使N=32=25。 有限長度序列補零后并不影響其頻譜X(ej)，只是頻譜的采樣點數(shù)增加了，當然，采樣點的位置也有相應的變化。上例中由30點增加到32點，采樣點則由2/30的整數(shù)倍變?yōu)?/32的整數(shù)倍，對應的絕對頻率也由fs/30的整

20、數(shù)倍變?yōu)閒s/32的整數(shù)倍。在許多場合這種處理是可接受的，但不適應對某些特殊頻率點有特別要求的場合。 n采用任意數(shù)基數(shù)的DFT算法 如要求準確的N點DFT值，可采用任意數(shù)為基數(shù)的DFT算法，計算效率低于以2為基數(shù)FFT算法。 fuping第三章 快速變換與卷積o 引言o 快速傅立葉變換o IDFT算法o 實輸入序列的FFT算法o N為組合數(shù)的FFT算法o FFT用于時域測量中應注意的問題用于時域測量中應注意的問題o FFT在頻譜分析中的應用o FFT卷積o 其他變換fupingFFT用于時域測量應注意的問題o 采用DFT或FFT，作了如下處理n用離散采樣信號的傅立葉變換來代替連續(xù)信號的頻譜n用

21、有限長序列來代替無限長離散采樣信號o 所以DFT或FFT得到的是傅立葉變換的一種逼近形式o 帶來的問題：n時域取樣頻譜混疊取樣定理n時域截斷頻譜泄露（截斷效應）時域加窗吉布斯現(xiàn)象加權(quán)n頻域取樣柵欄效應頻率間隔=時域長度的倒數(shù)n頻域截斷柵欄效應fupingFFT用于時域測量應注意的問題o 頻譜混疊n 對連續(xù)信號x(t)進行數(shù)字處理前，要進行采樣，采樣序列的頻譜是連續(xù)信號頻譜的周期延拓，周期為fs，如采樣率過低，fs2fh，則導致頻譜混疊，使一個周期內(nèi)的譜對原信號譜產(chǎn)生失真，無法恢復原信號。n 取樣定理fupingFFT用于時域測量應注意的問題o 頻譜泄露n序列x(n)，總要截斷，長為N點，相當于

22、乘以矩形窗w(n)=RN(n)。n矩形窗函數(shù)，頻譜是抽樣函數(shù)，有主瓣，有許多副瓣，窗口越大，主瓣越窄，當窗口趨于無窮大時，就是一個沖擊。n時域乘積頻域卷積，加窗后頻譜是原信號頻譜與矩形窗函數(shù)頻譜（抽樣函數(shù)）的卷積，結(jié)果使頻譜延伸到了主瓣以外，延伸到無窮。當窗口無窮大時，與沖擊的卷積就是其本身，無畸變。n如信號ejonT，是單線譜，加窗后，線譜與抽樣函數(shù)進行卷積，原來在0處的一根譜線變成了以0為中心的，形狀為抽樣函數(shù)的譜線序列，從能量守恒看，相當于x(ejT)的頻率成份從0處“泄漏”到其它頻率處去了。 n由于頻譜“泄漏”后的互相串漏，泄漏還會引起頻譜的混疊。fupingFFT用于時域測量應注意的

23、問題o 柵欄效應n N點DFT是在頻率區(qū)間0，2上對信號頻譜進行N點等間隔采樣，得到的是若干個離散的頻譜點X(k)，且它們限制在基頻的整數(shù)倍上，這就好像在柵欄的一邊通過縫隙看另一邊的景象一樣，只能在離散點處看到真實的景象，其余部分頻譜成分被遮擋，所以稱之為柵欄效應。n 減小柵欄效應方法：尾部補零，使譜線變密，增加頻域采樣點數(shù)，原來漏掉的某些頻譜部分就可能被檢測出來。 fupingo 測量中常用信號分析n 帶限周期信號頻帶有限周期正弦波。頻譜為有限條譜線構(gòu)成o 可滿足采樣定理，不混疊o 時域截斷長度=信號周期：不產(chǎn)生泄漏，無柵欄效應f=n/T0時，Sa(T0f)=0FFT用于時域測量應注意的問題

24、fupingo 測量中常用信號分析n 脈沖信號o 占空比小o 有效樣本少混疊FFT用于時域測量應注意的問題fupingo 測量中常用信號分析n 時限信號持續(xù)時間有限o 頻譜無限寬混疊o 頻譜連續(xù) 柵欄效應FFT用于時域測量應注意的問題fupingo 測量中常用信號分析n 帶限非周期信號頻帶有限持續(xù)時間無限非周期o 時域無限，必須截斷n 頻譜泄漏頻譜擴展混疊o 非周期信號，頻譜連續(xù)n 柵欄效應FFT用于時域測量應注意的問題fupingo 測量中常用信號分析n 無限帶寬周期信號頻帶無限類似時限信號周期頻譜離散方波。o 混疊o 時域截斷長度=信號周期：不產(chǎn)生泄漏，無柵欄效應FFT用于時域測量應注意的

25、問題fupingFFT用于時域測量應注意的問題o 測量中常用信號分析頻譜混疊頻譜泄漏 柵欄效應帶限周期信號可無可無可無時限信號有無有帶限非周期信號有有有無限帶寬周期信號有可無可無fuping第三章 快速變換與卷積o 引言o 快速傅立葉變換o IDFT算法o 實輸入序列的FFT算法o FFT用于時域測量中應注意的問題o FFT在頻譜分析中的應用在頻譜分析中的應用o FFT卷積o 其他變換fuping第三章 快速變換與卷積FFT用于頻譜分析o 脈沖激勵信號的頻譜分析n 周期為T0的脈沖激勵信號n 當T0=MT時，不產(chǎn)生頻譜泄漏，頻率分辨力下降n 當T0=T時，不產(chǎn)生柵欄效應n 不產(chǎn)生頻譜混疊的采樣

26、點數(shù)NTT021/hfNFTFfuping第三章 快速變換與卷積FFT用于頻譜分析o 用FFT分析階躍波形n必須時域截斷，從而引起頻譜泄漏nGans提出窗口法o 將包含豐富頻譜分量的前沿部分截斷，窗口長度為TW，并進行周期延拓o 將偶數(shù)波形倒轉(zhuǎn)方向，上移o 用FFT對此周期信號進行分析，周期為2 TW，即為階躍波形的頻譜TWTWfuping第三章 快速變換與卷積o 引言o 快速傅立葉變換o IDFT算法o 實輸入序列的FFT算法o FFT用于時域測量中應注意的問題o FFT在頻譜分析中的應用o FFT卷積卷積o 其他變換fupingFFT卷積o 周期卷積o 圓周卷積（循環(huán)卷積或圓卷積）o 線性

27、卷積o 各卷積之間的關(guān)系fuping周期卷積( )( )x nh n兩個周期序列：、，周期均為N1100( )( ) ()( ) ()NNmmy nx m h nmh m x nm( ),01( ),01( )( )0,0,x nnNh nnNx nh n當，時其它其它( )()( )()rrx nx nrNh nh nrNfuping周期卷積1100( )( ) ()( ) ()NNmmy nx m h nmh m x nmo 計算步驟n 折疊n 位移n 相乘n 相加fuping周期卷積o 周期卷積可看成周期為N的信號激勵長度為N的單位沖激相應的系統(tǒng)的輸出( )( )( )Y kX kH k

28、( ) ( )( ) ( )( ) ( )Y kDFS y kX kDFS x kH kDFS h k傅立葉級數(shù)：DFT表示DFS主值區(qū)間的序列值FFT DFT DFS 周期卷積 X(k)=FFTx(n)，H(k)=FFTh(n) Y(k)=X(k) H(k) y(n)=IFFTY(k)1. y(n)周期延拓( )y nfuping圓周卷積（循環(huán)卷積或圓卷積）11001100( )( ) ()( )( ) ()( )( ) ()( )( ) ()( )NNNNNmmNNNNNmmy nx m h nm Rnx m h nmRnh m x nm Rnh m x nmRn( )( )x nh n、

29、可以看作周期序列 的周期卷積，再取主值序列計算方法： X(k)=FFTx(n)，H(k)=FFTh(n) Y(k)=X(k) H(k)1. y(n)=IFFTY(k)fuping線性卷積( )( ) ()( ) ()( )( )mmy nx m h nmh m x nmx nh n應用最多，對有限長序列：x(n):N，h(n):M01( ):101mNy nLNMnmMo 不能直接用FFTo x(n)補充M個零點o h(n)補充N個零點o 按L=N+M-1進行周期延拓o 利用圓周卷積計算a.計算X(k)=FFTx(n) b.求H(k)=FFTh(n) c.求Y(k)=H(k)Y(k) k=0L

30、-1 d.求y(n)=IFFTY(k) n=0L-1 fuping線性卷積o 上述結(jié)論適用于x(n),h(n)兩序列長度比較接近或相等的情況,如果x(n),h(n)長度相差較多,例如,h(n)為某濾波器的單位脈沖響應,長度有限,用來處理一個很長的輸入信號x(n)（如語音信號等），或者處理一個連續(xù)不斷的信號，按上述方法,h(n)要補許多零再進行計算,計算量有很大的浪費，或者根本不能實現(xiàn)。o 為了保持快速卷積法的優(yōu)越性,可將x(n)分為許多段后處理,每小段的長與h(n)接近,其處理方法有兩種：o重疊相加法o重疊保存法 fuping線性卷積o 重疊相加法由分段卷積的各段相加構(gòu)成總的卷積輸出 o 計算步驟：計算步驟： a. 事先準備好濾波器參數(shù)H(k)=DFTh(n)，N點 b.用N點FFT計算Xi(k)=DFTxi(n) c.Yi(k)=Xi(k)H(k) d.用N