數(shù)字信號(hào)處理---第四章快速傅立葉變換fft-在線瀏覽
2025-01-25 09:43本頁面
【正文】 2( 3 )X ( 0 )X ( 1 )X ( 2 )X ( 3 )X ( 4 )X ( 5 )X ( 6 )X ( 7 )x ( 0 )X3( 0 )X3( 1 )X4( 0 )X4( 1 )x ( 4 )x ( 2 )x ( 6 )x ( 1 )x ( 5 )x ( 3 )x ( 7 )N /4 點(diǎn)D F TN /4 點(diǎn)D F TN /4 點(diǎn)D F TWN02WN02第 4章 快速傅立葉變換（ FFT） )4()0()1()0()1()4()0()1()0()0(03330333xWxxxXxWxxxXNN???????－)6()2()1()0()1()6()2()1()0()0(04440444xWxxxXxWxxxXNN???????－(三 ) N/4點(diǎn) DFT 第 4章 快速傅立葉變換（ FFT） )5()1()1()0()1()5()1()1()0()0(05550555xWxxxXxWxxxXNN???????－)7()3()1()0()1()7()3()1()0()0(06660666xWxxxXxWxxxXNN???????－第 4章 快速傅立葉變換（ FFT） )1()0()0( 55 xxx ??)5()2()1( 25 xxx ??)3()1()0( 26 xxx ??)7()3()1( 26 xxx ??)0()0()0( 13 xxx ??)4()2()1( 13 xxx ??)2()1()0( 14 xxx ??)6()3()1( 14 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()0(33XX)1()0(44XX0NW2NW1 1 )1()0(55XX)1()0(66XX0NW2NW1 1 0NW1 點(diǎn) DFT 4N 點(diǎn) DFT 4N 點(diǎn) DFT 4N 點(diǎn) DFT 4N0NW1 0NW1 0NW1 第 4章 快速傅立葉變換（ FFT） 圖 N點(diǎn) DIT―FFT 運(yùn)算流圖 (N=8) W N0W N1W N2W N3W N0W N2W N0W N2W N0W N0W N0W N0x ( 0 )x ( 4 )x ( 2 )x ( 6 )x ( 1 )x ( 5 )x ( 3 )x ( 7 )A ( 0 )A ( 1 )A ( 2 )A ( 3 )A ( 4 )A ( 5 )A ( 6 )A ( 7 )A ( 0 )A ( 1 )A ( 2 )A ( 3 )A ( 4 )A ( 5 )A ( 6 )A ( 7 )A ( 0 )A ( 7 )X ( 0 )X ( 1 )X ( 2 )X ( 3 )X ( 4 )X ( 5 )X ( 6 )X ( 7 )A ( 0 )A ( 1 )A ( 2 )A ( 3 )A ( 4 )A ( 5 )A ( 6 )A ( 7 )第 4章 快速傅立葉變換（ FFT） DIT―FFT 算法與直接計(jì)算 DFT運(yùn)算量的比較 ? 每一級運(yùn)算都需要 N/2次復(fù)數(shù)乘和 N次復(fù)數(shù)加 (每個(gè)蝶形需要兩次復(fù)數(shù)加法 )。N=2M點(diǎn)的 FFT共進(jìn)行 M級運(yùn)算 ， 每級由 N/2個(gè)蝶形運(yùn)算組成 。每個(gè)蝶形都要乘以因子 ，稱其為 旋轉(zhuǎn)因子， p為旋轉(zhuǎn)因子的指數(shù) 。為了編寫計(jì)算程序，應(yīng)先找出旋轉(zhuǎn)因子 與運(yùn)算級數(shù)的關(guān)系。觀察圖 ，第 L級共有 2L－ 1個(gè)不同的旋轉(zhuǎn)因子。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距 B個(gè)點(diǎn) ， 應(yīng)用原位計(jì)算 ， 則蝶形運(yùn)算可表示成如下形式： AL (J) AL1(J)+A L1(J+B)WpN AL(J+B) AL1(J)A L1(J+B)WpN 式中 p=J 而 AL－ 1(J)表示第 L級運(yùn)算前 A(J)的值 （ 即第 L級蝶形的輸入數(shù)據(jù) ） 4. 編程思想及程序框圖 圖 DIT―FFT 運(yùn)算和程序框圖 開 始送入 x ( n ) ， MN ＝ 2 M倒 序L ＝ 1 , MＪ ＝ 0 , B － 1P ＝ 2 M － LJk ＝ J , N － 1 , 2LpNpNWBkXkXBkXWBkXkXkX)()()()()()(???????輸 出結(jié) 束B 2 L － 1 DIT―FFT 算法的輸入序列的排序看起來似乎很亂 ，但仔細(xì)分析就會(huì)發(fā)現(xiàn)這種倒序是很有規(guī)律的 。 圖 形成倒序的樹狀圖 (N=23) 01010101010101( n2n1n0)2000 042615371000101100011010111115. 序列的倒序 表 順序和倒序二進(jìn)制數(shù)對照表 圖 倒序規(guī)律 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 )A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 )A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 )x ( 0 ) x ( 4 ) x ( 2 ) x ( 6 ) x ( 1 ) x ( 5 ) x ( 3 ) x ( 7 ) 圖 倒序程序框圖 221????NNLHJNLHI ＝ 1 , N1I ≥ JTJAJXIAIXT???)()()()(J ＜ KLHK ?KJJ ??2KKKJJ???ＹNNY 頻域抽取法 FFT（ DIT_FFT) ?算法原理 ????10)()(NnnkNWnxkX????????12/10)()(2 NNnnkNnnkN WnxWnxN??????????10)(10222)2()(NNNnknNnnkN WNnxWnx(一 )N/2點(diǎn) DFT 第 4章 快速傅立葉變換（ FFT） nkNnkN WWNnxnxNN????????? ??? 1022)2()(, 12 ??? ? ?jN eW N kkNNW )( 12 ??nkNnk WNnxnxkXN????????? ???? 102)2()1()()(1,1,0 ?? Nk ?第 4章 快速傅立葉變換（ FFT） nrNnWNnxnxrXN2102)2()()2( ????????? ???k為偶數(shù)時(shí)： nrnNNWNnxnx22 10)2()(????????? ??? 1,1,02 ?? Nr ?)(1 nxk為奇數(shù)時(shí)： nrnnN NNWWNnxnx22 10)2()(??? ???????????? ???)(2 nx1,1,0 2 ?? Nr ?)12(102)2()()12( ???? ?????? ???? rnNnWNnxnxrXN第 4章 快速傅立葉變換（ FFT） 1,1,0 )]2()([)()2()()(221???????????????NnNnWNnxnxnxNnxnxnx?1,1,0 )()12()()2(21202120122???????????????????? NnrNnnrNnrWnxrXWnxrXNN? 可見 ,上面兩式均為 N/2的 DFT。 第 4章 快速傅立葉變換（ FFT） ? 利用 FFT計(jì)算 IFFT的思路 1 ??????10)(1)]([)(NknkNWkXNkXI D F TnxI D F TF F TNWWD F TnkNnkN算法都可以用來運(yùn)算或頻率抽取抽?。┠敲匆陨嫌懻摰臅r(shí)間（將運(yùn)算結(jié)果都除以改成運(yùn)算中的每個(gè)系數(shù)只要把3)2()1(?? IDFT的高效算法 ?????10)()]([)(NknkNWnxnxD F TkX第 4章 快速傅立葉變換（ FFT） ?把 FFT的時(shí)間抽取法
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1