工学数字信号处理第四章学习教案.pptx

《工学数字信号处理第四章学习教案.pptx》由会员分享，可在线阅读，更多相关《工学数字信号处理第四章学习教案.pptx（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1工学数字工学数字(shz)信号处理第四章信号处理第四章第一页，共43页。(J.W.Tukey)发现发现DFT的快速算法后，的快速算法后，DFT才得到实际的应用。才得到实际的应用。n自自1965年后，年后，DFT的快速计算算法的快速计算算法的研究得到空前的发展，除了的研究得到空前的发展，除了Cooley-Tukey算法；算法；Sande-Tukey算算法外，还有许多其它算法，如：法外，还有许多其它算法，如：Winograd算法；余弦变换快速算法；算法；余弦变换快速算法；Walsh变换；数论变换等变换；数论变换等第1页/共43页第二页，共43页。nn对称性：对称性：10 )(1)(10 )

2、()1010NnWkXNnxNkWnxkXNknkNNnnkN（NjNeW2mNlNmjlNmNWeWN)(2mNNmNmNmNNmNNmNWWWWWW)2( 或者第2页/共43页第三页，共43页。n按按n的奇偶将的奇偶将x(n)分解分解(fnji)为两个为两个N/2点的子序列：点的子序列：nkNWMN212, 1 ,0 , )12()(12, 1 ,0 , )2()(21NrrxrxNrrxrx第3页/共43页第四页，共43页。和和1010)12(22)12()2()()(NnrkrNrkNnkNNWrxWrxWnxkXrkrkjrkNjrkNNNWeeW2222221, 1 ,0 )()(

3、 )()()(2211010212222NkNrrrkkNrkkkXWkXWrxWWrxkXNNNNnkNWrkkrNNNWW222)()()()()2(110110)(1122222kXWrxWrxkNXNNNNNrrkrkr)()2(22kXkNX第4页/共43页第五页，共43页。上式定义的运算称为蝶形运算上式定义的运算称为蝶形运算(Bullerfly Computation)，它可由图，它可由图4.2.1形象表示，形象表示，利用蝶形运算符号可将利用蝶形运算符号可将FFT运算用流图描运算用流图描述。述。kNkNjkNNkNWWeWWWNNNN2222)(1, 1 , 0 )()( )2()

