數(shù)字信號(hào)處理優(yōu)秀獲獎(jiǎng)?wù)n件第四章PPT

1、4-5線性卷積的FFT算法4-3 DIF的FFT算法4-4 IFFT算法4-2按時(shí)間抽取(DIT)的FFT算法4-1 引言4-14-1引言引言一一.DFT.DFT的計(jì)算工作量的計(jì)算工作量 兩者的差別僅在指數(shù)的符號(hào)和因子1/N. 1, 1 , 0 ,)()(10NkWnxkXNnnkN101, 1 , 0 ,)(1)(NknkNNnWkXNnx 通常x(n)和都是復(fù)數(shù),所以計(jì)算一個(gè) X(k)的值需要N次復(fù)數(shù)乘法運(yùn)算,和 次 復(fù)數(shù)加法運(yùn)算.那么,所有的X(k)就要N2次復(fù) 數(shù)乘法運(yùn)算,N(N-1)次復(fù)數(shù)加法運(yùn)算.當(dāng)N很 大時(shí),運(yùn)算量將是驚人的,如N=1024,則要完 成1048576 次(一百多萬(wàn)

2、次)運(yùn)算.這樣,難以做到實(shí)時(shí)處理.nkNW1N一個(gè)X(k)的值的工作量,如X(1)1210) 1() 2() 1 () 0() 1 (NNNNNWNxWxWxWxX二二.改進(jìn)的途徑改進(jìn)的途徑 1. 的對(duì)稱性和周期性nkNW;,)()()(*NknNkNnNnkNnkNnkNWWWWW.),1( 1),1()2/(2/)(2)()(2kNNkNjNNNnkNnNNkNnkNknNNkNnNWWeWWeWWWWWN得:對(duì)稱性:周期性: 利用上述特性利用上述特性, ,可以將有些項(xiàng)合并可以將有些項(xiàng)合并, ,并并將將DFTDFT分解為短序列分解為短序列, ,從而降低運(yùn)算次數(shù)從而降低運(yùn)算次數(shù), ,提提高運(yùn)

3、算速度高運(yùn)算速度.1965.1965年年, ,庫(kù)利庫(kù)利(cooley)(cooley)和圖基和圖基(Tukey)(Tukey)首先提出首先提出FFTFFT算法算法. .對(duì)于對(duì)于N N點(diǎn)點(diǎn)DFT,DFT,僅需僅需(N/2)log(N/2)log2 2N N 次復(fù)數(shù)乘法運(yùn)算次復(fù)數(shù)乘法運(yùn)算. .例如例如N=1024=2N=1024=21010 時(shí)，時(shí)，需要需要(1024/2)log(1024/2)log2 2 2 21010 =512 =512* *10=512010=5120次。次。5120/1048576=5120/1048576=4.88%4.88% , ,速度提高速度提高2020倍倍4-2

4、4-2 按時(shí)間抽取按時(shí)間抽取(DIT)(DIT)的的FFTFFT算法算法 庫(kù)利庫(kù)利- -圖基算法圖基算法一一. .算法原理算法原理( (基基2FFT)2FFT)( (一一)N/2)N/2點(diǎn)點(diǎn)DFTDFT1.1.先將 按n的奇偶分為兩組作DFT,DFT,設(shè)N=2N=2L L ,不足時(shí),可補(bǔ)些零。這樣有: n為偶數(shù)時(shí): : n為奇數(shù)時(shí): :1, 1 , 0 ),() 12(1, 1 , 0 ),()2(2221NNrrxrxrrxrx10)()()(NnnkNWnxnxDFTkX因此，)(nx由于由于: : 所以所以, ,上式可表示為上式可表示為: :1022102110)12(102101022

5、22)()()12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX(n為偶數(shù)) (n為奇數(shù))222)/(222NNNWeeWjjN)()()()()(211021012222kXWkXWrxWWrxkXkNrrkkNrrkNNNN 其中,2.2.兩點(diǎn)結(jié)論: (1) X (1) X (k),X(k),X (k)(k)均為N/2N/2點(diǎn)的DFTDFT。 (2) X(k)=X(2) X(k)=X (k)+W(k)+W X X (k)(k)只能確定出 X(k)X(k)的k= k= 個(gè)；即前一半的結(jié)果。1 21 2kN1010

6、2210101122222222) 12()()()2()()(NNNNNNNNrrkrrkrrkrrkWrxWrxkXWrxWrxkX1, 1 , 02 N 同理, 這就是說(shuō),X1(k),X2(k)的后一半,分別 等于其前一半的值。3.X(k)3.X(k)的后一半的確定的后一半的確定rkkrNNNWW222)()()()()2(1101)(101122222kXWrxWrxkNXNNNNNrrkkrr由于 （周期性）（周期性）, ,所以:)()2(22kXkNX 可可見,X(k)X(k)的后一半，也完全由X X1 1(k)(k), X X2 2 (k)(k)的前一半所確定。 *N點(diǎn)的DFT可

7、由兩個(gè)N/2點(diǎn)的DFT來(lái)計(jì)算。kNkNNkNWWWWNN22)()2()2()2(212NkXWNkXNkXNkN1, 1 , 0 ),()(221NkNkkXWkX又由于 , ,所以實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算 前一半4.4.蝶形運(yùn)算蝶形運(yùn)算 后一半（N/2個(gè)蝶形)(前一半)(后一半)1 1 11-1-1)()()()()()(2121kXWkXkXkXWkXkXkNkN)1,()1, 1 ,0(22 N Nk kk kN NN N)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW由X1(k)、X 2(k)表示X(k)的運(yùn)算是一種特殊的運(yùn)算-

