快速傅里葉變換

1、- DIT-FFT算法 - IFFT算法1 引言引言FFT: Fast Fourier Transform1965年，Cooley-Turky 發(fā)表文章機器計算傅里葉級數(shù)的一種算法，提出FFT算法，解決DFT運算量太大，在實際使用中受限制的問題。FFT的應用。頻譜分析、濾波器實現(xiàn)、實時信號處理等。DSP芯片實現(xiàn)。TI公司的TMS 320c30，10MHz時鐘，基2-FFT1024點FFT時間15ms。典型應用：信號頻譜計算、系統(tǒng)分析等)()(kXnxDFT )()()(nynhnxFFTnhnyIFFTFFTnx)()()( 系統(tǒng)分析 頻譜分析與功率譜計算2 直接計算直接計算DFT的問題及改進

2、途徑的問題及改進途徑10)()(NnknNWnxkX10)(1)(NkknNWkXNnx2.1、 DFT與與IDFT( )Nx n點有限長序列2.2、DFT與與IDFT運算特點運算特點復數(shù)乘法復數(shù)乘法復數(shù)加法復數(shù)加法一個一個X(k)NN 1N個個X(k)(N點點DFT)N 2N (N 1)10( )NnkNnx n Wajbcjdacbdj adcb實數(shù)乘法實數(shù)乘法實數(shù)加法實數(shù)加法一次復乘一次復乘42一次復加一次復加2一個一個X (k) 4N2N+2 (N 1)=2 (2N 1)N個個X (k)(N點點DFT)4N 22N (2N 1)同理：同理：IDFT運算量與運算量與DFT相同相同2.3、

3、降低、降低DFT運算量的考慮運算量的考慮nkNW 的特性*()() ()nknkN n kn N kNNNNWWWW對稱性()() nkN n kn N kNNNWWW周期性 nkmnkNmNWW可約性/nknk mNN mWW0/2(/2) 11Nk NkNNNNWWWW 特殊點：2jnknkNNWeNknkNNWWnNnkNNWW2jmnkmNe221NjjNee FFT算法分類算法分類:q 時間抽選法時間抽選法DIT: Decimation-In-Timeq 頻率抽選法頻率抽選法DIF: Decimation-In-FrequencyFFTDFTDFTDFTDFT算法的基本思想： 利用系

4、數(shù)的特性，合并運算中的某些項， 把長序列短序列，從而減少其運算量。3 按時間抽?。ò磿r間抽取（DIT）的）的FFT算法算法12/.210) 12()()2()(21Nrrxrxrxrx，（Decimation In Time）3.1、算法原理、算法原理設(shè)序列點數(shù)設(shè)序列點數(shù) N = 2L，L 為整數(shù)。為整數(shù)。 若不滿足，則補零若不滿足，則補零將序列將序列x(n)按按n的奇偶分成兩組：的奇偶分成兩組：N為為2的整數(shù)冪的的整數(shù)冪的FFT算法稱算法稱基基-2FFT算法算法。將將N點點DFT定義式分解為兩個長度為定義式分解為兩個長度為N/2的的DFT10)()()(NnknNWnxnxDFTkXkrNn

5、NrrkNnNrWrxWrx)12(12/0212/0) 12()2( 為奇為偶 )(12/02/2)(2/12/0121)()(kXNrrkNkNkXrkNNrWrxWWrx)()()(21kXWkXkXkN記：記： （1）rkNrkNWW2/2（這一步利用：（這一步利用： ）,0,1,./2 1r kN再利用周期性求再利用周期性求X(k)的后半部分的后半部分/22NkNkkNNNNWWWW 又)(2)()()(222112/02/112/0)2/(2/11kXkNXkXWrxWrxkNXNrrkNNrkNrNrkNkNrNWW2/)2/(2/)2()2()2()2(12/,.2 , 1 ,

6、 0)()()(2)2/(121kNXWkNXkNXNkkXWkXkXkNNkN，12/,.2 , 1 , 0)()(21NkkXWkXkN，將上式表達的運算用一個專用“蝶形”信流圖表示。)(1kX)(2kX)()(21kXWkXkN)()(21kXWkXkNkNW1212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,/21kN注：a. 上支路為加法，下支路為減法； b. 乘法運算的支路標箭頭和系數(shù)。用用“蝶形結(jié)蝶形結(jié)”表示上面運算的分解：表示上面運算的分解： 328N)0(x)1 (x)2(x)3(x)4(x)5(x)6(x)7(x)0(X

7、) 1 (X)2(X)3(X)4(X)5(X)6(X)7(X1NW0NW2NW3NW)0(1X)1(1X)2(1X)3(1X)0(2X)1 (2X(3)2X)2(2XDFTN點2DFTN點2分解后的運算量：分解后的運算量：復數(shù)乘法復數(shù)加法一個N/2點DFT (N/2)2N/2 (N/2 1)兩個N/2點DFT N2/2N (N/2 1)一個蝶形12N/2個蝶形N/2N總計22/2/2/2NNN2/2 1/2N NNN運算量減少了近一半運算量減少了近一半進一步分解進一步分解MN2122MN2N4N由于由于 ， 仍為偶數(shù)，因此，兩個仍為偶數(shù)，因此，兩個 點點DFT又可同樣進一步分解為又可同樣進一步

8、分解為4個個 點的點的DFT。1314(2 )( )(21)( )xlx lxlx l0,1,.,/4 1lN13/2413/24( )( )( )()( )( )4kNkNX kXkWXkNX kXkWXk0,1,.,14Nk 02/NW12/NW)(3lx)(4lx)2(x)4(x)6(x)0(x)0(1X) 1 (1X)2(1X) 3(1X) 0(3X) 1 (3X)0(4X) 1 (4XDFTN點4DFTN點4“蝶形蝶形”信流圖表示信流圖表示 )(.nxDFTN點4DFTN點4DFTN點4DFTN點4)2(x)4( x)6( x)0( x) 1 ( x) 3 ( x)5(x)7( x0

9、NW2NW0NW2NW1NW0NW2NW3NW)0(X) 1 (X) 2(X) 3(X) 4(X) 5(X)6(X)(.kX)7(XN點點DFT分解為四個分解為四個N/4點的點的DFT類似的分解一直繼續(xù)下去，直到分解為最后的兩類蝶形運算為止(2點DFT).如上述N=8=23，N/4=2點中： 類似進一步分解類似進一步分解1點點DFTx(0)1點點DFTx(4)X3(0)X3(1)02W進一步簡化為蝶形流圖：進一步簡化為蝶形流圖：0NWX3(0)X3(1)x(0)x(4)4()0()4()0()0(004/3xWxxWxXNN因此因此8點點FFT時間抽取方法的信流圖如下時間抽取方法的信流圖如下第

10、一級.)2(x)4(x)6(x)0(x) 1 ( x) 3 ( x)5(x)7(x0NW0NW0NW0NW 第二級.0NW2NW0NW2NW1NW0NW2NW3NW)0(X) 1 (X)2(X)3(X)4(X)5(X)6(X)7(X 第三級.FFT運算量與運算特點運算量與運算特點 1 N=2L時，共有L=log2N級運算；每一級有N/2個蝶形結(jié)。2每一級有N個數(shù)據(jù)中間數(shù)據(jù)，且每級只用到本級的轉(zhuǎn)入中間數(shù)據(jù)，適合于迭代運算。3計算量： 每級N/2次復乘法，N次復加。（每蝶形只乘一次，加減各一次）。共有L*N/2=N/2log2N 次復乘法；復加法L*N=Nlog2N 次。與直接DFT定義式運算量相

11、比(倍數(shù)) N2/(Nlog2N) 。當 N大時，此倍數(shù)很大。222()2()loglog2FFmDFTNNNmFFTNN與與DFT比較比較 可以直觀看出可以直觀看出:當點數(shù)當點數(shù)N越大時，越大時，F(xiàn)FT的優(yōu)點更突出。的優(yōu)點更突出。按時間抽取按時間抽取FFT蝶形運算特點蝶形運算特點 1、關(guān)于FFT運算的混序與順序處理（位倒序處理） 由于輸入序列按時間序位的奇偶抽取，故輸入序列是混序的，為此需要先進行混序處理?；煨蛞?guī)律混序規(guī)律： x(n)按n位置進行碼位（二進制）倒置規(guī)律輸入，而非自然排序，即得到混序排列。所以稱為位倒序處理。位倒序?qū)崿F(xiàn)位倒序?qū)崿F(xiàn)：（1）DSP實現(xiàn)采用位倒序?qū)ぶ罚?）通用計算機實

