小波分析快速傅里葉變換

1、快速傅里葉變換 快速傅里葉變換(FFT)并不是一種新的變換，而是離散博里葉變換(DFT)的一種快速算法。因此，為了很好地理解和掌握快速傅里葉變換，必須對離散傅里葉變換有充分的理解與掌握 。 由于DFT的計算量太大即使采用計算機也很難對問題進行實時處理，所以并沒有得到真正的運用。直到1965年庫利(J. W. Coo1ey)和圖基(J. W. Tukey)在計算數(shù)學(xué)上發(fā)表了著名的“機器計算傅里葉級數(shù)的一種算法”的文章提出了DFT的一種快速算法后來又有桑德(G. Sande)和圖基的快速算法相繼出現(xiàn)，情況才發(fā)生了根本的改變。經(jīng)過人們對算法的改進，發(fā)展和完善了一套高速有效的運算方法，使DFT的計算大

2、大簡化，運算時間般可縮短一、二個數(shù)量級，從而使DFT的運算在實際中真正得到了廣泛的加用。 1 直接計算DFT的問題及改進途徑( )x n對于N點有現(xiàn)長序列10( )( )( )NnkNnX kDFT x nx n W0,1,1kN101( )( )( )NnkNkx nIDFT X kX k WN0,1,1nN二者的差別只在于 的指數(shù)符號不同，以及差一個常數(shù)乘因子 ,因而我們只討論DFT正變換的運算量。IDFT的運算量是完全相同的。 NW1NDFT的運算量分析 一次復(fù)數(shù)乘法需用四次實數(shù)乘法和二次實數(shù)加法： 一次復(fù)數(shù)加法則需兩次實數(shù)加法。()()()()ajb cjdacbdj adbc()()

3、()()ajbcjdacj bd( )X k10( )NnkNnx n WN1N 4N22(1)NNN( )X k2N(1)N N 24N2(21)NN 一個個復(fù)數(shù)乘法復(fù)數(shù)加法實數(shù)乘法實數(shù)加法改進途徑改進途徑*nknkNNWW()()nkN n kn N kNNNWWWnkmnkNmNWW/nknk mNN mWW01NW/21NNW (/2)kNkNNWW 2jnknkNNWe利用 的特性 (1)對稱性(2)周期性 (3) 可約性 (4) 特殊點 FFT算法的基本思想 使DFT運算中有些項可以合并； 可以將長序列的DFT分解為短序列的DFT FFT算法分類: 時間抽選法 DIT: Decim

4、ation-In-Time 頻率抽選法 DIF: Decimation-In-Frequency2 按時間抽選(DIT)的基-2 FFT算法(庫利圖基算法) 算法原理 先沒序列點數(shù)為 , 為整數(shù)。如果不滿足這個條件，可以人為地加上若干零值點，使之達到這一要求。這種 為2的整數(shù)冪的FFT也稱基-2 FFT。 2LN LN2LN ( )x n(0,1,1)nN將 的序列 先按n的奇偶分成以下兩組： 12(2 )( ),0,1,1(21)( )2xrx rNrxrx r111000( )( )( )( )( )NNNnknknkNNNnnnX kDFT x nx n Wx n Wx n Wn為偶數(shù)

5、n為奇數(shù) 11222(21)00(2 )(21)NNrkrkNNrrxr WxrW1122221200( )( )NNrkrkkNNNrrx rWWx rW 式中 和 分別是 和 的N/2點DFT利用系數(shù) 的可約性： nkNW22222/2jNjNNNWeeW11221/22/200( )( )( )NNrkkrkNNNrrX kx r WWx r W12( )( )kNX kW Xk1( )X k2( )Xk1( )x r2( )x r112211/2/200( )( )(2 )NNrkrkNNrrX kx r Wxr W112222/2/200( )( )(21)NNrkrkNNrrXkx

6、 r WxrW可看出，一個N點DFT已分解成兩個N2點的DFT，它們又組合成一個N點DFT。 然而 和 以及 和 都是N/2點的序列：1( )X k2( )Xk1( )x r2( )x r,0,1,12Nr k ( )X k 卻有N點而用上式計算得到的只是 的前一半項數(shù)的結(jié)果，要用 和 來表達 全部的值，還必須應(yīng)用系數(shù)的周期性，即： ( )X k1( )X k2( )Xk( )X k()2/2/2Nr krkNNWW1122()211/21/2100()( )( )( )2NNNr krkNNrrNX kx r Wx r WX k1122()222/22/2200()( )( )( )2NNN

