線性卷積的FFT算法學習教案

1、會計學1線性卷積的線性卷積的FFT算法算法(sun f)第一頁，共87頁。1, 1 , 0 ,)()(10NkWnxkXNnnkN101, 1 , 0 ,)(1)(NknkNNnWkXNnx第2頁/共87頁第二頁，共87頁。成1048576 次(一百多萬次)運算.這樣,難以做到實時處理.nkNW1N一個(y )X(k)的值的計算量,如X(1)1210) 1() 2() 1 () 0() 1 (NNNNNWNxWxWxWxX第3頁/共87頁第三頁，共87頁。nkNW;)()()()(*NknNkNnNnkNkNNkNkNkNWWWWWorWW.),1( 1),1()2/(2/)(2)()(2kN

2、NkNjNNNnkNnNNkNnkNknNNkNnNWWeWWeWWWWWN得:對稱性:周期性:第4頁/共87頁第四頁，共87頁。第5頁/共87頁第五頁，共87頁。1, 1 , 0 ),() 12(1, 1 , 0 ),()2(2221NNrrxrxrrxrx10)()()(NnnkNWnxnxDFTkX因此(ync)，)(nx第6頁/共87頁第六頁，共87頁。NoImage1022102110)12(10210102222)()() 12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX(n為偶數(shù)(u sh) (n為

3、奇數(shù))222)/(222NNNWeeWjjN)()()()()(211021012222kXWkXWrxWWrxkXkNrrkkNrrkNNNN第7頁/共87頁第七頁，共87頁。1 21 2kN10102210101122222222) 12()()()2()()(NNNNNNNNrrkrrkrrkrrkWrxWrxkXWrxWrxkX1, 1 , 02 N第8頁/共87頁第八頁，共87頁。rkkrNNNWW222)()()()()2(1101)(101122222kXWrxWrxkNXNNNNNrrkkrr由于(yuy) （周期性）,所以:)()2(22kXkNX第9頁/共87頁第九頁，共8

4、7頁。kNkNNkNWWWWNN22)()2()2()2(212NkXWNkXNkXNkN1, 1 , 0 ),()(221NkNkkXWkX又由于(yuy) ,所以第10頁/共87頁第十頁，共87頁。 前一半前一半(ybn)(ybn)4.4.蝶形運算蝶形運算(yn sun)(yn sun) 后一半（N/2個蝶形)(前一半)(后一半)1 1 11-1-1)()()()()()(2121kXWkXkXkXWkXkXkNkN)1,()1, 1 , 0(22 N Nk kk kN NN N)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW由X1(k)、

5、X 2(k)表示X(k)的運算是一種特殊的運算-碟形運算第11頁/共87頁第十一頁，共87頁。5.計算(j sun)量分析復乘:復加:4)2(22NN)12(2NN22N)12(NN2NNN222)12(2NNNN22222NNN總共(znggng)運算量:按奇、偶分組后的計算量： *但是,N N點DFTDFT的復乘為N N2 2 ; ;復加N(N-1);N(N-1);與分解后相比可知,計算工作點差不多減少 一半。第12頁/共87頁第十二頁，共87頁。)(42/1kXDFTN，得點的進行3 , 2 , 1 , 0)2 ()()(30430411kWrxWrxkXrrkrrk);6()3(),4

