第3章離散傅里葉變換2

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

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

3、為基2按時間抽取的FFT算法。也稱為Coolkey-Tukey算法。n其中基數(shù)2-N=2M，M為整數(shù)。若不滿足這個條件，可以人為地加上若干零值（加零補長）使其達到 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中的前半部分點又合成（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值所對應(yīng)的X1(k),X2(k)則完全重復(fù)了前半部分的k值所對應(yīng)的X1(k),X2(k)的值。)()()(212/)2/kXWkXkXWWWWkNkNkNNNkNN后半部分：又（頻域中的N個點頻率成分為：)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN后半部分：前半部分：?結(jié)論：只要求出（0N/2-1）區(qū)間內(nèi)的各個整數(shù)k值所對應(yīng)的X1(k),X2(k)值，即可以求出(0N-1)整個區(qū)間內(nèi)全部X(k)值，這就是FFT能大量節(jié)省計算的關(guān)鍵。v由于N=2L，因此N/2仍為偶數(shù)，可以依照上面方法進一步把每個N/2點子序列，再按輸入n的奇偶分解為兩個

6、N/4點的子序列，按這種方法不斷劃分下去，直到最后剩下的是2點DFT，兩點DFT實際上只是加減運算加減運算。例子：求 N=23=8點FFT變換)()() 2/()()()(2121kXWkXNkXkXWkXkXkNkN12/, 0Nk先將N=8DFT分解成2個4點DFT：可知：時域上：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é)即蝶式計算結(jié)構(gòu)也即為蝶式信號流圖上面頻域頻域中前/后半部分表示式可以用蝶形信號流圖表示。X1(k)X2(k)kNW)()(

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

8、學們自已寫4點DFTx(0)x(2)x(4)x(6)4點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點的DFT)()4/()()()()()()()4/10)()() 12()2()()(62/5262/52242/3142/314/0) 12(2/114/022/1111LXWLXNkXLXWLXkXrxLXWLXNkXLLXWLXWLXWLXkXkXrxkNkNkNkNNLkLNNLLkNDFT）也可分解為：同樣，（同理：，其中（可分解為：c 一個2點的DFT蝶形流圖2點DFT2點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 另一個2點的DFT蝶形流圖2點DFT2點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點）DFT再分解成2個1點的DFT021022120202120230202020231021 , 0; 1 , 0)4()0()4()0() 1 ()4()0()4()0()0()()(2WWknWWWWWxWxWxWxXWxWxWxWxXWnxkXnknknkNnkNnnkN，其中，則這里用到對稱性這是一蝶形結(jié)代入上面流圖可知： 最后剩下兩點DFT,它可分解成兩個一點DFT，但一點DFT就等于輸入信號本身，所以兩點DFT可用一個蝶形結(jié)表示。取x(0)、x(4)為例。b 2個1點的DFT蝶形流圖1點DFTx(0)1點DFTx(4)X3(0)X3(1)02W進

12、一步簡化為蝶形流圖：02WX3(0)X3(1)x(0)x(4)4()0()4()0() 1 ()4()0()4()0()0(023023xxxWxXxxxWxX其中：(4)一個完整N=8的按時間抽取FFT的運算流圖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 按時間抽取FFT算法的特點算法特點1111( )( )( )( )( )( )rmmmNrmmmNXkXkXj WXjXkXj Wm表示第m級迭代，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看出：用原位運算結(jié)構(gòu)運算后，A(0)A(7)正好順序存放X(0)X(7),可以直接順序輸出。 碼位倒序規(guī)則以N=8為例：01234567000001010011100101110111自然順序二進制碼表示碼位倒讀碼位倒置順序00010001011000110101111104261537看出：碼位倒讀后的順序剛好是數(shù)據(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點DFT，記為X1(k)和X2(k)x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2點DFTN/2點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點DFTN/4點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兩種算法均為原位運算。兩種算法均為原位運算。算法是兩種等價的與次復(fù)加次復(fù)乘FFTDITD

20、IFNaNmNFNF22lglg2& DIF與DIT比較2快速傅里葉逆變換(IFFT)以上所討論的FFT的運算方法同樣可用于IDFT的運算，簡稱為IFFT。即快速付里葉反變換。從IDFT的定義出發(fā)，可以導(dǎo)出下列二種利用FFT來計算IFFT的方法。v 利用FFT計算IFFT的思路1IDFTFFTNWWDFTWnxnxDFTkXWkXNkXIDFTnxnkNnkNNknkNNknkN算法都可以拿來運算或頻率抽取抽?。┠敲匆陨嫌懻摰臅r間（將運算結(jié)果都除以改成運算中的每個系數(shù)只要把3)2() 1 ()()()()(1)()(1010v 利用FFT計算IFFT的思路210*10*10*10)()()(1()(1)()(1)()(1)(NnnkNnkNNknkNNknkNNkWnxkXkXDFTNWkXNnxWkXNnxWkXNnx比較與取共軛再取共軛）對它取共軛：此為DFT可用FFT程序v 利用FFT計算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子程序計算IFFT的方法：快速傅里葉的應(yīng)用l快速卷積