7、r krkNNrrNXkx r Wx r WXk將將 表達為前后兩部分表達為前后兩部分 再考慮到 的以下性質(zhì)： nkNW()/22NkNkkNNNNWWWW ( )X k前半部分 0,1,12Nk 12( )( )( )kNX kX kW Xk后半部分 212()()()222NkNNNNX kX kWXk12( )( )kNX kW Xk0,1,12Nk 可以用蝶形信號流圖符號表示，當支路上沒有標出系數(shù)時，則該支路的傳輸系數(shù)為1。 2LN 3L 計算量分析：復(fù)數(shù)乘法復(fù)數(shù)加法一個N2點DFT 兩個N2點DFT 22N(1)22NN22N(1)2NN一個蝶形運算 122NN222NN2(1)22

8、NNNNN點DFT 總計 2N(1)N N N2個蝶形運算 計算量減少一半 可以進一步把每一個N2點子序列再按其奇偶部分分解為兩個N4點的子序列 1( )x r2LN N2仍是偶數(shù) 1314(2 )( ),0,1,1(21)( )4xlx lNlxlx l34( ),( )x lx l分解為奇偶兩個序列11442(21)11/21/200( )(2 )(21)NNlklkNNllX kxl WxlW1144223/2/24/200( )( )NNlklkkNNNllx lWWx lW222224/2/4jjNNNNWeeW由于114413/4/24/400( )( )( )NNlkklkNNN

9、llX kx l WWx l W3/24( )( )kNXkWXk0,1,14Nk 其中， 與 分別是 與 的N4點的DFT： 3( )Xk4( )Xk3( )x l4( )x l114433/41/400( )( )(2 )NNlklkNNllXkx l Wxl W114444/41/400( )( )(21)NNlklkNNllXkx l WxlW同樣可以計算 在N/4到N/2-1的值3( )Xk0,1,14Nk ()4/4/4Nl klkNNWW()/44/2/2/2/2NkNkkNNNNWWWW 由于1144()433/43/4300()( )( )( )4NNNl klkNNllNX

10、kx l Wx l WXk1144()444/41/4400()( )( )( )4NNNl klkNNllNXkx l Wx l WXk0,1,14Nk ()413/24()()()444NkNNNNX kXkWXk因此：3/24( )( )kNXkWXk2526(2 )( ),0,1,1(21)( )4xlx lNlxlx l25/26( )( )( )kNXkXkWXk25/26()( )( )4kNNXkXkWXk0,1,14Nk 114455/42/400( )( )(2 )NNlklkNNllXkx l Wxl W114466/42/400( )( )(21)NNlklkNNllX

11、kx l WxlW其中， 與 分別是 與 的N4點的DFT： 5( )Xk6( )Xk5( )x l6( )x lN=8的DFT可以分解為4個 點DFT:24N2/2kkNNWWrNW由于： 將系數(shù)統(tǒng)一成 形式 計算量又減少一半計算量又減少一半討論 按偶數(shù)與奇數(shù)的分解過程中序列標號的變化。對于一個N8點的DFT的例子，輸入序列按偶數(shù)點與奇數(shù)點第一次分解為兩個N2點序列： 再經(jīng)過一起分解，剩下的是2點DFT，對于此例N8，就是4個 點DFT，其輸出為 24N3( )Xk4( )Xk5( )Xk6( )Xk0,1k 可以方便地計算出來，例如：0033232(0)(0)(1)(0)(4)(0)(4)

12、XxW xxW xxx110332322(1)(0)(1)(0)(4)(0)(4)(0)(4)XxW xxW xxW xxx0044242(0)(0)(1)(2)(6)(2)(6)XxW xxW xxx110442422(1)(0)(1)(2)(6)(2)(6)(2)(6)XxW xxW xxW xxx0055252(0)(0)(1)(1)(5)(1)(5)XxW xxW xxx110552522(1)(0)(1)(1)(5)(1)(5)(1)(5)XxW xxW xxW xxx0066262(0)(0)(1)(3)(7)(3)(7)XxW xxW xxx110662622(1)(0)(1)(

13、3)(7)(3)(7)(3)(7)XxW xxW xxW xxx偶序列 奇序列1(2 )( )xrx r2(21)( )xrx rr 0，1，2，3 0，1，2，3 n0，2，4，6 1，3，5，7 偶序列奇序列 偶序列奇序列 13(2 )( )xlx l14(21)( )xlx l25(2 )( )xlx l26(21)( )xlx llrn0，10，1 0，1 0，1 0，21，3 0，2 1，3 0，42，6 1，5 3，7 的排列規(guī)律，將 寫成二進制，將二進制的數(shù)碼翻轉(zhuǎn)，即得到正確的輸入序列 0,1,1nN( )x n這種方法的每一步分解那是按輸入序列在時間上的次序是屬于偶數(shù)還是屬于奇