6、()2(),2()1(),0()0(1111xxxxxxxx);6(),4(),2(),0(xxxx第13頁/共87頁第十三頁，共87頁。);7()3(),5()2(),3()1(),1()0(2222xxxxxxxx3 , 2 , 1 , 0) 12()()(30430422kWrxWrxkXrrkrrk)(42/2kXDFTN，得點的進行3 , 2 , 1 , 0),()() 4()()()(2121kkXWkXkXkXWkXkXkNkN第14頁/共87頁第十四頁，共87頁。1 2 X X1(0)(0)X X1(1)(1)X X1(2)(2)X X1(3)(3)X X2(0)(0)X X2

7、(1)(1)X X2(2)(2)X X2(3)(3)WN2WN1WN0WN3-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)第15頁/共87頁第十五頁，共87頁。( (二二) N/4) N/4點點DFTDFT1, 1 , 0),()2(431Nlxlx1, 1 , 0),() 12(441Nlxlx進行(jnxng)N/4點的DFT,得到klNllkNllkNllkNlWlxWlxkXWlxWlxkXNNNN) 12(2/1014/104422/1014/1033) 12()()()2()()(44

8、44( (偶中偶) )( (偶中奇) )第16頁/共87頁第十六頁，共87頁。)()()(4312kXWkXkXkN1, 1 , 04Nk從而(cng r)可得到前N/4的X1(k)()()4(4312kXWkXkNXkN后N/4的X1(k)為1, 1 , 04Nk第17頁/共87頁第十七頁，共87頁。( (奇中偶奇中偶) )104/64/1026104/5104/254444)() 12()()()2()(NNNNllkNlkNlllkNllkNWlxWlxkXWlxWlxkX( (奇中奇奇中奇) )同樣對n為奇數(shù)(j sh)時，N/2點分為兩個N/4點 的序列進行DFT，則有:14, 1

9、, 0k; (k)XW(k) X(k) X6kN/252N14, 1 , 0k; (k)XW(k) Xk)4N( X6kN/252N進行碟形運算，得：、由)()(65kXkX第18頁/共87頁第十八頁，共87頁。 例如(lr),N=8時的DFT可分解為四個N/4的DFT, 具體步驟如下:)4()2() 1 ()0()0()0()()()(131313xxxxxxnxrxlx(1) 將原序列(xli)x(n)的“偶中偶”部分:構(gòu)成N/4點DFT，從而(cng r)得到X3(0), X3(1)。第19頁/共87頁第十九頁，共87頁。)6()3()1()2()1()0()()()(141414xxx

10、xxxnxrxlx(2) 將原序列(xli)x(n)的“偶中奇”部分:構(gòu)成N/4點DFT，從而(cng r)得到X4(0), X4(1)。(3) 將原序列(xli)x(n)的“奇中偶”部分:)5()2()1()1()0()0()()()(252525xxxxxxnxrxlx構(gòu)成N/4點DFT，從而得到X5(0), X5(1)。第20頁/共87頁第二十頁，共87頁。(4) 將原序列(xli)x(n)的“奇中奇”部分:)7()3()1()3()1()0()()()(262626xxxxxxnxrxlx構(gòu)成N/4點DFT，從而(cng r)得到X6(0), X6(1)。（5）由 X3(0), X3(

11、1), X4(0), X4(1)進行(jnxng)碟形運算, 得到X1(0), X1(1), X1(2), X1(3)。（6）由 X5(0), X5(1), X6(0), X6(1)進行碟形運算, 得到X2(0), X2(1), X2(2), X2(3)。第21頁/共87頁第二十一頁，共87頁。3 13 14 14 15 25 26 26 2 02NN02NNWWWW0123NNNN-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)111

12、22221X(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)進行碟形運算(yn sun), 得到 X(0), X(1), X(2), X(3) X(4), X(5), X(6), X(7) 。第22頁/共87頁第二十二頁，共87頁。0,1k ,)()(0,1k ,)()(0,1k ,)()(0,1k ,)()(4/1066104/55104/44104/33lkNlllkNllkNllkNWlxkXWlxkXWlxkXWl

13、xkX第23頁/共87頁第二十三頁，共87頁。)4()0() 1 ()0() 1 ()4()0() 1 ()0()0(031233030233xWxxWxXxWxxWxXNN)6()2() 1 ()0() 1 ()6()2() 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第24頁/共87頁第二十四頁，

