按時(shí)間抽取的FFT算法講義

1、時(shí)間抽選法時(shí)間抽選法DIT: Decimation-In-Time頻率抽選法頻率抽選法DIF: Decimation-In-Frequency2022-2-2527-2 按按時(shí)間抽取的FFT算法一、按時(shí)間抽取的算法原理二、按時(shí)間抽取的算法特點(diǎn)三、按時(shí)間抽取FFT算法的其他形式2022-2-253一、按時(shí)間抽取的算法原理設(shè)序列點(diǎn)數(shù) N = 2L，L 為整數(shù)。若不滿足，則補(bǔ)零N為2的整數(shù)冪的FFT算法稱基-2FFT算法。將序列x(n)按n的奇偶分成兩組： 12221xrx rxrxr0,1,.,/2 1rN2022-2-254 則則x(n)的的DFT: 111000NNNnknknkNNNnnnX

2、kx n Wx n Wx n Wn為偶數(shù)n為奇數(shù)/2 1/2 121200221NNrkrkNNrrxr WxrW /2 1/2 1221200NNrkrkkNNNrrx rWWxrW /2 1/2 11/22/200NNrkkrkNNNrrx r WWxr W 12kNXkW Xk,0,1,./2 1r kN2022-2-255 再利用周期性求再利用周期性求X(k)的后半部分的后半部分 121122,/222XkXkNNNXkXkXkXk是以為周期的/22NkNkkNNNNWWWW 又2022-2-2561212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW

3、 Xk0,1,.,/2 1kN 一個(gè)一個(gè)“蝶形運(yùn)算蝶形運(yùn)算”包含包含1次乘法，次乘法，2次加法次加法2022-2-2572022-2-258復(fù)數(shù)乘法復(fù)數(shù)乘法復(fù)數(shù)加法復(fù)數(shù)加法一個(gè)一個(gè)N / 2點(diǎn)點(diǎn)DFT(N / 2)2N / 2 (N / 2 1)兩個(gè)兩個(gè)N / 2點(diǎn)點(diǎn)DFTN 2 / 2N (N / 2 1)一個(gè)蝶形一個(gè)蝶形12N / 2個(gè)蝶形個(gè)蝶形N / 2N總計(jì)總計(jì)分解后的運(yùn)算量：分解后的運(yùn)算量：運(yùn)算量減少了近一半運(yùn)算量減少了近一半22/2/2/2NNN2/2 1/2N NNN2022-2-259N / 2仍為偶數(shù)，進(jìn)一步分解：N / 2 N / 41314(2 )( )(21)( )xl

4、xlxlxl0,1,.,/41lN13/ 2413/ 24()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 102/2kkNNWW統(tǒng)一系數(shù)：同理同理：25/ 2625/ 26()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 其中：其中：552( )( )(2 )XkDFT xlDFT xl662( )( )(21)XkDFT xlDFT xl0,1,.,/ 41lN這樣逐級(jí)分解，直到這樣逐級(jí)分解，直到2點(diǎn)點(diǎn)DFT2022-2-2511基2時(shí)間抽取FFT算法流圖N=2xk=x0, x1 1 0002xWxX 1 0 1 12

5、xWxX0 x 1 x0X-102W 1 X 1 002xWx2022-2-25124點(diǎn)基2時(shí)間抽取FFT算法流圖x0 x2x1x3X10X11X20X212點(diǎn)DFT2點(diǎn)DFT111104W14W02W02WX 0X 1X 2X 31 , 0,241mmXWmXmXm1 , 0,2241mmXWmXmXm2022-2-25134點(diǎn)基2時(shí)間抽取FFT算法流圖2022-2-25148點(diǎn)基2時(shí)間抽取FFT算法流圖4點(diǎn)DFT4點(diǎn)DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W3 ,

6、2 , 1 , 0,4281mmXWmXmXm3 , 2 , 1 , 0,281mmXWmXmXm2022-2-25154點(diǎn)DFT4點(diǎn)DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W8點(diǎn)基2時(shí)間抽取FFT算法流圖2022-2-2516基基2時(shí)間抽取時(shí)間抽取FFT算法算法第一級(jí)第一級(jí)第二級(jí)第二級(jí)第三級(jí)第三級(jí)2022-2-2517二、按時(shí)間抽取的算法特點(diǎn)1.計(jì)算速度 當(dāng)N = 2L時(shí)，共有L級(jí)蝶形，每級(jí)N / 2個(gè)蝶形，每個(gè)蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。2log22FNNmLN

7、復(fù)數(shù)乘法復(fù)數(shù)乘法：2logFaNLNN復(fù)數(shù)加法復(fù)數(shù)加法：222()2()loglog2FFmDFTNNNmFFTNN比較比較DFT 2022-2-25182022-2-2519算法的計(jì)算復(fù)雜度算法的計(jì)算復(fù)雜度復(fù)乘次數(shù)NN 2NN2log22022-2-2520例 .如果一臺(tái)通用計(jì)算機(jī)的速度為平均每次復(fù)乘 ，每次復(fù)加 ，用它來計(jì)算512點(diǎn)的 ，問直接計(jì)算需要多少時(shí)間，用 運(yùn)算需要多少時(shí)間。 5 s0.5 s DFT x nFFT解：(1)直接利用 計(jì)算： 復(fù)乘次數(shù)為 ，復(fù)加次數(shù)為 。 DFT2N1N N 復(fù)乘所需時(shí)間 626215 105 105121.31072TNs復(fù)加所需時(shí)間 6260.5

8、 1010.5 10512512 10.130816TNNs所以直接利用DFT 計(jì)算所需時(shí)間： 121.441536TTTs2022-2-2521復(fù)乘所需時(shí)間 612625 10log25125 10log 5120.011522NTNs 622620.5 10log0.5 10512log 5120.002304TNNs復(fù)加所需時(shí)間 所以用 FFT 計(jì)算所需時(shí)間 120.013824TTTs(2) 利用 計(jì)算： 復(fù)乘次數(shù)為 ，復(fù)加次數(shù)為 。 FFT2log2NN2logNN222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序00000000100410010102201011063011001141001015510101136110111771112102()nn n n0 122()nn nn2 102( )()x nnn n n2022-2-2523倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x1