快速傅立葉變換ppt課件(編輯修改稿)
2025-05-26 02:01 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ????????lkNlllkNllkNllkNWlxkXWlxkXWlxkXWlxkX 亦即 , )4()0()1()0()1()4()0()1()0()0(031233030233xWxxWxXxWxxWxXNN????????)6()2()1()0()1()6()2()1()0()0(041244040244xWxxWxXxWxxWxXNN????????)5()1()1()0()1()5()1()1()0()0(051255050255xWxxWxXxWxxWxXNN????????)7()3()1()0()1()7()3()1()0()0(061266060266xWxxWxXxWxxWxXNN???????? (0) (4) (2) (6) (1) (5) (3) (7) W N 0 W N 0 W N 0 W 0 N 1 1 1 1 X (0) X (1) X (0) X (1) X (0) X (1) X (0) X (1) 3 3 4 4 5 5 6 6 W N 0 W N 2 W N 0 W N 2 1 1 1 1 X (0) X (1) X (2) X (3) X (0) X (1) X (2) X (3) 1 1 1 2 1 2 2 2 W W W W N 0 N 1 N 2 N 3 1 1 1 1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) xxxxxxxx因此 ,8點(diǎn) DFT的 FFT的運(yùn)算流圖如下 這種 FFT算法 ,是在時(shí)間上對(duì)輸入序列 的次序是屬于偶數(shù)還是屬于奇數(shù)來(lái)進(jìn)行分 解的 ,所以稱作按 時(shí)間 抽取的算法 。 二 .運(yùn)算量 由上述分析可知 ,N=8需三級(jí)蝶形運(yùn)算 N=2 =8,由此可知 ,N=2L 共需 L級(jí)蝶形運(yùn)算 , 而且每級(jí)都由 N/2個(gè)蝶形運(yùn)算 組成 ,每個(gè)蝶 形運(yùn)算有一次復(fù)乘 ,兩次復(fù)加。 (DIT) 3 因此 ,N點(diǎn)的 FFT的運(yùn)算量為 復(fù)乘 : mF =（ N/2） L=（ N/2） log2 N 復(fù)加 : aF =N L=N log2 N 由于計(jì)算機(jī)的乘法運(yùn)算比加法運(yùn)算 所 需的時(shí)間多得多，故以乘法作為比較 基準(zhǔn) .如表 41所示 (）。 (0)=X0(0) X1(0) X2(0) X3(0)=X(0) (4)=X0(1) X1(1) X2(1) X3(1)=X(1) (2)=X0(2) X3(2)=X(2) (6)=X0(3) X3(3)=X(3) (1)=X0(4) X1(4) X2(4) X3(4)=X(4) (5)=X0(5) X3(5)=X(5) (3)=X0(6) X3(6)=X(6) (7)=X0(7) X1(7) X2(7) X3(7)=X(7) W W W W N 0 N 0 N 0 N 0 1 1 1 1 W W W W N 0 N 2 N 0 N 2 1 1 1 1 W W W W N N N N 0 1 2 3 . . . . . . . . . . . 三 .DIT的 FFT算法的特點(diǎn) 輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲(chǔ)器。 xxxxxxxx?????????????rNmmmrNmmmWjXkXjXWjXkXkX)()()()()()(1111),3()6(),2()2(),1()4(),0()0(0000XxXxXxXx????).7()7(),6()3(),5()5(),4()1(0000XxXxXxXx???? 設(shè)用 m(m=1,2,… ,L)表示第 m列 。用 k,j表示蝶形 輸入數(shù)據(jù)所在的（上 /下）行數(shù) (0,1,2,… ,N1)。這時(shí)任何一個(gè)蝶形運(yùn)算可用下面通用式表示， 即 由 運(yùn)算流圖可知 ,一共有 N個(gè)輸入 /出 行 ,一共有 log2 N=L列（級(jí)）蝶形運(yùn)算 (基本迭代運(yùn)算 ). 所以 ,當(dāng) m=1時(shí) ,則有（前兩個(gè)蝶形） 00010001)1()0()1()1()0()0(NNWXXXWXXX????00010001)3()2()3()3()2()2(NNWXXXWXXX???? 當(dāng) m=2時(shí) ,則有（前兩個(gè)蝶形） 當(dāng) m=3時(shí) ,則有（前兩個(gè)蝶形） ??????????????????2112211201120112)3()1()3()3()1()1()2()0()2()2()0()0(NNNNWXXXWXXXWXXXWXXX??????????????????1223122302230223)5()1()5()5()1()1()4()0()4()4()0()0(NNNNWXXXWXXXWXXXWXXX 可見(jiàn) ,在某列進(jìn)行蝶形運(yùn)算的任意兩個(gè)節(jié)點(diǎn) (行 )k和 j的節(jié)點(diǎn)變量 就完全可以確定蝶形運(yùn)算的結(jié)果 ,與其它行 (節(jié)點(diǎn) )無(wú)關(guān)。 這樣 ,蝶形運(yùn)算的兩個(gè)輸出值仍可放回蝶形運(yùn)算的兩個(gè)輸入所在的存儲(chǔ)器中 ,即實(shí)現(xiàn)所謂原位運(yùn)算。每一組(列 )有 N/2個(gè)蝶形 運(yùn)算 ,所以只需 N個(gè)存儲(chǔ)單元，可以節(jié) 省存儲(chǔ)單元。 )(),( jXkX mm)(),( 11 jXkX mm ?? 2 倒位序規(guī)律 由圖可知 ,輸出 X(k)按正常順序排 列在存儲(chǔ)單元 ,而輸入是按順序 : 這種順序稱作倒位序 ,即二進(jìn)制數(shù) 倒位。 ）；）； 7(),3(),5(),1(6(),2(),4(),0( xxxxxxxxn =0 0 n =1 0 n =0 1 n =1 1 n =0 1 n =1 1 0 1 0 1 0 1 0 1 xxxxxxxx),( 012 nnnx(n2) x(000) 0 乾 x(100) 4 兌 x(010) 2 離 x(110) 6 震 x(001) 1巽 x(101) 5 坎 x(011) 3 艮 x(111) 7 坤
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1