12、現(xiàn)可以有兩個方法：一是嚴格按照位倒序含義進行；二是倒進位的加N/2。倒位序倒位序自然序自然序00000000100410010102201011063011001141001015510101136110111771112 102( )()x nnn n n倒位序倒位序例： 計算 ， 。計算 點FFT。用時間抽取輸入倒序算法，問倒序前 寄存器的數(shù) 和倒序后 的數(shù)據(jù)值？2)(nnx31.2 , 1 , 0n32N)13( x)13( x16913)13(2x5232 N210)01101()13(102)22()10110(48422)13(2x解：倒序前解：倒序前 倒序倒序 倒序為倒序為 倒序

13、后倒序后 DIT FFT中最主要的蝶形運算實現(xiàn)中最主要的蝶形運算實現(xiàn)（1）參與蝶形運算的兩類結(jié)點（信號）間“距離”（碼地址）與其所處的第幾級蝶形有關(guān)；第m級的“結(jié)距離”為 (即原位計算迭代）（2）每級迭形結(jié)構(gòu)為，12m)2(,.2 , 1LNLmrNmmmmmrNmmmmWkXkXkXWkXkXkX)2()()2()2()()(1111111FFT算法中一些概念算法中一些概念 （1）“級”概念將N 點DFT先分成兩個N/2點DFT，再是四個N/4點DFT直至N/2個兩點DFT. 每分一次稱為“一”級運算。因為N=2M所以N點DFT可分成M級如上圖所示依次m = 0, m = 1 . M-1共M

14、級（2）“組”概念 每一級都有N/2個蝶形單元，例如：N=8,則每級都有4個蝶形單元。每一級的N/2個蝶形單元可以分成若干組，每一組具有相同的結(jié)構(gòu)，相同的 因子分布，第m級的組數(shù)為：rNW12mN例：N=8=23，分3級。m=0級,分成四組,每組系數(shù)為m=1級,分成二組,每組系數(shù)為m=2級,分成一組,每組系數(shù)為080204/WWWN28082012/02/,WWWWWWNNNN382818083210,WWWWWWWWNNNN(3) 因子的分布rNW121 , 0,3 , 2 , 102101001238281808828081404408022mkkkkkWmWWWWkWmWWWWkWmWW

15、kWmm級的系數(shù)為看出：第，級，級，級，由上可知：結(jié)論：每由后向前（m由M-1-0級）推進一級，則此系數(shù)為后級系數(shù)中偶數(shù)序號的那一半。DIT算法的其他形式流圖算法的其他形式流圖輸入倒位序輸出自然序輸入自然序輸出倒位序輸入輸出均自然序相同幾何形狀輸入倒位序輸出自然序輸入自然序輸出倒位序時間抽取、時間抽取、 輸入自然順序、輸入自然順序、 輸出倒位序的輸出倒位序的FFT流圖流圖 0NW0NW0NW2NW1110NW10NW2NW1111X(0)x(0)X(4)x(1)X(2)x(2)X(6)x(3)X(1)x(4)X(5)x(5)X(3)x(6)X(7)x(7)110NW0NW2NW1NW3NW11

16、 例例 用用FFT算法處理一幅算法處理一幅NN點的二維圖像，如點的二維圖像，如用每秒可做用每秒可做10萬次復數(shù)乘法的計算機，當萬次復數(shù)乘法的計算機，當N=1024時，時，問需要多少時間（不考慮加法運算時間）？問需要多少時間（不考慮加法運算時間）？ 例例 用用FFT算法處理一幅算法處理一幅NN點的二維圖像，如點的二維圖像，如用每秒可做用每秒可做10萬次復數(shù)乘法的計算機，當萬次復數(shù)乘法的計算機，當N=1024時，時，問需要多少時間（不考慮加法運算時間）？問需要多少時間（不考慮加法運算時間）？ 解解 當當N=1024點時，點時，F(xiàn)FT算法處理一幅二維圖像所算法處理一幅二維圖像所需復數(shù)乘法約為需復數(shù)乘法約為 次，僅為直接計算次，僅為直接計算DFT所需時間的所需時間的10萬分之一。萬分之一。 即原需要即原需要3000小時，現(xiàn)小時，現(xiàn)在只需要在只需要2 分鐘。分鐘。 722210log2NN- DIT-FFT算法 - IFFT算法IDFT的的FFT算法算法一、從定義比較分析knNNkWkXNkXIDFTn