工學(xué)數(shù)字信號處理第四章PPT學(xué)習(xí)教案

1、會計學(xué)1工學(xué)數(shù)字信號處理第四章工學(xué)數(shù)字信號處理第四章Sande-Tukey如：如：Winograd算法；余弦變換快速算法；算法；余弦變換快速算法；Walsh變換；數(shù)論變換等變換；數(shù)論變換等第1頁/共43頁10 )(1)(10 )()1010NnWkXNnxNkWnxkXNknkNNnnkN（NjNeW2mNlNmjlNmNWeWN)(2mNNmNmNmNNmNNmNWWWWWW)2( 或者第2頁/共43頁nkNWMN212, 1 ,0 , )12()(12, 1 ,0 , )2()(21NrrxrxNrrxrx第3頁/共43頁和和1010)12(22)12()2()()(NnrkrNrkNnk

2、NNWrxWrxWnxkXrkrkjrkNjrkNNNWeeW2222221, 1 ,0 )()( )()()(2211010212222NkNrrrkkNrkkkXWkXWrxWWrxkXNNNNnkNWrkkrNNNWW222)()()()()2(110110)(1122222kXWrxWrxkNXNNNNNrrkrkr)()2(22kXkNX第4頁/共43頁上式上式定義的運算稱為定義的運算稱為蝶形運算蝶形運算(Bullerfly Computation)，它可由圖，它可由圖4.2.1形象表示，形象表示，利用蝶形運算符號可將利用蝶形運算符號可將FFT運算用流圖描運算用流圖描述。述。kNkN

3、jkNNkNWWeWWWNNNN2222)(1, 1 , 0 )()( )2()2()2(2212)(12NkNkNkkXWkXNkXWNkXNkXN 1, 1 , 0 )()()2(1, 1 , 0 )()()(221221NkNNkNkkXWkXkNXkkXWkXkX第5頁/共43頁第6頁/共43頁第7頁/共43頁第8頁/共43頁N越大，越大，F(xiàn)FT效率越高，由圖效率越高，由圖4.2.5顯見。顯見。NNNMCM2log22)2(NNNMCA2log22)2(（倍） log2log2222NNNNRN（倍） log1log) 1(22NNNNNNR第9頁/共43頁mNW121 lMN蝶距l(xiāng)M

4、 2mNW12lmNWmNWlM 2)4()100()001() 1 (xxxx第10頁/共43頁nkNWnkNW)(1)(1)(10kXDFTNWkXNnxNknkN1, 1 ,0 )(1, 1 ,0 )(222NNNnnxnnx第11頁/共43頁10)(21010222)()()()(NNNnnkNNnnkNNnnkNWnxWnxWnxkX10222)()( NNnnkNNkNnkNWnxWWnx1022)()( NnnkNNkjWnxenx1jke1jke101102102222222)()()( )()()2(NNNNNnrnrnnNnrnNNWnxWnxnxWnxnxrX第12頁/共

5、43頁10210210)12(222222)()()( )()() 12(NNNNNnrnrnnnNNnnrNNWnxWWnxnxWnxnxrXnNNNWnxnxnxnxnxnx)()()()()()(2221第13頁/共43頁第14頁/共43頁第15頁/共43頁第16頁/共43頁間）的重要方面。一般間）的重要方面。一般“基基”均取小于均取小于8。1mNWjWmN第17頁/共43頁虛部設(shè)為零），將浪費大量時間和空間，虛部設(shè)為零），將浪費大量時間和空間，因此，研究如何利用復(fù)序列因此，研究如何利用復(fù)序列FFT運算有效運算有效地計算實序列具有實際意義。地計算實序列具有實際意義。第18頁/共43頁第1

6、9頁/共43頁 )2)(2)()2)(2)( )2)(2)()2)(2)( )()()(kNZkZkNZkZjkNZkZkNZkZkjZkZkZiiiirrrrir)(),(kIkRee)(),(kIkRoo第20頁/共43頁)2)(2)()2)(2)(= )()()(kNZkZjkNZkZkjIkRkHiirroe)()()(kjIkRkjGeo)2)(2)()2)(2)( )()()(kNZkZjkNZkZkjRkIkGrriioe1, 1 , 0 )()()(NkkjZkZkZir第21頁/共43頁)2)(2)()2)(2)(= )()()(kNZkZjkNZkZkjIkRkHiirro

7、e)()()(kjIkRkjGeo)2)(2)()2)(2)( )()()(kNZkZjkNZkZkjRkIkGrriioe1, 1 , 0 )()()(NkkjZkZkZir第22頁/共43頁1, 1 ,0 )12()(1, 1 ,0 )2()(NnnxngNnnxnh12 , 1 , 0 )()()()( ) 12()2()()(101010)12(2101202NkkGekHWngeWnhWnxWnxWnxkXNkNkjNnnkNjNnnkNNnknNNnnkNNnnkN第23頁/共43頁1, 1 , 0 ) 12()(1, 1 , 0 )2()(NnnxngNnnxnh1, 1 ,0

8、)()()(NkkjZkZkZir)()( cos)(sin)()( sin)(cos)()(= )()()()()(kjXkXkRkIkIjkRkIkRkjRkIekjIkRkXirNkoNkeoNkoNkeeoejoeNk第24頁/共43頁NkrrNkiiiiiNkrrNkiirrrkNZkZkNZkZkNZkZkXkNZkZkNZkZkNZkZkXcos)2)(2)( sin)2)(2)()2)(2)()(sin)2)(2)( cos)2)(2)()2)(2)()(第25頁/共43頁1,2 , 1 , 0 )2()()()(10NkknNcasnxnxDHTkXNnH1, 2 , 1 ,

9、 0 )2()(1)()(0NnknNcaskXNkXIDHTnxNkHH)(Im)(Re)()()()(kXkXkXkjXkXkXHHoHe)()(21)()(21)(kNXkXjkNXkXkXHHHH第26頁/共43頁1,2, 1 ,0 2sin2)cos()()(10NkknNknNnxnNxDHTkNXNnH第27頁/共43頁0002sin)(2cos)()()(knNkNXknNkXnRnnxHHNN)()()()()()()()()()()()(212121121221kXkNXkXkXnxnxkXkNXkXkXnxnxHoHHeHHoHHeH)()()()(2121kXkXnxn

10、xHH第28頁/共43頁運算量。設(shè)x1(n)和x2(n) 為兩個L點的序列， X1(k)和X2(k)分別是它們的L點DFT， y(n)是x1(n)和x2(n)循環(huán)卷積的結(jié)果序列，由DFT時域卷積定理可得：第29頁/共43頁)()()()(21kXkXnyDFTkY)()()()(21nxnxkYIDFTny第30頁/共43頁易證明，當時，亦有，因此，線性卷積又可寫成：0)()()()()(mlmnxmhnxnhny10Nm10Mmn20MNn 2, 0 MNn 2, 0 MNm第31頁/共43頁即：20)()()(MNmlmnxmhny1MNL, 0 , 0),1(,),1 (),0(: )(

11、, 0 , 0),1(,),1 (),0(: )(MxxxnxNhhhnh10 , )()( ; )()()(NnnhnhrLnhnhnhrL10 , )()( ; )()()(MnnxnxqLnxnxnxqL第32頁/共43頁可如圖3.4.3給出。)()()()()()()()()()()()()()()(101010nynRqLnynRmqLnxmhnRqLmnxmhnRmnxmhnxnhnylqLlqLmLLmqLLmLLe 第33頁/共43頁1 010 )()(LnNNnnhnh1 010 )()(LnMMnnxnx第34頁/共43頁第35頁/共43頁其他 01) 1( )()(MknkMnxnxk第36頁/共43頁0)()(kknxnx00)()()()()()(kkkknynhnxnhnxny)()()(nhnxnykk)()()(nhnxnykkx(n)M2M第37頁/共43頁第38頁/共43頁號。第39頁/共43頁dtetxtxFTjfXftjaaa2)()()(第40頁/共43頁其圖形如圖3.4.5(c)。同理，可得：cf211