8、碟形運(yùn)算(1)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):復(fù)加次數(shù):(2)兩個(gè)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):復(fù)加次數(shù): (3)N/2個(gè)蝶形運(yùn)算的運(yùn)算量:復(fù)乘次數(shù):復(fù)加次數(shù): : 5. .計(jì)算工作量分析計(jì)算工作量分析復(fù)乘:復(fù)加:4)2(22NN)12(2NN22N)12(NN2NNN222)12(2NNNN22222NNN總共運(yùn)算量:按奇、偶分組后的計(jì)算量： *但是,N N點(diǎn)DFTDFT的復(fù)乘為N N2 2 ; ;復(fù)加N(N-1);N(N-1);與分解后相比可知,計(jì)算工作點(diǎn)差不多減少 一半。 例如 N=8N=8 時(shí)的DFT,DFT,可以分解為兩個(gè) N/2=4N/2=4點(diǎn)的DFTDFT.具體方法如下:

9、: (1)n(1)n為偶數(shù)時(shí),即 分別記作: : )(42/1kXDFTN，得點(diǎn)的進(jìn)行3 , 2 , 1 , 0)2()()(30430411kWrxWrxkXrrkrrk);6()3(),4()2(),2()1(),0()0(1111xxxxxxxx);6(),4(),2(),0(xxxx (2) n (2) n為奇數(shù)時(shí),分別記作:);7()3(),5()2(),3()1(),1()0(2222xxxxxxxx3 , 2 , 1 , 0) 12()()(30430422kWrxWrxkXrrkrrk)(42/2kXDFTN，得點(diǎn)的進(jìn)行3 , 2 , 1 , 0),()() 4()()()(2

10、121kkXWkXkXkXWkXkXkNkN x1 1(0)=(0)=x(0) (0) x1(1)=(1)=x(2) (2) N/2N/2點(diǎn)點(diǎn) x1(2)=(2)=x(4) DFT (4) DFT x1(3)=(3)=x(6) (6) x2(0)=(0)=x(1) (1) x2(1)=(1)=x(3) (3) N/2N/2點(diǎn)點(diǎn) x2(2)=(2)=x(5) (5) DFT DFT x2(3)=(3)=x(7)(7) 1 2 X X1(0)(0)X X1(1)(1)X X1(2)(2)X X1(3)(3)X X2(0)(0)X X2(1)(1)X X2(2)(2)X X2(3)(3)WN2WN1

11、WN0WN3-1-1-1-1X(0)X(0)X(1)X(1)X(2)X(2)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)(3)(3)對(duì)X X (k)(k)和X X (k)(k)進(jìn)行蝶形運(yùn)算,前半部為 X(0) X(3),X(0) X(3),后半部分為X(4) X(7)X(4) X(7) 整個(gè)過(guò)程如下圖所示: 由于N=2N=2 L , ,所以 N/2N/2仍為偶數(shù),可以進(jìn) 一步把每個(gè)N/2N/2點(diǎn)的序列再按其奇偶部分 分解為兩個(gè)N/4N/4的子序列。例如，n為偶數(shù)時(shí)的 N/2N/2點(diǎn)分解為:( (二二) N/4) N/4點(diǎn)點(diǎn)DFTDFT1, 1 , 0),()

