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

2、 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-3-215 再利用周期性求再利用周期性求X(k)的后半部分的后半部分 121122,/222XkXkNNNXkXkXkXk是以為周期的/22NkNkkNNNNWWWW 又2022-3-2161212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,

3、/2 1kN 一個(gè)一個(gè)“蝶形運(yùn)算蝶形運(yùn)算”包含包含1次乘法，次乘法，2次加法次加法2022-3-2172022-3-21復(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ì)8分解后的運(yùn)算量：分解后的運(yùn)算量：運(yùn)算量減少了近一半運(yùn)算量減少了近一半22/2/2/2NNN2/2 1/2N NNN2022-3-21N / 2仍為偶數(shù)，進(jìn)一步分解：N / 2 N / 491314(2 )( )(21)( )xlx lxlxl0,

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

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

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

7、乘法：2logFaNLNN復(fù)數(shù)加法復(fù)數(shù)加法：222()2()loglog2FFmDFTNNNmFFTNN比較比較DFT 2022-3-21182022-3-21算法的計(jì)算復(fù)雜度算法的計(jì)算復(fù)雜度19復(fù)乘次數(shù)NN 2NN2log22022-3-21例 .如果一臺(tái)通用計(jì)算機(jī)的速度為平均每次復(fù)乘 ，每次復(fù)加 ，用它來(lái)計(jì)算512點(diǎn)的 ，問(wè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 1010.5

8、10512512 10.130816TNNs所以直接利用DFT 計(jì)算所需時(shí)間： 121.441536TTTs2022-3-2120復(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ù)為 。 FFT2log2NN2logNN2022-3-2121222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序0000000010041001010220101106301100114100101551010113611011177111222 1 02()nn nn0122()nn n n2 102( )()x nnn n n23倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x011x1110