第3章離散傅里葉變換2

1、3.3 快速傅里葉變換GFFT 并 不 是 一 種 新 的 變 換 形 式，它 只 是 DFT 的 一 種 快快 速速 算算 法法 。并 且 根 據(jù) 對(duì) 序 列 分 解 與 選 取 方 法 的 不 同 而 產(chǎn) 生 了 FFT 的 多 種 算 法 。計(jì)算DFT復(fù)數(shù)運(yùn)算量10)() 1 (NnnNWnxX利用 的固有對(duì)稱性和周期性改善DFT的運(yùn)算效率knNWknNW的對(duì)稱性：nkNknNWW*)(knNW的周期性：)()(kNnNkNnNknNWWW1)()(22kjkNNjkNNeeW因?yàn)椋?, 1 , 0Nk1)()(22njNnNjNnNeeW1, 1 , 0Nn由此可得出：nkNknNNk

2、NnNWWW)()(1sincos)(222/jeWNNjNNkNNkNWW)(2nkNW 的特性*()() ()nknkN n kn N kNNNNWWWW對(duì)稱性()() nkN n kn N kNNNWWW周期性 nkmnkNmNWW可約性/nknk mNN mWW0/2(/2) 11Nk NkNNNNWWWW 特殊點(diǎn)：2jnknkNNWeNknkNNWWnNnkNNWW2jmnkmNe221NjjNee 時(shí)間抽取基-2FFT算法Decimation-in-Time (DIT)一、算法原理一、算法原理n設(shè)輸入序列長度為N=2M(M為正整數(shù)，將該序列按時(shí)間順序的奇偶分解為越來越短的子序列，稱

3、為基2按時(shí)間抽取的FFT算法。也稱為Coolkey-Tukey算法。n其中基數(shù)2-N=2M，M為整數(shù)。若不滿足這個(gè)條件，可以人為地加上若干零值（加零補(bǔ)長）使其達(dá)到 N=2M。1、算法推導(dǎo) 12221xrx rxrxr0,1,.,/2 1rN將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱基-2FFT算法。 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/200NNrkkrk

4、NNNrrx r WWxr W 12kNXkW Xk,0,1,./2 1r kN12/1 , 0)()()21NkDFTNkXWkXkXkN中的前半部分點(diǎn)又合成（1212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,/21kN 121122,/222XkXkNNNXkXkXkXk是以為周期的/22NkNkkNNNNWWWW 又12/012/022/2)2/(2/2212/012/012/1)2/(2/11)2/(2/2/)()()()2()()()()2(NrNrrkNkNrNNrNrrkNkNrNNkrNrkNkXWrxWrxkNXkXWr

5、xWrxkNXWW后半部的k值所對(duì)應(yīng)的X1(k),X2(k)則完全重復(fù)了前半部分的k值所對(duì)應(yīng)的X1(k),X2(k)的值。)()()(212/)2/kXWkXkXWWWWkNkNkNNNkNN后半部分：又（頻域中的N個(gè)點(diǎn)頻率成分為：)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN后半部分：前半部分：?結(jié)論：只要求出（0N/2-1）區(qū)間內(nèi)的各個(gè)整數(shù)k值所對(duì)應(yīng)的X1(k),X2(k)值，即可以求出(0N-1)整個(gè)區(qū)間內(nèi)全部X(k)值，這就是FFT能大量節(jié)省計(jì)算的關(guān)鍵。v由于N=2L，因此N/2仍為偶數(shù)，可以依照上面方法進(jìn)一步把每個(gè)N/2點(diǎn)子序列，再按輸入n的奇偶分解為兩個(gè)