12、2(431Nlxlx1, 1 , 0),() 12(441Nlxlx進(jìn)行N/4N/4點(diǎn)的DFTDFT,得到klNllkNllkNllkNlWlxWlxkXWlxWlxkXNNNN) 12(2/1014/104422/1014/1033) 12()()()2()()(4444( (偶中偶) )( (偶中奇) )()()(4312kXWkXkXkN1, 1 , 04Nk從而可得到前N/4的X1(k)()()4(4312kXWkXkNXkN后N/4的X1(k)為1, 1 , 04Nk( (奇中偶奇中偶) )104/64/1026104/5104/254444)()12()()()2()(NNNNll

13、kNlkNlllkNllkNWlxWlxkXWlxWlxkX( (奇中奇奇中奇) )同樣對(duì)n n為奇數(shù)時(shí)，N/2N/2點(diǎn)分為兩個(gè)N/4N/4點(diǎn) 的序列進(jìn)行DFT，則有:14, 1 , 0k; (k)XW(k) X(k) X6kN/252N14, 1 , 0k; (k)XW(k) Xk)4N( X6kN/252N進(jìn)行碟形運(yùn)算，得：、由)()(65kXkX 例如,N=8N=8時(shí)的DFTDFT可分解為四個(gè)N/4N/4的DFT,DFT, 具體步驟如下: :)4()2() 1 ()0()0()0()()()(131313xxxxxxnxrxlx(1) 將原序列x(n)的“偶中偶”部分:構(gòu)成N/4點(diǎn)DFT

14、，從而得到X3(0), X3(1)。)6()3()1()2()1()0()()()(141414xxxxxxnxrxlx(2) 將原序列x(n)的“偶中奇”部分:構(gòu)成N/4點(diǎn)DFT，從而得到X4(0), X4(1)。(3) 將原序列x(n)的“奇中偶”部分:)5()2()1()1()0()0()()()(252525xxxxxxnxrxlx構(gòu)成N/4點(diǎn)DFT，從而得到X5(0), X5(1)。(4) 將原序列x(n)的“奇中奇”部分:)7()3()1()3()1()0()()()(262626xxxxxxnxrxlx構(gòu)成N/4點(diǎn)DFT，從而得到X6(0), X6(1)。（5）由 X3(0),

15、X3(1), X4(0), X4(1)進(jìn)行碟形運(yùn)算, 得到X1(0), X1(1), X1(2), X1(3)。（6）由 X5(0), X5(1), X6(0), X6(1)進(jìn)行碟形運(yùn)算, 得到X2(0), X2(1), X2(2), X2(3)。 (0)= (0)= (0) N/4 (1)= (2)= (4) DFT (0)= (1)= (2) N/4 (1)= (3)= (6) DFT (0)= (0)= (1) N/4 (1)= (2)= (5) DFT (0)= (1)= (3) N/4 (1)= (3)= (7) DFT3 13 14 14 15 25 26 26 2 02NN02N

16、NWWWW0123NNNN-1-1-1-2-1-1WWWWX (0)X (1)X (0)X (1)X (0)X (1)X (0)X (1)33445566X (0)X (1)X (2)X (3)X (0)X (1)X (2)X (3)11122221X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)xxxxxxxxxxxxxxxxxxxxxxxx（7）由X1(0), X1(1), X1(2), X1(3)，X2(0), X2(1),X2(2), X2(3)進(jìn)行碟形運(yùn)算, 得到 X(0), X(1), X(2), X(3) X(4), X(5), X(6), X(7) 。 這樣,又

17、一次分解,得到四個(gè)N/4N/4點(diǎn)DFT,DFT, 兩級(jí)蝶形運(yùn)算,其運(yùn)算量有大約減少一半 即為N N點(diǎn)DFTDFT的1/41/4。 對(duì)于N=8N=8時(shí)DFT,N/4DFT,N/4點(diǎn)即為兩點(diǎn)DFT,DFT,因此 0,1k ,)()(0,1k ,)()(0,1k ,)()(0,1k ,)()(4/1066104/55104/44104/33lkNlllkNllkNllkNWlxkXWlxkXWlxkXWlxkX 亦即, )4()0() 1 ()0() 1 ()4()0() 1 ()0()0(031233030233xWxxWxXxWxxWxXNN)6()2() 1 ()0() 1 ()6()2()

18、1 ()0()0(041244040244xWxxWxXxWxxWxXNN) 5() 1 () 1 ()0() 1 () 5() 1 () 1 ()0()0(051255050255xWxxWxXxWxxWxXNN)7() 3() 1 ()0() 1 ()7() 3() 1 ()0()0(061266060266xWxxWxXxWxxWxXNN (0) (4) (2) (6) (1) (5) (3) (7)WN0WN0WN0W0N-1-1-1-1X (0)X (1)X (0)X (1)X (0)X (1)X (0)X (1)33445566WN0WN2WN0WN2-1-1-1-1X (0)X

19、(1)X (2)X (3)X (0)X (1)X (2)X (3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)xxxxxxxx因此,8點(diǎn)DFT的FFT的運(yùn)算流圖如下 這種FFTFFT算法,是在時(shí)間上對(duì)輸入序列 的次序是屬于偶數(shù)還是屬于奇數(shù)來(lái)進(jìn)行分 解的,所以稱作按時(shí)間抽取的算法 。 二二. .運(yùn)算量運(yùn)算量 由上述分析可知,N=8N=8需三級(jí)蝶形運(yùn)算 N=2 =8,N=2 =8,由此可知,N=2N=2L L 共需L L級(jí)蝶形運(yùn)算, 而且每級(jí)都由N/2N/2個(gè)蝶形運(yùn)算 組成,每個(gè)蝶 形運(yùn)算有一次復(fù)乘,兩次復(fù)加。( (DIT

20、DIT) )3 3 因此,N N點(diǎn)的FFTFFT的運(yùn)算量為復(fù)乘: m mF F = =（N/2N/2）L=L=（N/N/2） loglog2 2 N N復(fù)加: a aF F =N L=N log =N L=N log2 2 N N 由于計(jì)算機(jī)的乘法運(yùn)算比加法運(yùn)算所 需的時(shí)間多得多，故以乘法作為比較基準(zhǔn).如表4-1-1所示(pp.145）。 (0)=(0)=X X0 0(0)(0) X X1 1(0)(0) X X2 2(0) X(0) X3 3(0)(0)=X(0) =X(0) (4)=(4)=X X0 0(1)(1) X X1 1(1) X(1) X2 2(1) X(1) X3 3(1)(1

21、)=X(1)=X(1) (2)=(2)=X X0 0(2)(2) X X3 3(2)(2)=X(2)=X(2) (6)=(6)=X X0 0(3)(3) X X3 3(3)(3)=X(3)=X(3) (1)=(1)=X X0 0(4)(4) X X1 1(4) X(4) X2 2(4) X(4) X3 3(4)(4)=X(4)=X(4) (5)=(5)=X X0 0(5)(5) X X3 3(5)(5)=X(5)=X(5) (3)=(3)=X X0 0(6)(6) X X3 3(6)(6)=X(6)=X(6) (7)=(7)=X X0 0(7)(7) X X1 1(7) X(7) X2 2(7

22、) X(7) X3 3(7)(7)=X(7)=X(7)WWWWN0N0N0N0-1-1-1-1WWWWN0N2N0N2-1-1-1-1WWWWNNNN0123.三三.DIT.DIT的的FFTFFT算法的特點(diǎn)算法的特點(diǎn) 1.1.原位運(yùn)算輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲(chǔ)器。xxxxxxxxrNmmmrNmmmWjXkXjXWjXkXkX)()()()()()(1111),3()6(),2()2(),1 ()4(),0()0(0000XxXxXxXx).7()7(),6()3(),5()5(),4() 1 (0000XxXxXxXx 設(shè)用m(m=1,2, ,L)表示第m列; ;用用k,j

23、k,j表示蝶形輸入數(shù)據(jù)所在的（上/下）行數(shù)(0,1,2, ,N-1);(0,1,2, ,N-1);這時(shí)任何一個(gè)蝶形運(yùn)算可用下面通用式表示， 即 由運(yùn)算流圖可知,一共有N N個(gè)輸入個(gè)輸入/ /出出行,一共有l(wèi)oglog2 2 N=LN=L列（級(jí)）蝶形運(yùn)算( (基本迭代運(yùn)算). ). 所以,當(dāng)m=1時(shí)時(shí), ,則有（前兩個(gè)蝶形） 00010001)1()0()1()1()0()0(NNWXXXWXXX00010001)3()2()3()3()2()2(NNWXXXWXXX 當(dāng)m=2時(shí),則有（前兩個(gè)蝶形） 當(dāng)m=3時(shí),則有（前兩個(gè)蝶形） 2112211201120112)3()1()3()3()1()

24、1()2()0()2()2()0()0(NNNNWXXXWXXXWXXXWXXX1223122302230223)5()1()5()5()1()1()4()0()4()4()0()0(NNNNWXXXWXXXWXXXWXXX 可見,在某列進(jìn)行蝶形運(yùn)算的任意兩個(gè)節(jié)點(diǎn)( (行)k)k和j j的節(jié)點(diǎn)變量 就完全可以確定蝶形運(yùn)算的結(jié)果 ,與其它行( (節(jié)點(diǎn)) )無(wú)關(guān)。 這樣,蝶形運(yùn)算的兩個(gè)輸出值仍可放回蝶形運(yùn)算的兩個(gè)輸入所在的存儲(chǔ)器中,即實(shí)現(xiàn)所謂原位運(yùn)算。每一組( (列) )有N/2N/2個(gè)蝶形運(yùn)算,所以只需N N個(gè)存儲(chǔ)單元，可以節(jié) 省存儲(chǔ)單元。)(),(jXkXmm)(),(11jXkXmm 2 2

25、 倒位序規(guī)律倒位序規(guī)律 由圖可知,輸出X X(k)(k)按正常順序排列在存儲(chǔ)單元,而輸入是按順序: 這種順序稱作倒位序,即二進(jìn)制數(shù)倒位。）；）；7 (),3 (),5 (),1 (6 (),2(),4(),0 (xxxxxxxxn =00n =10n =01n =11n =01n =1101010101 x xx xx xx xx xx xx xx x),(012nnnx(n2)x(000) 0 乾x(100) 4 兌x(010) 2 離x(110) 6 震x(001) 1巽x(101) 5 坎x(011) 3 艮x(111) 7 坤（偶）（奇） 這是由奇偶分組造成的,以N=8N=8為例 說(shuō)明

26、如下: 3.3.倒位序?qū)崿F(xiàn)倒位序?qū)崿F(xiàn) 輸入序列先按自然順序存入存儲(chǔ)單 元,然后經(jīng)變址運(yùn)算來(lái)實(shí)現(xiàn)倒位序排列 設(shè)輸入序列的序號(hào)為n n,二進(jìn)制為 (n2 n1 n0 )2 , ,倒位序順序用 表示,其倒位序二進(jìn)制為(n0 n1 n2 )2 , ,例如 ，N=8N=8時(shí)如下表： n 0 00 0 0 0 0 00 0 0 0 0 0 0 0 1 01 0 0 0 1 11 1 0 0 0 4 0 4 2 02 0 1 1 0 00 0 1 1 0 2 0 2 3 03 0 1 1 1 11 1 1 1 0 6 0 6 4 14 1 0 0 0 00 0 0 0 1 1 1 1 5 15 1 0 0

27、1 11 1 0 0 1 5 1 5 6 16 1 1 1 0 00 0 1 1 1 3 1 3 7 17 1 1 1 1 11 1 1 1 1 7 1 7 自然順序n n 二進(jìn)制n n n n n n 倒位序二進(jìn)制n n n n n n 倒位順序n n2 1 0 0 1 2A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8)x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7)變址處理方法變址處理方法存儲(chǔ)單元自然順序變址倒位序4.4.蝶形運(yùn)算兩節(jié)點(diǎn)的距離蝶形運(yùn)算兩節(jié)

28、點(diǎn)的距離: :2m-1 其中,m表示第m列, ,且且m =1, ,L=1, ,L 例如N=8=2N=8=23 3 , ,第一級(jí)( (列) )距離為2 21-11-1=1,=1, 第二級(jí)( (列) )距離為2 22-12-1=2=2， 第三級(jí)( (列) )距離為2 23-13-1=4=4。5.WNr 的確定(僅給出方法) ) 考慮蝶形運(yùn)算兩節(jié)點(diǎn)的距離為2m-1 , ,蝶 形運(yùn)算可表為 Xm(k)=Xm-1(k)+Xm-1(k+2m-1)WNr Xm(k+2m-1)=Xm-1(k)-Xm-1(k+2m-1)WNr 由于N N為已知,所以將r r的值確定即可。 為此，令k=(n2n1n0)2 , ,