14、數(shù)來分解為兩個更短的子序列，所以稱為“按時間抽選法”。000,001,010,011,100,101,110,111000,100,010,110,001,101,011,111(0), (1), (2), (3), (4), (5), (6), (7)xxxxxxxx(0), (4), (2), (6), (1), (5), (3), (7)xxxxxxxx以N=8為例稱為到位序規(guī)律運算量分析運算量分析： 由按時間抽選法FFT的流圖可見，當 時，共有L級蝶形，每級都由N/2個蝶形運算組成，每個蝶形有一次復(fù)乘、二次復(fù)加因而每級運算都需N/2次復(fù)乘和N次復(fù)加，這樣L級運算總共需要:2LN 2lo

15、g22FNNmLN2logFaNLNN復(fù)乘數(shù) 復(fù)加數(shù) 實際計算量與這個數(shù)字稍有不同，因為 01NW/4NNWj 這幾個系數(shù)都不用乘法運算，當N較大時，這些特例相對而言就很少。 出于計算機上乘法運算所用時間比加法運算所需時間多得多、故以乘法為例，在直接計算DFT與FFT算法的計算量之比為：222222logloglog22NNNNNNNNN2N2log2NN22log2NNN2414.041644.0864125.416256328.032 10248012.864 409619221.4128 1639444836.6256 65536102464.05122621142304113.8102

16、410485765120204.8算法特點算法特點 1 同址運算 2 到位序規(guī)律 3蝶形運算兩節(jié)點的“距離” 4 的確定rNW11( )( )( )( )( )( )rmmNmrmmNmxpxpW xqxqxpW xqp, q是參與本碟形單元運算的上下節(jié)點的序號。第m級序號為p, q的兩點只參與這一個碟形單元的運算，其輸出在第m+1級，并且這一碟形單元不涉及別的點，即某一列的N個數(shù)據(jù)送到存儲器后，經(jīng)蝶形運算，其結(jié)果為另列數(shù)據(jù)，它們以蝶形為單位仍存儲在這同一組存儲器中，直到最后輸出，中間無需其他存儲器。也就是蝶形的兩個輸出值仍放回蝶形的兩個輸人所在的存儲器中。每列的N2個蝶形運算全部完成后，再開

17、始下一列的蝶形運算。這樣存儲數(shù)據(jù)只需N個存儲單元。下一級的運算仍采用這種原位方式，只不過進人蝶形結(jié)的組合關(guān)系有所不同。這種原位運算結(jié)構(gòu)可以節(jié)省存儲單元，降低設(shè)備成本。稱同址運算以8點FFT為例，其輸入是倒位序的，輸出是自然順序的，其第一級(第一列)每個蝶形的兩節(jié)點間“距離”為1，第二級每個蝶形的兩節(jié)點“距離為2，第二級每個蝶形的兩節(jié)點“距離”為4，由此類推得，對 點FFT，當輸人為倒位序，輸出為正常順序時，其第m級運算，每個蝶形的兩節(jié)點“距離”為 。蝶形運算兩節(jié)點的“距離”2LN 12m（從左到右，第一級，第二級，第m級）從最右邊一級開始，看 分布規(guī)律rNW1111111( )( )(2)(2

18、)( )(2)rmmmNmmrmmmNmxpxpW xpxpxpW xp的確定842(2),0,1,123,0,1,2,32,0,11,0LrNrrrNmLN WrmWrmWrmWr12,0,1,21mrmWr任意第m級4按頻率抽選(DIF)的基-2 FFT算法(桑德圖基算法)這里討論另一種FFT算法，稱為按頻率抽選(DIF)的FFT算法，它是把輸出序列 (也是N點序列)按其順序的奇偶分解為越來越短的序列。( )X k算法原理仍設(shè)序列點數(shù)為 ，L為整數(shù)。在把輸出 按k的奇偶分組之前，先把輸入按n的順序分成前后兩半(注意，這不是頻率抽選)；2LN ( )X k1112002( )( )( )(

19、)NNNnknknkNNNNnnnX kx n Wx n Wx n W1122()2001220( )()2( )()2NNNnknkNNnnNNknkNNnNx n Wx nWNx nx nWW/2nkNWnkNW式中用的 是，不是 ，因而這并不是N2點DFT。/21NNW /2( 1)NkkNW 因為所以120( )( )( 1)()2NknkNnNX kx nx nW ( 1)1k( 1)1k k為偶數(shù)時k為奇數(shù)時221krkr0,1,12Nr 按照k的奇偶將 分為兩部分( )X k11222/200(2 )( )()( )()22NNnrnrNNnnNNXrx nx nWx nx nW