6、N/4點(diǎn)的子序列，按這種方法不斷劃分下去，直到最后剩下的是2點(diǎn)DFT，兩點(diǎn)DFT實(shí)際上只是加減運(yùn)算加減運(yùn)算。例子：求 N=23=8點(diǎn)FFT變換)()() 2/()()()(2121kXWkXNkXkXWkXkXkNkN12/, 0Nk先將N=8DFT分解成2個(gè)4點(diǎn)DFT：可知：時(shí)域上：x(0),x(2),x(4),x(6)為偶子序列 x(1),x(3),x(5),x(7)為奇子序列 頻域上：X(0)X(3)，由X(k)給出 X(4)X(7),由X(k+N/2)給出2、蝶形結(jié)即蝶式計(jì)算結(jié)構(gòu)也即為蝶式信號(hào)流圖上面頻域頻域中前/后半部分表示式可以用蝶形信號(hào)流圖表示。X1(k)X2(k)kNW)()(

7、21kXWkXkN)()(21kXWkXkN作圖要素：作圖要素：(1)左邊兩路為輸入左邊兩路為輸入(2)右邊兩路為輸出右邊兩路為輸出(3)中間以一個(gè)小圓表示加、中間以一個(gè)小圓表示加、減運(yùn)算（右上路為相加輸減運(yùn)算（右上路為相加輸出、右下路為相減輸出出、右下路為相減輸出)(4)如果在某一支路上信號(hào)需要進(jìn)行如果在某一支路上信號(hào)需要進(jìn)行相乘運(yùn)算，則在該支路上標(biāo)以箭頭，相乘運(yùn)算，則在該支路上標(biāo)以箭頭，將相乘的系數(shù)標(biāo)在箭頭旁。將相乘的系數(shù)標(biāo)在箭頭旁。(5)當(dāng)支路上沒有箭頭及系當(dāng)支路上沒有箭頭及系數(shù)時(shí)，則該支路的傳輸比數(shù)時(shí)，則該支路的傳輸比為為1。將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DFT的信號(hào)流圖X(4)X(7)同

8、學(xué)們自已寫4點(diǎn)DFTx(0)x(2)x(4)x(6)4點(diǎn)DFTx(1)x(3)x(5)x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶數(shù)序列奇數(shù)序列3821282118210821) 3 () 3 (3) 2() 2(2) 1 () 1 (1) 0() 0(0WXXXWXXXWXXXWXXX）（）（）（）（如：x1(r)x2(r)奇序列、偶序列、) 6() 2() 4() 0(: )(1xxxxrx奇序列、偶序列、同理：)7() 3 () 5 () 1 (: )(2

9、xxxxrx1014012()()2(4131，），在此（）奇序列（）偶序列若設(shè)：LNLLXLxLXLx1014012()()2(6252，），在此（）奇序列（）偶序列同理：LNLLXLxLXLxb 求2點(diǎn)的DFT)()4/()()()()()()()4/10)()() 12()2()()(62/5262/52242/3142/314/0) 12(2/114/022/1111LXWLXNkXLXWLXkXrxLXWLXNkXLLXWLXWLXWLXkXkXrxkNkNkNkNNLkLNNLLkNDFT）也可分解為：同樣，（同理：，其中（可分解為：c 一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFT

10、x(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)04W14W01134413440113441344(0)(0)(0)(1)(1)(1)(2)(0)(0)(3)(1)(1)XXW XXXW XXXW XXXW X其中d 另一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)04W14W01254625460125462546(0)(0)(0)(1)(1)(1)(2)(0)(0)(3)(1)(1)XXW XXXW XXXW XXX

11、W X其中同理：(3)將N/4（2點(diǎn)）DFT再分解成2個(gè)1點(diǎn)的DFT021022120202120230202020231021 , 0; 1 , 0)4()0()4()0() 1 ()4()0()4()0()0()()(2WWknWWWWWxWxWxWxXWxWxWxWxXWnxkXnknknkNnkNnnkN，其中，則這里用到對(duì)稱性這是一蝶形結(jié)代入上面流圖可知： 最后剩下兩點(diǎn)DFT,它可分解成兩個(gè)一點(diǎn)DFT，但一點(diǎn)DFT就等于輸入信號(hào)本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x(0)、x(4)為例。b 2個(gè)1點(diǎn)的DFT蝶形流圖1點(diǎn)DFTx(0)1點(diǎn)DFTx(4)X3(0)X3(1)02W進(jìn)

12、一步簡化為蝶形流圖：02WX3(0)X3(1)x(0)x(4)4()0()4()0() 1 ()4()0()4()0()0(023023xxxWxXxxxWxX其中：(4)一個(gè)完整N=8的按時(shí)間抽取FFT的運(yùn)算流圖x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12/0NNNWW其中旋轉(zhuǎn)因子，共有m=0m=1m=2x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x

13、5(1)x6(1)x6(0)3 按時(shí)間抽取FFT算法的特點(diǎn)算法特點(diǎn)1111( )( )( )( )( )( )rmmmNrmmmNXkXkXj WXjXkXj Wm表示第m級(jí)迭代，k，j表示數(shù)據(jù)所在的行數(shù)180818084,3,2,1WRWRWRWR暫存器x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)=x(0)A(1)=x(1)A(2)=x(2)A(3)=x(3)A(4)=x(4

14、)A(5)=x(5)A(6)=x(6)A(7)=x(7)R1R1R1R1R1R2R1R1R2R2R3R4看出：用原位運(yùn)算結(jié)構(gòu)運(yùn)算后，A(0)A(7)正好順序存放X(0)X(7),可以直接順序輸出。 碼位倒序規(guī)則以N=8為例：01234567000001010011100101110111自然順序二進(jìn)制碼表示碼位倒讀碼位倒置順序00010001011000110101111104261537看出：碼位倒讀后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。2 102( )()x nnn n n2 102()nn n n0 122()nn n n2log22FNNmLN2logFaNLNN222()2()log

15、log2FFmDFTNNNmFFTNNNN2log2頻率抽取基-2FFT算法Decimation-in-Frequency (DIF)N=2M，M將X(k)按k的奇偶分組前，先將輸入x(n)按n的順序分成前后兩半。1/2 1100/2( )( )( )( )NNNnknknkNNNnnn NX kx n Wx n Wx n W/2 1/2 1200( )2NNNnknkNNnnNx n Wx nW/2 1/20( )2NNknkNNnNx nx nWW/2 10( )( 1)2NknkNnNx nx nW 0,1,.,1kN/21NNW k的奇偶將X(k)221krkr0,1,.,/2 1rN

16、/2 120(2 )( )2NnrNnNXrx nx nW/2 1(21)0(21)( )2NnrNnNXrx nx nW/2 1/20( )2NnrNnNx nx nW/2 1/20( )2NnnrNNnNx nx nWW12( )( )2( )( )2nNNx nx nx nNx nx nx nW0,1,.,12Nn 則X(2r)和X(2r+1)分別是x1(n)和x2(n)的 N / 2點(diǎn)DFT，記為X1(k)和X2(k)x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2點(diǎn)DFTN/2點(diǎn)DFTx(0)x(7)x(1)x(2)x(3)x(4

17、)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)1NW0NW2NW3NW311411/2( )( )(/4)( )( )(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn 313414( )(2 )( )( )(21)( )XkXkDFT x nXkXkDFT x n0,1,.,14Nk x3(0)x3(1)-1-1x4(0)x4(1)N/4點(diǎn)DFTN/4點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0

18、)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)0/2NW1/2NW0,1,.,14Nk 525626( )(2 )( )( )(21)( )XkXkDFT x nXkXkDFT x n522622/2( )( )(/4)( )( )(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn 0033223330103322333(0)(0)(0)(1)(0)(1)(4)(1)(0)(1)(0)(1)NXXxWW xxxXXxWW xxxW/4 1133/43/400( )( )( )NlklkNNllXkx l Wx l W0,1k x

19、3(n)，x4(n)，x5(n)，x6(n)，n=0,10044224440104422444(2)(0)(0)(1)(0)(1)(6)(1)(0)(1)(0)(1)NXXxWW xxxXXxWW xxxW/4 1144/44/400( )( )( )NlklkNNllXkx l Wx l W0,1k x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)& DIF與DIT比較1DIF與與DIT兩種算法均為原位運(yùn)算。兩種算法均為原位運(yùn)算。算法是兩種等價(jià)的與次復(fù)加次復(fù)乘FFTDITD

