快速傅立葉變換ppt課件-閱讀頁
2025-05-14 02:01本頁面
【正文】 )距離為 211=1, 第二級(jí) (列 )距離為 221=2， 第三級(jí) (列 )距離為 231=4。 為此 ， 令 k=(n2n1n0)2 ,再 將 k= (n2n1n0)2 左 移 (Lm)位 ,右邊位置補(bǔ)零 ,就可得到 (r)2 的值 ， 即 (r)2 =(k)22Lm 。 (2)k=3 ,m=3 的 r值 。 k=5=(101)2 左移 Lm=1位 r=(010)2 =2。 存放系數(shù) , r=0,1, ,（ N/2） 1, 需 N/2個(gè)存儲(chǔ)單元； 共計(jì) (N+N/2)個(gè)存儲(chǔ)單元。 這時(shí) X(k) 可分為兩部分： nrnnrNnNNNWNnxnxWNnxnx22210210)2()()2()(? ?????????? ?????????????)2( rXr 1,1,0 2 ?? Nr ?k為偶數(shù)時(shí)： 可見 ,上面兩式均為 N/2的 DFT。 (0) X(0) (1) X(4) (2) X(2) (3) X(6) (4) X(1) (5) X(5) (6) X(3) (7) X(7) 1 1 1 1 W W W W N N N N 0 1 2 3 1 1 1 1 W W W W N N N N 0 2 0 2 1 1 1 1 W W W W N N N N 0 0 0 0 xxxxxxxx例如 N=8時(shí) DIF的 FFT流圖如下： 二 .原位運(yùn)算 每級(jí) (列 )都是由 N/2個(gè)蝶形運(yùn)算構(gòu) 成 ,即 1 W N r ?????????????rNmmmmmmWjXkXjXjXkXkX)]()([)()()()(1111)(1 kX m?)(1 jX m?)()()( 11 jXkXkX mmm ?? ??rNmmm WjXkXjX )]()([)( 11 ?? ??三 .蝶形運(yùn)算兩節(jié)點(diǎn)的距離 一般公式為 2Lm =N/2m 例如 N=23 =8 ： (1)m=1 時(shí)的距離為 8/2=4； (2)m=2 時(shí)的距離為 8/4=2。 r的求法 ： k=(n2 n1 n0 ) ,左移 m1位 ,右邊空出補(bǔ)零 , 得 (r)2 ,亦即 (r)2 =(k)2 2m1 . 例如 ,N=8: (1)m=1,k=2, k=(010)2 左移 0位 ,(r)2=(010)2=2。 (3)m=2,k=5, k=(101)2 左移 1位 ,(r)2=(010)2=2 . ??????????????????rNmmmmmmmmmWNkXkXNkXNkXkXkX)]2()([)2()2()()(1111四 . 的計(jì)算 由于 DIF蝶形運(yùn)算的兩節(jié)點(diǎn)的距離為 N/2m , 所以蝶形運(yùn)算可表為： rNW (1)進(jìn)行原位運(yùn)算； (2)運(yùn)算量相同 ,均為（ N/2) Log2N次復(fù)乘 ,N Log2N次復(fù)加。但 DIT也有輸入為自然順序 ,輸出為倒位序的情況。 a.(DIT) b.(DFT) rNWrNW?1 1 1 1 rNWrNW? IFFT算法 一 .稍微變動(dòng) FFT程序和參數(shù)可實(shí)現(xiàn) IFFT ? ?? ?nkNNkNnnkNWkXNkXI D F TnxWnxnxD F TkX???????????1010)(1)()()()()( 比較兩式可知 ,只要 DFT的每個(gè)系數(shù) 換 成 ,最后再乘以常數(shù) 1/N就可以得到 IDFT 的快速算法 IFFT。 nkNWnkNW?LLN )21(211 ??二 .不改 (FFT)的 程序 直接實(shí)現(xiàn) IFFT nkNNkNknkNWkXNWkXNnx????????????1010*)(1])(1[)(? ?? ????????????????? ?)(1)(110kXD F TNWkXNnkNNk)( nx因此，????? ???? BABAWW nkNnkN ][,][? 這就是說 ,先將 X(k)取共軛 ,即將 X(k)的 虛部乘 1， 直接利用 FFT程序計(jì)算 DFT； 然后 再取一次共軛；最后再乘 1/N,即得 (n)。 x 線性卷積的 FFT算法 一 .線性卷積的長度 設(shè)一離散線性移不變系統(tǒng)的沖激響 應(yīng)為 ,其輸入信號(hào)為 .其輸出 為 .并且 的長度為 L點(diǎn) , 的 長度為 M點(diǎn) ,則： )(nx)(nx)(nh)(nh)(ny)(nx )(nh???????10)()()()()(Lmmnhmxnhnxny)(ny以實(shí)例說明： 0 1 2 3 1 2 3 )(mx)(mh0 1 21 1. 。 0 1 1 2 3 )(mx2 3 )( mh ?)1( mh ??????300)()()0(mmhmxy?????301)1()()1(mmhmxy。 0 1 2 3 )2( mh ?)3( mh ?。 ?????303)2()()2(mmhmxy?????306)3()()3(mmhmxy0 1 2 3 4 0 1 2 3 4 5 )4( mh ?)5( mh ?0 1 1 2 3 )(mx2 3 。 ?????305)4()()4(mmhmxy?????303)5()()5(mmhmxy0 1 2 3 4 5 1 3 3 5 6 6 )(ny1)( ?? MLny 的長度為可見。1)(),(.1 點(diǎn)補(bǔ)零點(diǎn)，至少為將 ??? LMNnhnx? ?；求 )()(.2 nhFFTkH ?? ?；求 )()(.3 nxF F TkX ?；求 )()()(.4 kHkXkY ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1