數(shù)字信號(hào)處理---第四章快速傅立葉變換fft-展示頁(yè)
2024-12-17 09:43本頁(yè)面
【正文】 k( 221 ???? NkN kkXWkXNX ?＋ 可 見 ,X(k)的后一半，也完全由 X1(k), X2 (k)的前一半所確定。 第 4章 快速傅立葉變換（ FFT） 實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算 （ N/2個(gè)蝶形 ) 122,1,0k )()()(122,1,0k ()()(2121????????NkXWkXkXNkXWkXkXkNkN??后一半）前一半(前一半 ) )()()( kXWkXkX kN 21 ??(后一半 ) )()()2( 21 kXWkXkNX kN???1 1 1 1 1 )(1 kX)(2 kXkNW1次 復(fù)乘 2次復(fù)加 第 4章 快速傅立葉變換（ FFT） 圖 蝶形運(yùn)算符號(hào) CABA ＋ BCA － BC第 4章 快速傅立葉變換（ FFT） 例如 N=8 時(shí)的 DFT,可以分解為兩個(gè) N/2=4點(diǎn)的 DFT.具體方法如下 : )(/ kXDFTN 142 ，得點(diǎn)的進(jìn)行 ?3,2,1,0)2()()(30430411 ??? ????kWrxWrxkXrrkrrk)。6(),4(),2(),0( xxxx(1)n為偶數(shù)時(shí) , 記作 : (2) n為奇數(shù)時(shí) ,分別記作 : )。而計(jì)算一個(gè) N/2點(diǎn) DFT需要 (N/2)2次復(fù)數(shù)乘法和 N/2(N/2－ 1)次復(fù)數(shù)加法。 (二 ) N/4點(diǎn) DFT 與第一次分解相同 ， 將 x1(r)按奇偶分解成兩個(gè) N/4長(zhǎng)的子序列 x3(l)和 x4(l)， 即 3241( ) ( 2 ) , 0 , 1 , , 1( ) ( 2 1 ) 4x l x l Nlx l x l? ? ? ? ? ? ?????那么， X1(k)又可表示為 / 4 1 / 4 12 ( 2 1 )1 1 / 2 1 / 200/ 4 1 / 4 13 / 4 / 2 4 / 4003 / 2 4( ) ( 2 ) ( 2 1 )( ) ( )( ) ( ) , 0 , 1 , / 4 1NNk l k lNNiiNNk l k k lN N NiikNX k x l W x l Wx l W W x l WX k W X k k N?????????? ? ???? ? ? ? ? ? ?????第 4章 快速傅立葉變換（ FFT） 式中 / 4 13 3 / 4 3 / 40/ 4 14 4 / 4 4 / 40( ) ( ) [ ( ) ]( ) ( ) [ ( ) ]NklNNiNklNNiX k x l W DFT x lX k x l W DFT x l?????????? 同理 ， 由 X3(k)和 X4(k)的周期性和 Wm N/2的對(duì)稱 性 Wk+N/4 N/2=Wk N/2 最后得到： 1 3 2 41 3 2 40 1 4 14//( ) ( ) ( ), , , , /( / ) ( ) ( )kNkNX k X k W X kkNX k N X k W X k??? ?? ? ? ? ??? ? ? ??() 第 4章 快速傅立葉變換（ FFT） 用同樣的方法可計(jì)算出 2 5 / 2 62 5 / 2 6( ) ( ) ( ), 0 , 1 , / 4 1( / 4 ) ( ) ( )??? ?? ? ? ? ??? ? ? ??kNkNX k X k W X kkNX k N X k W X k() 其中 5262/ 4 15 5 / 4 50/ 4 16 6 / 4 60( ) ( 2 ), 0 , 1 , / 4 1( ) ( 2 1 )( ) ( ) [ ( ) ]( ) ( ) [ ( ) ]NklNiNklNix l x llNx l x lX k x l W D FT x lX k x l W D FT x l????? ?? ? ? ? ???????????第 4章 快速傅立葉變換（ FFT） )0()0(1 xx ?)2()1(1 xx ?)4()2(1 xx ?)6()3(1 xx ? 點(diǎn) DFT 2N)3()2()1()0(1111XXXX)1()0(2 xx ?)3()1(2 xx ?)5()2(2 xx ?)7()3(2 xx ? 點(diǎn) DFT 2N)3()2()1()0(2222XXXX)0(X)4(X0NW)1(X)5(X1NW)2(X)6(X2NW)3(X)7(X3NW1 1 1 1 第 4章 快速傅立葉變換（ FFT） )0()0(1 xx ?)2()1(1 xx ?)4()2(1 xx ?)6()3(1 xx ? 點(diǎn) DFT 2N)3()2()1()0(1111XXXX第 4章 快速傅立葉變換（ FFT） 偶中偶 偶中奇 )0()0()0( 13 xxx ??)4()2()1( 13 xxx ??)2()1()0( 14 xxx ??)6()3()1( 14 xxx ??)1()0(33XX)1()0(44XX0 2NW1 2NW DFT 點(diǎn)4N1 )0(1X)2(1X1 )1(1X)3(1XN/2點(diǎn) DFT分解為兩個(gè) N/4點(diǎn) DFT的信號(hào)流圖 DFT 點(diǎn)4N第 4章 快速傅立葉變換（ FFT） 1 3 2 41 3 2 44//( ) ( ) ( )( / ) ( ) ( )kNkNX k X k W X kX k N X k W X k??? ??? ? ? ??奇中偶 奇中奇 )1()0()0( 55 xxx ??)5()2()1( 25 xxx ??)3()1()0( 26 xxx ??)7()3()1( 26 xxx ??)1()0(55XX)1()0(66XX0 2NW1 2NW1 )0(2X)2(2X1 )1(2X)3(2X DFT 點(diǎn)4N DFT 點(diǎn)4N第 4章 快速傅立葉變換（ FFT） )0()0(1 xx ?)2()1(1 xx ?)4()2(1 xx ?)6()3(1 xx ? 點(diǎn) DFT 2N)1()0(2 xx ?)3()1(2 xx ?)5()2(2 xx ?)7()3(2 xx ? 點(diǎn) DFT 2N)3()2()1()0(1111XXXX)3()2()1()0(2222XXXX)0(X)4(X0NW)1(X)5(X1NW)2(X)6(X2NW)3(X)7(X3NW1 1 1 1 )1()0()0( 55 xxx ??)5()2()1( 25 xxx ??)3()1()0( 26 xxx ??)7()3()1( 26 xxx ??)1()0(55XX)1()0(66XX02NW12NW1 1 點(diǎn) DFT 4N 點(diǎn) DFT 4N)0()0()0( 13 xxx ??)4()2()1( 13 xxx ??)2()1()0( 14 xxx ??)6()3()1( 14 xxx ??)1()0(33XX)1()0(44XX02NW12NW 點(diǎn) DFT 4N1 點(diǎn) DFT 4N第 4章 快速傅立葉變換（ FFT） )1()0()0( 55 xxx ??)5()2()1( 25 xxx ??)3()1()0( 26 xxx ??)7()3()1( 26 xxx ??)3()2()1()0(1111XXXX)3()2()1()0(2222XXXX)0(X)4(X0NW)1(X)5(X1NW)2(X)6(X2NW)3(X)7(X3NW1 1 1 1 1 )1()0(55XX)1()0(66XX0NW2NW1 1 )0()0()0( 13 xxx ??)4()2()1( 13 xxx ??)2()1()0( 14 xxx ??)6()3()1( 14 xxx ??)1()0(33XX)1()0(44XX0NW2NW 點(diǎn) DFT 4N1 點(diǎn) DFT 4N 點(diǎn) DFT 4N 點(diǎn) DFT 4N一個(gè) N=8點(diǎn) DFT分解為四個(gè) N/4點(diǎn) DFT的信號(hào)流圖 圖 N點(diǎn) DFT的第二次時(shí)域抽取分解圖 (N=8) N /4 點(diǎn)D F TWN12WN12W N0W N1W N2W N3X1( 0 )X1( 1 )X1( 2 )X1( 3 )X2( 0 )X2( 1 )X2( 2 )X
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1