20、IFNaNmNFNF22lglg2& DIF與DIT比較2快速傅里葉逆變換(IFFT)以上所討論的FFT的運(yùn)算方法同樣可用于IDFT的運(yùn)算，簡稱為IFFT。即快速付里葉反變換。從IDFT的定義出發(fā)，可以導(dǎo)出下列二種利用FFT來計(jì)算IFFT的方法。v 利用FFT計(jì)算IFFT的思路1IDFTFFTNWWDFTWnxnxDFTkXWkXNkXIDFTnxnkNnkNNknkNNknkN算法都可以拿來運(yùn)算或頻率抽取抽?。┠敲匆陨嫌懻摰臅r(shí)間（將運(yùn)算結(jié)果都除以改成運(yùn)算中的每個(gè)系數(shù)只要把3)2() 1 ()()()()(1)()(1010v 利用FFT計(jì)算IFFT的思路210*10*10*10)()()(1()(1)()(1)()(1)(NnnkNnkNNknkNNknkNNkWnxkXkXDFTNWkXNnxWkXNnxWkXNnx比較與取共軛再取共軛）對(duì)它取共軛：此為DFT可用FFT程序v 利用FFT計(jì)算IFFT的思路31*01( )( )NnkNkx nXk WN*1*011( )( )( )NnkNkx nXk WDFT XkNN101( )( )NnkNnx nX k WN共軛FFT共軛乘1/ N( )X k*( )Xk( )x n直接調(diào)用FFT子程序計(jì)算IFFT的方法：快速傅里葉的應(yīng)用l快速卷積