20、11222/200(21)( )()( )()22NNnrnnnrNNNNnnNNXrx nx nWWx nx nW W12( )( )()2( )( )()2nNNx nx nx nNx nx nx nW0,1,12Nn 令121/20122/20(2 )( )(21)( )NnrNnNnrNnXrx n WXrx n W0,1,12Nr 與時間抽選法的推導(dǎo)過程一樣，由于 ，N/2仍是個偶數(shù)，因而可以將每個N/2點DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點DFT進一步分解為兩個N/4點DFT。這兩個N4點DFT的輸入也是先將N/2點DFT的輸入上下對半分開后通過蝶形運算而形成。這樣的

21、分解可以一直進行到第L次( )，第L次實際L是做兩點DFT，它只有加減運算。但是，為了比較并為了統(tǒng)一運算結(jié)構(gòu)，我們?nèi)匀徊捎孟禂?shù)為 的蝶形運算來表示，這N/2個兩點DFT的N個輸出就是 的N點DFT的結(jié)果 。2LN 2LN nNW( )x n( )X k算法特點 1 同址運算 2蝶形運算兩節(jié)點的“距離” 3 的確定rNW1111( )( )( )( )( )( )mmmrmmmNXkXkXjXjXkXj W以8點FFT為例，其輸入是自然順序的，輸出是倒位序的，其第一級(第一列)每個蝶形的兩節(jié)點間“距離”為4，第二級每個蝶形的兩節(jié)點“距離為2，第二級每個蝶形的兩節(jié)點“距離”為1，由此類推得，對 點

22、FFT，當輸人為自然順序，輸出為倒位序時，其第m級運算，每個蝶形的兩節(jié)點“距離”為 。蝶形運算兩節(jié)點的“距離”2LN 22L mmN（從左到右，第一級，第二級，第m級）從最左邊一級開始，看 分布規(guī)律rNW11,0,1,1222,0,2,242,2,0,1,122rNrNrlNllNNmWrNNmWrNNmlWrkk的計算1,2,0,1,12rmNmNWrkk任意第m級1111( )( )()2()( )()22mmmmrmmmNmmNXkXkXkNNXkXkXkW按頻率抽選法與按時間抽選法的異同DIF的基本蝶形與DIT的基本蝶形運算順序有所不問，這才是實質(zhì)的不同，DIF的復(fù)數(shù)乘法只出現(xiàn)在減法之

23、后，DIT則是先作復(fù)乘后作加減法。DIF與DIT就運算量來說則是相同的，即都有L級(列)運算，每級運算需N2個蝶形運算來完成，總共需要 次復(fù)乘與 次復(fù)加 DIF法與DIT法都可進行同址運算。2log22FNNmLN2logFaNLNN只要把DFT運算中的每一個系數(shù) 換成 ，最后再乘以常數(shù)1/N，則以上所有按時間抽選或按頻率抽選的FFT都可以拿來運算IDFT。上面的FFT算法同樣可以適用于離散傅里葉反變換(1DFT)運算，即快速傅里葉反變換(IFFT)。比較IDFT和DFT公式:離散傅里葉反變換(IDFT)的快速計算方法10101( )( )( )( )NnkNkNnkNnx nX k WNX

24、kx n WnkNWnkNW上面這種IFFT算法雖然編程很方便，但是需要稍稍改動FFT的程序和參數(shù)才能實現(xiàn)。下面討論一種完全不用改變FFT的程序就可以計算IFFT的方法。我們對IDFT公式式取共軛：1*01( )( )NnkNkx nXk WN*1*011( )( )( )NnkNkx nXk WDFT XkNN則這說明，只要先將X(k)取共軛，就可以直接利用FF丁子程序，最后再將運算結(jié)果取一次共扼，并乘以1/N，即得到x(n)值。因此，F(xiàn)FT運算和IFFT運算就可以共用一個子程序塊。*nknkNNWW基-4FFT算法 時就是基-4FFT算法4LN 3111142430424( )( )( )( )( )NNNNnknknknkNNNNNNNnnnnX kx n Wx n Wx n Wx n W111134444()()()42400003( )()()()424NNNNNNNnknknknkNNNNnnnnNNNx n Wx nWx nWx nW /4/23/43( )()()()424NkNkNknkNNNNNNNx nx nWx nWx nWW頻率抽取的基-4FFT算法4 ,41,42,43,0,1,14Nkr krkrkrr/4/23/41,1,kNNNNNNNNWWj WWj 144014/403(4 )( )()()