快速傅里葉變換

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

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

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

4、數(shù)的特性，合并運(yùn)算中的某些項(xiàng)， 把長序列短序列，從而減少其運(yùn)算量。3 按時(shí)間抽?。ò磿r(shí)間抽取（DIT）的）的FFT算法算法12/.210) 12()()2()(21Nrrxrxrxrx，（Decimation In Time）3.1、算法原理、算法原理設(shè)序列點(diǎn)數(shù)設(shè)序列點(diǎn)數(shù) N = 2L，L 為整數(shù)。為整數(shù)。 若不滿足，則補(bǔ)零若不滿足，則補(bǔ)零將序列將序列x(n)按按n的奇偶分成兩組：的奇偶分成兩組：N為為2的整數(shù)冪的的整數(shù)冪的FFT算法稱算法稱基基-2FFT算法算法。將將N點(diǎn)點(diǎn)DFT定義式分解為兩個(gè)長度為定義式分解為兩個(gè)長度為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，將上式表達(dá)的運(yùn)算用一個(gè)專用“蝶形”信流圖表示。)(1kX)(2kX)()(21kXWkXkN)()(21kXWkXkNkNW1212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,/21kN注：a. 上支路為加法，下支路為減法； b. 乘法運(yùn)算的支路標(biāo)箭頭和系數(shù)。用用“蝶形結(jié)蝶形結(jié)”表示上面運(yùn)算的分解：表示上面運(yùn)算的分解： 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點(diǎn)2DFTN點(diǎn)2分解后的運(yùn)算量：分解后的運(yùn)算量：復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)N/2點(diǎn)DFT (N/2)2N/2 (N/2 1)兩個(gè)N/2點(diǎn)DFT N2/2N (N/2 1)一個(gè)蝶形12N/2個(gè)蝶形N/2N總計(jì)22/2/2/2NNN2/2 1/2N NNN運(yùn)算量減少了近一半運(yùn)算量減少了近一半進(jìn)一步分解進(jìn)一步分解MN2122MN2N4N由于由于 ， 仍為偶數(shù)，因此，兩個(gè)仍為偶數(shù)，因此，兩個(gè) 點(diǎn)點(diǎn)DFT又可同樣進(jìn)一步分解為又可同樣進(jìn)一步

8、分解為4個(gè)個(gè) 點(diǎn)的點(diǎn)的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點(diǎn)4DFTN點(diǎn)4“蝶形蝶形”信流圖表示信流圖表示 )(.nxDFTN點(diǎn)4DFTN點(diǎn)4DFTN點(diǎn)4DFTN點(diǎn)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點(diǎn)點(diǎn)DFT分解為四個(gè)分解為四個(gè)N/4點(diǎn)的點(diǎn)的DFT類似的分解一直繼續(xù)下去，直到分解為最后的兩類蝶形運(yùn)算為止(2點(diǎn)DFT).如上述N=8=23，N/4=2點(diǎn)中： 類似進(jìn)一步分解類似進(jìn)一步分解1點(diǎn)點(diǎn)DFTx(0)1點(diǎn)點(diǎn)DFTx(4)X3(0)X3(1)02W進(jìn)一步簡化為蝶形流圖：進(jìn)一步簡化為蝶形流圖：0NWX3(0)X3(1)x(0)x(4)4()0()4()0()0(004/3xWxxWxXNN因此因此8點(diǎn)點(diǎn)FFT時(shí)間抽取方法的信流圖如下時(shí)間抽取方法的信流圖如下第

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

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

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

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

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

15、kWmm級(jí)的系數(shù)為看出：第，級(jí)，級(jí)，級(jí)，由上可知：結(jié)論：每由后向前（m由M-1-0級(jí)）推進(jìn)一級(jí)，則此系數(shù)為后級(jí)系數(shù)中偶數(shù)序號(hào)的那一半。DIT算法的其他形式流圖算法的其他形式流圖輸入倒位序輸出自然序輸入自然序輸出倒位序輸入輸出均自然序相同幾何形狀輸入倒位序輸出自然序輸入自然序輸出倒位序時(shí)間抽取、時(shí)間抽取、 輸入自然順序、輸入自然順序、 輸出倒位序的輸出倒位序的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點(diǎn)的二維圖像，如點(diǎn)的二維圖像，如用每秒可做用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，時(shí)，問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？ 例例 用用FFT算法處理一幅算法處理一幅NN點(diǎn)的二維圖像，如點(diǎn)的二維圖像，如用每秒可做用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，時(shí)，問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？ 解解 當(dāng)當(dāng)N=1024點(diǎn)時(shí)，點(diǎn)時(shí)，F(xiàn)FT算法處理一幅二維圖像所算法處理一幅二維圖像所需復(fù)數(shù)乘法約為需復(fù)數(shù)乘法約為 次，僅為直接計(jì)算次，僅為直接計(jì)算DFT所需時(shí)間的所需時(shí)間的10萬分之一。萬分之一。 即原需要即原需要3000小時(shí)，現(xiàn)小時(shí)，現(xiàn)在只需要在只需要2 分鐘。分鐘。 722210log2NN- DIT-FFT算法 - IFFT算法IDFT的的FFT算法算法一、從定義比較分析knNNkWkXNkXIDFTn