线性卷积的FFT算法ppt课件学习教案

1、会计学1线性卷积的线性卷积的FFT算法算法(sun f)ppt课件课件第一页，共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

2、)()(2kNNkNjNNNnkNnNNkNnkNknNNkNnNWWeWWeWWWWWN得:对称性:周期性:第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为偶数(u s

3、h) (n为奇数)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页

4、第九页，共87页。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由

5、X1(k)、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(

6、)3(),4()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)(

7、0)X X2(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(

8、)()(4444( (偶中偶) )( (偶中奇) )第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为奇数时，N/2点分为(fn wi)两个N/4点 的序列进行DFT，则有

9、:14, 1 , 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)的“偶中偶”部分:构成(guchng)N/4点DFT，从而得到X3(0), X3(1)。第19页/共87页第十九页，共87页。)6()3()1()2()1()0()()()(1

10、41414xxxxxxnxrxlx(2) 将原序列(xli)x(n)的“偶中奇”部分:构成N/4点DFT，从而(cng r)得到X4(0), X4(1)。(3) 将原序列(xli)x(n)的“奇中偶”部分:)5()2()1()1()0()0()()()(252525xxxxxxnxrxlx构成N/4点DFT，从而得到X5(0), X5(1)。第20页/共87页第二十页，共87页。(4) 将原序列(xli)x(n)的“奇中奇”部分:)7()3()1()3()1()0()()()(262626xxxxxxnxrxlx构成N/4点DFT，从而(cng r)得到X6(0), X6(1)。（5）由 X3

11、(0), X3(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)

12、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)进行(jnxng)碟形运算, 得到 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/33lkNlllkNllkNllkNWlxkXWlxkX

13、WlxkXWlxkX第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

15、页。WWWWN0N0N0N0-1-1-1-1WWWWN0N2N0N2-1-1-1-1WWWWNNNN0123.输入数据、中间(zhngjin)运算结果和最后输出均用同一存储器。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)表示第m列;用k,j表示蝶形输入数据所在(suzi)的（上/下）行数(0,1,2, ,N-

16、1);这时任何一个蝶形运算可用下面通用式表示， 即 由运算流图可知(k zh),一共有N个输入/出行,一共有log2 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()1()1()4(

17、)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)自然(zrn)顺序变

19、址倒位序4.4.蝶形运算两节点的距离蝶形运算两节点的距离: :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 = ( n 2 n 1 n 0 ) 2 , 再 将 k = (n2n1n0)2 左移(M-m)位,右边位置(wi zhi)补零,就可得到(r)2 的值，即 (r)

20、2 =(k)2 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

21、 , 0Nk第43页/共87页第四十三页，共87页。nrnnrNnNNNWNnxnxWNnxnx22210210)2()()2()()2( rXr1, 1 , 02Nrk k为偶数为偶数(u sh)(u sh)时：时：第44页/共87页第四十四页，共87页。nrnnNrnNnNNNWWNnxnxWNnxnxrX22210)12(10)2()()2()() 12(xxk k为奇数为奇数(j sh)(j sh)时：时：1, 1 , 02Nr第45页/共87页第四十五页，共87页。-1-1)2()(Nnxnx1, 1 , 02NnnNWNnxnx)2()(3.3.蝶形运算蝶形运算(yn (yn su

22、n)sun)进行如下碟形运算：和)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的奇偶的奇偶(q u)(q u)分分解过程解过程 先蝶形运算，后先蝶形运算，后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页。第48页/共87页第四十

23、八页，共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)()()(11jXkXkXmmmrNmm

24、mWjXkXjX)()()(11第50页/共87页第五十页，共87页。三三.蝶形运算两节点蝶形运算两节点(ji din)的距离的距离第51页/共87页第五十一页，共87页。rNmmmmmmmmmWNkXkXNkXNkXkXkX)2()()2()2()()(1111四四. . 的计算的计算(j sun)(j sun) 由于由于DIFDIF蝶形运算的两节点的距离为蝶形运算的两节点的距离为 N/2m N/2m , , 所以蝶形运算可表为：所以蝶形运算可表为：rNW第52页/共87页第五十二页，共87页。五五.DIF法与法与DIT法的异同法的异同(ytng)第53页/共87页第五十三页，共87页。rN

25、mmmWjXkXjX)()()(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、图的所有支路方向都反向,交换(jiohun)输入和输出，即可得到另一种蝶形。 a.a.(DIT)(DIT)b.b.(DIF)(DIF)rNWrNW1111rNWrNW第56页/共87页第五十六页，共87页。nkNNkNnnkNWkXNkXIDFTnxWnxnxDFTkX1010)(1)()()()()(第57页/共87页第五十七页，共87页。 ,形运算均乘以1/2。nkNWnkNWMMN)21(211第58页/共87页第五十八页，共87页。nkNNkNknkNWkXNWkXNnx1010*)(1)(1)()(1)(110kXDFTNWkXNnkNNk)(nx因此，BABAWWnkNnkN ,第

27、59页/共87页第五十九页，共87页。x第60页/共87页第六十页，共87页。其中,T为抽样间隔。hsff2sfhfhsffT211第61页/共87页第六十一页，共87页。,就造成拖尾现象,称之为频谱泄漏(xilu).)(1nx第62页/共87页第六十二页，共87页。0n0)(1nx)(1jeXn)(2nx)(2jeXn )()(21nxnxnyjeY第63页/共87页第六十三页，共87页。pTF1pT第64页/共87页第六十四页，共87页。 dejXtxdtetxjXtjtj21)(2. 连续时间周期(zhuq)信号傅氏级数变换对 ktjkTTtjkpejkXtxdtetxTjkXpp000

28、2/2/01第65页/共87页第六十五页，共87页。10 ,)(1)(10 ,)()(1010NnWkXNnxNkWnxkXNknkNNnnkN第66页/共87页第六十六页，共87页。(guchng)总共乘了幅度电平未受到影响。sf1sfT第67页/共87页第六十七页，共87页。设nTdtnTt,10)()()()(NnnTjnnTjtjenTxTTenTxdtetxjX用DFT计算所得的频谱分量(fn ling)乘以T的理由：第68页/共87页第六十八页，共87页。)()()()(10/210/20nxDFTTenxTenTxTjkXNnNknjNnNfTjkns1,.1 , 0,/200NkkNfs又第69页/共87页第六十九页，共87页。0000,2,2kdNNFfFs)()(1)(2)(21)(1102021000000kXDFTfekjXNfekjXejkXnTxsNkknNjsknNTfjNkknTjks 用IDFT计算非周期(zhuq)信号的傅氏反变换乘以 的理由sf dejXtxtj21第70页/共87页第七十页，共87页。(din pn)。第71页/共87页第七十一页，共87页。第7