[工學]數(shù)字信號處理[第四章_快速傅里葉變換fft-資料下載頁

　　

【正文】 o s [ ( ) ] s in [ ( ) ] }Nnx n k N n k N nNN????? ? ? ??1022( ) [ c o s sin ]Nnx n k n k nNN???????22c o s[ ( ) ] c o s[ ]k N n k nNN???? 22s in [ ( ) ] s in [ ]k N n k nNN??? ? ?102( ) ( ) [ ( ) ]NHnX N k x n c a s N k nN???? ? ??1022( ) [ c s( ) sin ( ) ]Nnx n k n k nNN??????61 快速傅里葉變換（ FFT） [ ( ) ] ( )HD F T x n X k?0 0 022c o s ( ) s in ( )( ( ) ) ( ) ( ) ( )N N H Hn k n k nNx n R n X k NX N k??? ? ? ?0 0 022c o s ( ) s in ( )( ( ) ) ( ) ( ) ( )N N H Hn k n k nNx n R n X k NX N k??? ? ? ?62 快速傅里葉變換（ FFT） 證明： 10002[ ( ( ) ) ( ) ] ( ( ) ) ( ) ( )NN N N NnD F T x n n R n x n n R n c a s k nN???? ? ??1002( ) [ ( ) ]Nnx n c a s k n nN??????39。 0n n n??1000002 2 2 2( ) [ ( ) ( ) (c o s c o s sin s) ( )2 2 2inc o s sin2( ) ( ) ( ) ( )sin c o s ]Nnx n k n k n k n k nN N N Nk n k n k n k nN N N N? ? ? ?? ? ? ????????02( ) c o s( )HX k k nN??02( ) s in ( )HX N k k nN???63 快速傅里葉變換（ FFT） 1 1 1 12 2 2 2[ ( ) ( ) ] ( ) ( )HHD F T x n x N n X k X N k? ? ? ? ?[ ( ) ] ( )[ ( ) ] ( )HHD F T x n X kD F T x N n X N k?? ? ?1 1 1 12 2 2 2[ ( ) ( ) ] ( ) ( )HHD F T x n x N n X k X N k? ? ? ? ?64 快速傅里葉變換（ FFT） 1122[ ( ) ] ( )[ ( ) ] ( )HHD F T x n X kD F T x n X k??1 2 2 1 2 1( ) ( ) ( ) ( ) ( ) ( )H H e H H ox n x n X K X K X N K X K? ? ? ?1 2 1 2 1 2( ) ( ) ( ) ( ) ( ) ( )H H e H H ox n x n X K X K X N K X K? ? ? ?65 快速傅里葉變換（ FFT） ( ) ( ) ( )11[ ( ) ( ) ] [ ( ) ( ) ]22H e H oH H H HX k X k jX kX k X N k j X k X N k??? ? ? ? ? ?證明： 1 2 1 2[ ( ) ( ) ] ( ) ( )D F T x n x n X k X k? ? ?11 2 2211 2 2211 2 2211 2 22( ) ( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]H e H HH e H HH o H HH o H HX k X k X k X N kX k X k X N kX k X k X N kX k X k XjkjN? ? ?? ? ?? ? ?? ? ?66 ()HXK ?快速傅里葉變換（ FFT） ( ) R e [ ( ) ] l i m [ ( ) ]HX k X k X k??11 2 2211 2 2211 2 2211 2 22( ) ( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]H e H HH e H HH o H HH o H HX k X k X k X N kX k X k X N kX k X k X N kX k X k XjkjN? ? ?? ? ?? ? ?? ? ?11 2 2 1 2 2211 2 2 1 2 221( ) ( ) [ ( ) ( ) ] ( )1( ) [ ( ) ( ) ] ( ) [ ( )[ ( ) ( ) ]( ) ]22H e H H H o HH H e H H H o H HHX k X k X k X N k X k X k X N kX k X k X N k X k X k X N k?? ? ? ? ? ?? ? ? ? ?21( ) ( )H H oX N K X K??21( ) ( )H H eX K X K12( ) ( )x n x n??67 快速傅里葉變換（ FFT） DHT的快速算法（ FHT）： 102( ) [ ( ) ] ( ) ( )NHnX k D H T x n x n c a s k nN????? ?2 MN ?設(shè) ：01 2( ) ( 2 ) ( ) ( 2 1 ) 0 , 1 , 1Nx r x r x r x r r? ? ? ? ?22110022( ) ( 2 ) ( 2 ) ( 2 1 ) [ ( 2 1 ) ]NNHrrX k x r c a s k r x r c a s k rNN??????? ? ? ???22211010011022( ) ( ) ( ) ( )/ 2 /2c os( )2sin(22( ) ( ))/2NNNrrrx r c as k r x r c as k rNNkx r c as kNNrNk?? ????????????????( ) c o s ( ) s i nc a s c a s c a s? ? ? ? ? ?? ? ? ? ? ?22,/2 k r kNN??????68 快速傅里葉變換（ FFT） 2221101001102 2 2( ) ( ) ( ) c os( ) ( ) ( )/ 2 / 222si n( ) ( ) ( )/2NNNHrrrX k x r c as k r k x r c as k rN N Nk x r c as k rNN? ? ????????????????0 ()HXk 2 1c o s ( ) ( )HN k X k?? 2 1 2s i n ( ) ( )NHN k X k???()HXk ?22( ) c o s ( ) 。 ( ) s i n ( )NNC k k S k k????0 1 1 2( ) ( ) ( ) ( ) ( ) ( )NH H H HX k X k C k X k S k X k? ? ? ?0 1 122( ) ( ) ( ) ( ) ( ) ( )NNH H H HX k X k C k X k S k X k? ? ? ? ?0 1 12 2 2( ) ( ) ( ) ( ) ( ) ( )N N NH H H HX k X k S k X k C k X k? ? ? ? ? ?0 1 122( ) ( ) ( ) ( ) ( ) ( )NNH H H HX N k X k S k X k C k X k? ? ? ? ? ?0 1 12 2 2 2 2( ) ( ) ( ) ( ) ( ) ( )N N N N NH H H HX k X k C k X k S k X N k? ? ? ? ? ? ? ? ?0 1 12 2 2 2 2 2 2( ) ( ) ( ) ( ) ( ) ( )N N N N N NH H Hk X k C k X k S k X k? ? ? ? ? ? ? ? ? ?0 1 1 2( ) ( ) ( ) ( ) ( ) ( )NH H H HX N k X N k C N k X N k S N k X N k? ? ? ? ? ? ? ? ? ?69 快速傅里葉變換（ FFT） 0 1 1 2( ) ( ) ( ) ( ) ( ) ( )NH H H HX k X k C k X k S k X k? ? ? ?0 1 122( ) ( ) ( ) ( ) ( ) ( )NNH H H HX k X k C k X k S k X k? ? ? ? ?0 1 12 2 2( ) ( ) ( ) ( ) ( ) ( )N N NH H H HX k X k S k X k C k X k? ? ? ? ? ?0 1 122( ) ( ) ( ) ( ) ( ) ( )NNH H H HX N k X k S k X k C k X k? ? ? ? ? ?哈特萊蝶形 0 ()HXk ()HXk0 ()xr( 2 )xr ?1()xr( 2 1 )xr ??0 2()NHXk?1 ()HXk1 2()NHXk?2()NHXk?2()NHXk?()HX N k?()Ck()Sk ()Sk()Ck?1?1?70 快速傅里葉變換（ FFT） 0 1 1 2( ) ( ) ( ) ( ) ( ) ( )NH H H HX k X k C k X k S k X k? ? ? ?0 1 122( ) ( ) ( ) ( ) ( ) ( )NNH H H HX k X k C k X k S k X k? ? ? ? ?0 1 12 2 2( ) ( ) ( ) ( ) ( ) ( )N N NH H H HX k X k S k X k C k X k? ? ? ? ? ?0 1 122( ) ( ) ( ) ( ) ( ) ( )NNH H H HX N k X k S k X k C k X k? ? ? ? ? ?01010 : ( 0 ) ( 0 ) ( 0 ) ( ) ( 0 ) ( 0 )2H H HH H Hk X X XNX X X? ? ???0101: ( ) ( ) ( )4 4 4 43 ( ) ( ) ( )4 4 4H H HH H HN N N Nk X X XN N NX X X? ? ???71 快速傅里葉變換（ FFT） DITFHT算法與 DITDFT運算量的比較 2 MN ?設(shè) ： M 級 蝶 形 , 表 示 自 右 向 左 的L 蝶 形 級 數(shù)2 / 2 2LLLN ?第 級 乘 法 次 數(shù) 為 （ ）最 后 兩 級 無 乘 法 運 算212 ( / 2 2 ) 3 4MLLHLM N M N N??? ? ? ??=33 222HA M N N??=運算量減小一半 72 快速傅里葉變換（ FFT） FHT FHT 1 ()xn2 ()xnIDFT 12( ) ( )x n x n* 實信號的快速卷積 循環(huán)卷積 定理 12( ) ( )x n x n* 1L N M? ? ?