第四章2按時(shí)間抽選的基-2FFT算法同濟(jì)大學(xué)數(shù)字信號(hào)處理ppt課件

1、二 、按時(shí)間抽選的基-2FFT算法1、算法原理設(shè)序列點(diǎn)數(shù) N = 2L，L 為整數(shù)。 假設(shè)不滿足，那么補(bǔ)零 12221xrx rxrxr0,1,.,/2 1rN將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱基-2FFT算法。那么x(n)的DFT: 111000NNNnknknkNNNnnnX 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,

2、1,./2 1r kN再利用周期性求X(k)的后半部分1212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,/2 1kN 121122,/222XkXkNNNXkXkXkXk是以為周期的/22NkNkkNNNNWWWW 又分解后的運(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 N 2 / 2N (N / 2 1)一個(gè)蝶形12N / 2個(gè)蝶形N / 2N總計(jì)22/2/2/2NNN2/2 1/2N NNN運(yùn)算量減少了近一半1314(2 )( )(21)( )xlx lxlx l

3、0,1,.,/4 1lN13/2413/24( )( )( )()( )( )4kNkNX kXkWXkNX kXkWXk0,1,.,14Nk N / 2仍為偶數(shù)，進(jìn)一步分解：N / 2 N / 425/2625/26( )( )( )()( )( )4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 同理：其中：552( )( )(2 )XkDFT x lDFT xl662( )( )(21)XkDFT x lDFT xl0,1,.,/4 1lN2/2kkNNWW統(tǒng)一系數(shù)：這樣逐級(jí)分解，直到2點(diǎn)DFT當(dāng)N = 8時(shí)，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k = 0

4、, 10003322301033223(0)(0)(1)(0)(4)(1)(0)(1)(0)(4)NNXxWW xxW xXxWW xxW x/4 1133/43/400( )( )( )NlklkNNllXkx l Wx l W0,1k 0004422401044224(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)NNXxWW xxW xXxWW xxW x/4 1144/44/400( )( )( )NlklkNNllXkx l Wx l W0,1k 2、運(yùn)算量當(dāng)N = 2L時(shí)，共有L級(jí)蝶形，每級(jí)N / 2個(gè)蝶形，每個(gè)蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。2log22FNNmLN復(fù)

5、數(shù)乘法：2logFaNLNN復(fù)數(shù)加法：222()2()loglog2FFmDFTNNNmFFTNN比較DFT 3、算法特點(diǎn)1原位計(jì)算1111( )( )( )( )( )( )rmmmNrmmmNXkXkXj WXjXkXj Wm表示第m級(jí)迭代，k，j表示數(shù)據(jù)所在的行數(shù)2倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111n0n1n2000110110011012 102( )()x nnn n n2 102()nn n n0 122()nn n n3蝶形運(yùn)算對(duì)N = 2L點(diǎn)FFT，輸入倒位序，輸出自然序，第m級(jí)運(yùn)算每個(gè)蝶形的兩節(jié)點(diǎn)間隔為 2m1第m級(jí)運(yùn)算：1111111( )( )(2)(2)( )(2)mrmmmNmmrmmmNXkXkXkWXkXkXkW 蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為k值，表示成L位二進(jìn)制數(shù)，左移L m位，把右邊空出的位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。rNW 的確定2( )2L mrk 4存儲(chǔ)單元輸入序列x(n) : N個(gè)存