29、再再將k= (n2n1n0)2 左移(L-m)位,右邊位置補(bǔ)零,就可得到(r)2 的值，即(r)2 =(k)22L-m 。 例如 N=8=2N=8=23 3 (1) (1)k=2 , m=3 的r r值,k=2=(010)2 左移L-m=3-3=0 , r=(010)2=2; (2)k=3 ,m=3 的r r值; ; k= 3=(011)2,左移0位,r=3r=3； (3)(3)k=5 ,m=2的值; ; k=5=(101)2 左移L-m=1=1位 r=(010)2 =2。 6 6.存儲(chǔ)單元 存輸入序列 (n),n=0,1, ,N-1, (n),n=0,1, ,N-1, 計(jì)N N 個(gè)單元; ;

30、 存放系數(shù) , r=0,1, , r=0,1, ,（N/2N/2）-1,-1, 需N/2N/2個(gè)存儲(chǔ)單元； 共計(jì)(N+N/2)個(gè)存儲(chǔ)單元。xr rN NW W4-3 DIF4-3 DIF的的FFTFFT算法算法( (桑德桑德圖基算法圖基算法) ) 一一. .算法原理算法原理 1.N1.N點(diǎn)DFTDFT的另一種表達(dá)形式10)()(NnnkNWnxkX10)(1012/102222)2()()()(NNNNnknNnnkNNNnnkNnnkNWNnxWnxWnxWnx 由于 故 因此 X(k)可表為 nkNnkNWWNnxnxNN1022)2()(, 12jNeWNkkNNW) 1(2nkNnkW

31、NnxnxkXN102)2() 1()()(1, 1 , 0Nk 2.N點(diǎn)DFT按k的奇偶分組可分為兩個(gè)N/2的DFT 當(dāng)k k為偶數(shù),即 k=2rk=2r時(shí),(-1)k =1； 當(dāng)k k為奇數(shù),即 k=2r+1 k=2r+1 時(shí) (-1)k =-1 。 這時(shí) X(k)X(k) 可分為兩部分： nrnnrNnNNNWNnxnxWNnxnx22210210)2()()2()()2( rXr1, 1 , 02Nrk k為偶數(shù)時(shí)： 可見,上面兩式均為N/2N/2的DFTDFT。nrnnNrnNnNNNWWNnxnxWNnxnxrX22210)12(10)2()()2()() 12(xxk k為奇數(shù)時(shí)

32、：1, 1 , 02Nr-1-1)2()(Nnxnx1, 1 ,02NnnNWNnxnx)2()(3.3.蝶形運(yùn)算進(jìn)行如下碟形運(yùn)算：和)2()(NnxnxnNW)2(Nnx)(nx-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 34.N=84.N=8時(shí)時(shí), ,按按k k的奇偶分解過(guò)程的奇偶分解過(guò)程 先蝶形運(yùn)算，后先蝶形運(yùn)算，后DFT:DFT:)0( x) 1 ( x)5( x)4( x) 3( x)2( x)7( x)6( x)0(X)2(X)6(X) 1 (X) 3(X)5(X)7(X)4(XDFTN點(diǎn)2DFTN點(diǎn)2 5.5.仿照DITD

33、IT的方法 再將N/2N/2點(diǎn)DFTDFT按k k的奇偶分解為兩個(gè)N/4N/4點(diǎn)的DFTDFT,如此進(jìn)行下去,直至分解為2 2點(diǎn)DFTDFT。 (0) X(0) (0) X(0) (1) X(4) (1) X(4) (2) X(2) (2) X(2) (3) X(6) (3) X(6) (4) X(1) (4) X(1) (5) X(5) (5) X(5) (6) X(3) (6) X(3) (7) X(7) (7) X(7)-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 3-1-1-1-1-1-1-1-1W WW WW WW WN NN

34、NN NN N0 02 20 02 2-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 00 00 00 0 xxxxxxxx例如 N=8N=8時(shí)DIFDIF的FFTFFT流圖如下： 二二.原位運(yùn)算原位運(yùn)算 每級(jí)(列)都是由N/2N/2個(gè)蝶形運(yùn)算構(gòu) 成,即 -1-1W WN Nr rrNmmmmmmWjXkXjXjXkXkX)()()()()()(1111)(1kXm)(1jXm)()()(11jXkXkXmmmrNmmmWjXkXjX)()()(11三三.蝶形運(yùn)算兩節(jié)點(diǎn)的距離蝶形運(yùn)算兩節(jié)點(diǎn)的距離 一般公式為2L-m =N/2m 例如 N=2N=23 3 =8

35、 =8 ： (1)(1)m=1 時(shí)的距離為 8/2=48/2=4； (2) (2)m=2 時(shí)的距離為 8/4=2;8/4=2; (3) (3)m=3 時(shí)的距離為 8/8=18/8=1。r r的求法的求法： k=(n2 n1 n0 ) , ,左移m-1位, ,右邊空出補(bǔ)零, ,得(r)(r)2 2 , ,亦即(r)(r)2 2 =(k) =(k)2 2 2m-1 . .例如,N=8:,N=8:(1)m=1,k=2, k=(010)(1)m=1,k=2, k=(010)2 2 左移0位,(r),(r)2 2=(010)=(010)2 2=2;=2;(2)m=2,k=1, k=(001)(2)m=2

36、,k=1, k=(001)2 2 左移1 1位,(r),(r)2 2=(010)=(010)2 2=2;=2;(3)m=2,k=5, k=(101)(3)m=2,k=5, k=(101)2 2 左移1 1位,(r),(r)2 2=(010)=(010)2 2=2 .=2 .rNmmmmmmmmmWNkXkXNkXNkXkXkX)2()()2()2()()(1111四四. . 的計(jì)算的計(jì)算 由于DIFDIF蝶形運(yùn)算的兩節(jié)點(diǎn)的距離為 N/2m , , 所以蝶形運(yùn)算可表為：rNW 1. 1.相同點(diǎn) (1)(1)進(jìn)行原位運(yùn)算； (2)(2)運(yùn)算量相同, ,均為（N/2) Log2N次復(fù)乘, ,N Lo