4、2()2(2212)(12NkNkNkkXWkXNkXWNkXNkXN 1, 1 , 0 )()()2(1, 1 , 0 )()()(221221NkNNkNkkXWkXkNXkkXWkXkX第5页/共43页第六页，共43页。第6页/共43页第七页，共43页。第7页/共43页第八页，共43页。第8页/共43页第九页，共43页。v复加法：复加法：v N越大，越大，FFT效率越高，由图效率越高，由图4.2.5显显见。见。NNNMCM2log22)2(NNNMCA2log22)2(（倍） log2log2222NNNNRN（倍） log1log) 1(22NNNNNNR第9页/共43页第十页，共43

5、页。mNW121 lMN蝶距lM 2mNW12lmNWmNWlM 2)4()100()001() 1 (xxxx第10页/共43页第十一页，共43页。抽取原理抽取原理将将x(n)分成前分成前N/2和后和后N/2两半，即：两半，即：nkNWnkNW)(1)(1)(10kXDFTNWkXNnxNknkN1, 1 ,0 )(1, 1 ,0 )(222NNNnnxnnx第11页/共43页第十二页，共43页。10)(21010222)()()()(NNNnnkNNnnkNNnnkNWnxWnxWnxkX10222)()( NNnnkNNkNnkNWnxWWnx1022)()( NnnkNNkjWnxen

6、x1jke1jke101102102222222)()()( )()()2(NNNNNnrnrnnNnrnNNWnxWnxnxWnxnxrX第12页/共43页第十三页，共43页。10210210)12(222222)()()( )()() 12(NNNNNnrnrnnnNNnnrNNWnxWWnxnxWnxnxrXnNNNWnxnxnxnxnxnx)()()()()()(2221第13页/共43页第十四页，共43页。第14页/共43页第十五页，共43页。第15页/共43页第十六页，共43页。第16页/共43页第十七页，共43页。1mNWjWmN第17页/共43页第十八页，共43页。因此，研究如

7、何利用复序列因此，研究如何利用复序列FFT运算有效运算有效地计算实序列具有实际意义。地计算实序列具有实际意义。第18页/共43页第十九页，共43页。，即可通过求即可通过求N点复信号点复信号(xnho)z(n)的的DFT来求得来求得h(n)和和g(n)的的DFT。第19页/共43页第二十页，共43页。 )2)(2)()2)(2)( )2)(2)()2)(2)( )()()(kNZkZkNZkZjkNZkZkNZkZkjZkZkZiiiirrrrir)(),(kIkRee)(),(kIkRoo第20页/共43页第二十一页，共43页。)2)(2)()2)(2)(= )()()(kNZkZjkNZkZ

8、kjIkRkHiirroe)()()(kjIkRkjGeo)2)(2)()2)(2)( )()()(kNZkZjkNZkZkjRkIkGrriioe1, 1 , 0 )()()(NkkjZkZkZir第21页/共43页第二十二页，共43页。)2)(2)()2)(2)(= )()()(kNZkZjkNZkZkjIkRkHiirroe)()()(kjIkRkjGeo)2)(2)()2)(2)( )()()(kNZkZjkNZkZkjRkIkGrriioe1, 1 , 0 )()()(NkkjZkZkZir第22页/共43页第二十三页，共43页。1, 1 ,0 )12()(1, 1 ,0 )2()(

9、NnnxngNnnxnh12 , 1 , 0 )()()()( ) 12()2()()(101010)12(2101202NkkGekHWngeWnhWnxWnxWnxkXNkNkjNnnkNjNnnkNNnknNNnnkNNnnkN第23页/共43页第二十四页，共43页。1, 1 , 0 ) 12()(1, 1 , 0 )2()(NnnxngNnnxnh1, 1 ,0 )()()(NkkjZkZkZir)()( cos)(sin)()( sin)(cos)()(= )()()()()(kjXkXkRkIkIjkRkIkRkjRkIekjIkRkXirNkoNkeoNkoNkeeoejoeNk

10、第24页/共43页第二十五页，共43页。NkrrNkiiiiiNkrrNkiirrrkNZkZkNZkZkNZkZkXkNZkZkNZkZkNZkZkXcos)2)(2)( sin)2)(2)()2)(2)()(sin)2)(2)( cos)2)(2)()2)(2)()(第25页/共43页第二十六页，共43页。1,2 , 1 , 0 )2()()()(10NkknNcasnxnxDHTkXNnH1, 2 , 1 , 0 )2()(1)()(0NnknNcaskXNkXIDHTnxNkHH)(Im)(Re)()()()(kXkXkXkjXkXkXHHoHe)()(21)()(21)(kNXkXj

11、kNXkXkXHHHH第26页/共43页第二十七页，共43页。1,2, 1 ,0 2sin2)cos()()(10NkknNknNnxnNxDHTkNXNnH第27页/共43页第二十八页，共43页。0002sin)(2cos)()()(knNkNXknNkXnRnnxHHNN)()()()()()()()()()()()(212121121221kXkNXkXkXnxnxkXkNXkXkXnxnxHoHHeHHoHHeH)()()()(2121kXkXnxnxHH第28页/共43页第二十九页，共43页。卷积，但比较麻烦，特别是当N很大时，需要很大的计算(j sun)量。通过卷积定理，可以将两序

12、列的循环卷积变换到频域，并利用FFT可以大大降低其运算量。n设x1(n)和x2(n) 为两个L点的序列，X1(k)和X2(k)分别是它们的L点DFT，y(n)是x1(n)和x2(n)循环卷积的结果序列，由DFT时域卷积定理可得：第29页/共43页第三十页，共43页。)()()()(21kXkXnyDFTkY)()()()(21nxnxkYIDFTny第30页/共43页第三十一页，共43页。易证明(zhngmng)，当时，亦有，因此，线性卷积又可写成：0)()()()()(mlmnxmhnxnhny10Nm10Mmn20MNn 2, 0MNn 2, 0 MNm第31页/共43页第三十二页，共43

13、页。即：20)()()(MNmlmnxmhny1MNL, 0 , 0),1(,),1 (),0(: )(, 0 , 0),1(,),1 (),0(: )(MxxxnxNhhhnh10 , )()( ; )()()(NnnhnhrLnhnhnhrL10 , )()( ; )()()(MnnxnxqLnxnxnxqL第32页/共43页第三十三页，共43页。方法和步骤可如图3.4.3给出。)()()()()()()()()()()()()()()(101010nynRqLnynRmqLnxmhnRqLmnxmhnRmnxmhnxnhnylqLlqLmLLmqLLmLLe 第33页/共43页第三十四页

14、，共43页。1 010 )()(LnNNnnhnh1 010 )()(LnMMnnxnx第34页/共43页第三十五页，共43页。第35页/共43页第三十六页，共43页。其他 01) 1( )()(MknkMnxnxk第36页/共43页第三十七页，共43页。0)()(kknxnx00)()()()()()(kkkknynhnxnhnxny)()()(nhnxnykk)()()(nhnxnykkx(n)M2M第37页/共43页第三十八页，共43页。第38页/共43页第三十九页，共43页。第39页/共43页第四十页，共43页。dtetxtxFTjfXftjaaa2)()()(第40页/共43页第四十一页，共43页。6)其图形如图3.4.5(c)。同理，可得：cf21102)()(NnfnTjaenTxTjfXpsTNTNfF11)()()(102nxDFTTenxTkXNnknjaN)(1)(kXIDFTTnxa第41页/共43页第四十二页，共43页。量幅度形成其频谱函数：nn仍为以2为周期的周期函数(zhu q hn sh)。n截取的整数个周期做DFT，也能获得的频谱结构。)(jeX)(jeX)(jeX)(nxkjkNkXNnxFTeX)2()(2)()()(jeX)(nx)(nx第42页/共43页第四十三页，共43页。