14、共87頁。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 (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第25頁/共87頁第二十五頁，共87頁。成,每個蝶形運算有一次復乘,兩次復加。( (DITDIT) )3 3第26頁/共87頁第二十六頁，共87頁。第27頁/共87頁第二十七頁，共87頁。WWWWN

15、0N0N0N0-1-1-1-1WWWWN0N2N0N2-1-1-1-1WWWWNNNN0123.輸入數(shù)據(jù)(shj)、中間運算結(jié)果和最后輸出均用同一存儲器。xxxxxxxx第28頁/共87頁第二十八頁，共87頁。rNmmmrNmmmWjXkXjXWjXkXkX)()()()()()(1111),3()6(),2()2(),1 ()4(),0()0(0000XxXxXxXx).7()7(),6()3(),5()5(),4() 1 (0000XxXxXxXx 設用m(m=1,2, ,L)表示(biosh)第m列;用k,j表示(biosh)蝶形輸入數(shù)據(jù)所在的（上/下）行數(shù)(0,1,2, ,N-1);這

16、時任何一個蝶形運算可用下面通用式表示(biosh)， 即 由運算流圖可知,一共(ygng)有N個輸入/出行,一共(ygng)有l(wèi)og2 N=L列（級）蝶形運算(基本迭代運算). 第29頁/共87頁第二十九頁，共87頁。00010001)1()0()1()1()0()0(NNWXXXWXXX00010001)3()2()3()3()2()2(NNWXXXWXXX第30頁/共87頁第三十頁，共87頁。2112211201120112)3()1()3()3()1()1()2()0()2()2()0()0(NNNNWXXXWXXXWXXXWXXX1223122302230223)5()1()5()5(

17、)1()1()4()0()4()4()0()0(NNNNWXXXWXXXWXXXWXXX第31頁/共87頁第三十一頁，共87頁。)(),(jXkXmm)(),(11jXkXmm第32頁/共87頁第三十二頁，共87頁。）；）；7 (),3 (),5 (),1 (6 (),2 (),4 (),0 (xxxxxxxx第33頁/共87頁第三十三頁，共87頁。n =00n =10n =01n =11n =01n =1101010101 ),(012nnnx(n2)x(000) 0 x(100) 4 x(010) 2 x(110) 6 x(001) 1x(101) 5 x(011) 3 x(111) 7（

18、偶）（奇） 這是由奇偶分組造成的,以N=8為例 說明(shumng)如下:第34頁/共87頁第三十四頁，共87頁。n 第35頁/共87頁第三十五頁，共87頁。自然(zrn)順序n 二進制n n n 倒位序二進制n n n 倒位順序n2 1 0 0 1 2第36頁/共87頁第三十六頁，共87頁。A(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)變址處理變址處理(chl)方法方法存儲單元(cn ch dn yun)自

19、然(zrn)順序變址倒位序4.4.蝶形運算兩節(jié)點的距離蝶形運算兩節(jié)點的距離: :2m-1 其中,m表示第m列, ,且且m =1,=1, ,L ,L 例如N=8=2N=8=23 3 , ,第一級( (列) )距離為2 21-11-1=1,=1, 第二級( (列) )距離為2 22-12-1=2=2， 第三級( (列) )距離為2 23-13-1=4=4。第37頁/共87頁第三十七頁，共87頁。第38頁/共87頁第三十八頁，共87頁。 為此，令k=(n2n1n0)2 ,再將k= (n2n1n0)2 左移(M-m)位,右邊(yu bian)位置補零,就可得到(r)2 的值，即 (r)2 =(k)2

20、2L-m 。 第39頁/共87頁第三十九頁，共87頁。第40頁/共87頁第四十頁，共87頁。xr rN NW W第41頁/共87頁第四十一頁，共87頁。頻率頻率(pnl)(pnl)抽取抽取FFTFFT算法算法( (桑德桑德圖基算法圖基算法) )10)()(NnnkNWnxkX10)(1012/102222)2()()()(NNNNnknNnnkNNNnnkNnnkNWNnxWnxWnxWnx第42頁/共87頁第四十二頁，共87頁。nkNnkNWWNnxnxNN1022)2()(, 12jNeWNkkNNW) 1(2nkNnkWNnxnxkXN102)2() 1()()(1, 1 , 0Nk第4

21、3頁/共87頁第四十三頁，共87頁。nrnnrNnNNNWNnxnxWNnxnx22210210)2()()2()()2( rXr1, 1 , 02Nrk k為偶數(shù)為偶數(shù)(u sh)(u sh)時：時：第44頁/共87頁第四十四頁，共87頁。nrnnNrnNnNNNWWNnxnxWNnxnxrX22210)12(10)2()()2()() 12(xxk k為奇數(shù)為奇數(shù)(j sh)(j sh)時：時：1, 1 , 02Nr第45頁/共87頁第四十五頁，共87頁。-1-1)2()(Nnxnx1, 1 , 02NnnNWNnxnx)2()(3.3.蝶形運算蝶形運算(yn (yn sun)sun)進行

22、如下碟形運算：和)2()(NnxnxnNW)2(Nnx)(nx第46頁/共87頁第四十六頁，共87頁。-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 34 . N = 84 . N = 8 時時 , , 按按 k k 的 奇 偶 分 解的 奇 偶 分 解(fnji)(fnji)過程過程 先蝶形運算，后先蝶形運算，后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點2DFTN點2第47頁/共87頁第四十七頁，共87頁。

23、第48頁/共87頁第四十八頁，共87頁。-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 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例如(lr) N=8時DIF的FFT流圖如下：第49頁/共87頁第四十九頁，共87頁。 -1-1W WN Nr rrNmmmmmmWjXkXjXjXkXkX)()()()()()(1111)(1kXm)(1jXm)()()(11j

24、XkXkXmmmrNmmmWjXkXjX)()()(11第50頁/共87頁第五十頁，共87頁。三三.蝶形運算兩節(jié)點蝶形運算兩節(jié)點(ji din)的距離的距離第51頁/共87頁第五十一頁，共87頁。rNmmmmmmmmmWNkXkXNkXNkXkXkX)2()()2()2()()(1111四四. . 的計算的計算 由于由于DIFDIF蝶形運算的兩節(jié)點的距離蝶形運算的兩節(jié)點的距離(jl)(jl)為為 N/2m ,N/2m , 所以蝶形運算可表為：所以蝶形運算可表為：rNW第52頁/共87頁第五十二頁，共87頁。五五.DIF法與法與DIT法的異同法的異同(ytng)第53頁/共87頁第五十三頁，共8

25、7頁。rNmmmWjXkXjX)()()(11rNmmmWjXkXkX)()()(11)(1kXm)(1jXmrNW1(2)(2)蝶形運算蝶形運算(yn (yn sun)sun)不同不同a.a.(DIT)(DIT)用矩陣(j zhn)表示)(kXm)( jXmrNWrNW)(1kXm)(1jXm=11第54頁/共87頁第五十四頁，共87頁。rNmmmWjXkXjX)()()(11)()()(11jXkXkXmmm)(1kXm)(1jXmrNW1b.b.(DIF)(DIF)用矩陣(j zhn)表示)(kXm)( jXmrNWrNW)(1kXm)(1jXm=11第55頁/共87頁第五十五頁，共87

26、頁。 將流圖的所有支路方向都反向(fn xin),交換輸入和輸出，即可得到另一種蝶形。 a.a.(DIT)(DIT)b.b.(DIF)(DIF)rNWrNW1111rNWrNW第56頁/共87頁第五十六頁，共87頁。nkNNkNnnkNWkXNkXIDFTnxWnxnxDFTkX1010)(1)()()()()(第57頁/共87頁第五十七頁，共87頁。 ,形運算(yn sun)均乘以1/2。nkNWnkNWMMN)21(211第58頁/共87頁第五十八頁，共87頁。nkNNkNknkNWkXNWkXNnx1010*)(1)(1)()(1)(110kXDFTNWkXNnkNNk)(nx因此，BA

27、BAWWnkNnkN ,第59頁/共87頁第五十九頁，共87頁。x第60頁/共87頁第六十頁，共87頁。其中,T為抽樣間隔。hsff2sfhfhsffT211第61頁/共87頁第六十一頁，共87頁。,就造成拖尾現(xiàn)象,稱之為頻譜泄漏.)(1nx第62頁/共87頁第六十二頁，共87頁。0n0)(1nx)(1jeXn)(2nx)(2jeXn )()(21nxnxnyjeY第63頁/共87頁第六十三頁，共87頁。pTF1pT第64頁/共87頁第六十四頁，共87頁。 dejXtxdtetxjXtjtj21)(2. 連續(xù)(linx)時間周期信號傅氏級數(shù)變換對 ktjkTTtjkpejkXtxdtetxTj

28、kXpp0002/2/01第65頁/共87頁第六十五頁，共87頁。10 ,)(1)(10 ,)()(1010NnWkXNnxNkWnxkXNknkNNnnkN第66頁/共87頁第六十六頁，共87頁。程總共乘了幅度電平未受到影響。sf1sfT第67頁/共87頁第六十七頁，共87頁。設nTdtnTt,10)()()()(NnnTjnnTjtjenTxTTenTxdtetxjX用DFT計算(j sun)所得的頻譜分量乘以T的理由：第68頁/共87頁第六十八頁，共87頁。)()()()(10/210/20nxDFTTenxTenTxTjkXNnNknjNnNfTjkns1,.1 , 0,/200NkkNfs又第69頁/共87頁第六十九頁，共87頁。0000,2,2kdNNFfFs)()(1)(2)(21)(1102021000000kXDFTfekjXNfekjXejkXnTxsNkknNjsknNTfjNkknTjks 用IDFT計算非周期信號的傅氏反變換(binhun)乘以 的理由sf dejXtxtj21第70頁/共87頁第七十頁，共87頁。(xnho)第71頁/共87頁第七十一頁，共87頁。第