37、g2N次復(fù)加。 2.2.不同點(diǎn) (1)DIT(1)DIT輸入為倒位序,輸出為自然順序； DIFDIF正好與此相反。但DITDIT也有輸入為自然順序,輸出為倒位序的情況。五五.DIFDIF法與法與DITDIT法的異同法的異同rNmmmWjXkXjX)()()(11rNmmmWjXkXkX)()()(11)(1kXm)(1jXmrNW1(2)(2)蝶形運(yùn)算不同a.a.(DIT)(DIT)用矩陣表示)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11rNmmmWjXkXjX)()()(11)()()(11jXkXkXmmm)(1kXm)(1jXmrNW1b.b.(DFT)(DFT)用矩陣表示)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11(3)(3)兩種蝶形運(yùn)算的關(guān)系 互為轉(zhuǎn)置（矩陣）； 將流圖的所有支路方向都反向, ,交換輸入和輸出，即可得到另一種蝶形。 a.a.(DIT)(DIT)b.b.(DFT)(DFT)rNWrNW1111rNWrNW 4-4 IFFT4-4 IFFT算法算法一一.稍微變動(dòng)稍微變動(dòng)FFT程序和參數(shù)可實(shí)現(xiàn)程序和參數(shù)可實(shí)現(xiàn)IFFT nkNNkNnnkNWkXNkXIDFTnxWnxnxDFTkX1010)(1)()()()()( 比較兩式可知,