快速傅里葉變換(編輯修改稿)
2024-09-11 23:53 本頁面
【文章內(nèi)容簡介】 llkN WlxWlxkX????????14/04/42/14/04/3 )()(NllkNkNNllkN WlxWWlx)()( 42/3 kXWkX KN??1,. .. .. .1,0)()()()()()(442/34142/31 ????????????NkNNkN kkXWkXkXkXWkXkX??????????14/0)12(2/214/022/22 )21()2()(NlklNNllkN WlxWlxkX????????14/04/62/14/04/5 )()(NllkNkNNllkN WlxWWlx1, .. .. ..1,0)()()()()()(462/54262/52 ????????????NkNNkN kkXWkXkXkXWkXkXX2(k)也可以進行相同的分解： 注意：通常我們會把 寫成 。 kNW 2/ kNW2)()( 62/5 kXWkX KN??N點 DFT的第二次時域抽取分解圖 (N=8) 2點DFT 2點DFT 2點DFT 2點DFT x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X3(0) X3(1) X4(0) X4(1) X5(0) X5(1) X6(0) X6(1) 08W28W08W28WX1(0) X1(1) X1(2) X1(3) X2(0) X2(1) X2(2) X2(3) 38W28W18W08WX(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 4點DFT 4點DFT x(0) x(2) x(4) x(6) x(1) x(3) x(5) x(7) X1(0) X1(1) X1(2) X1(3) X2(0) X2(1) X2(2) X2(3) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 38W28W18W08W)1()0()()]([)(32314/04/333xWxWlxlxD F TkXkNlklN???? ???)1()0()1()0()1()1()0()0(30233123330233xWxxWxXxWxX??????8 8 08WX3(0) X3(1) x(0)=x3(0) x(4)=x3(1) N點 DIT―FFT 運算流圖 (N=8) x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 0NW0NW0NW0NW0NW2NW0NW2NW0NW2NW1NW3NW DIT―FFT 算法與直接計算 DFT運算量的比較 22l o g2 NNN ??1)、 N=2M的 DFT運算可分成 M級，每一級有 N/2個蝶形 ，每個蝶形有一次復(fù)乘兩次復(fù)加。 NN 2lo g2 NN 2lo g2)、所以 M級共有 次復(fù)乘和 次復(fù)加。 3)、若直接計算 DFT， 需 N2次復(fù)乘和 N(N1)次復(fù)加。 顯然，當 N較大時，有： 例如 ， N=210=1024時 221048576 20 4. 8( / 2 ) lo g 51 20NNN ??FFT算法與直接計算 DFT所需乘法次數(shù)的比較曲線 DIT―FFT 的運算規(guī)律及編程思想 FFT的每級（列）計算都是由 N個復(fù)數(shù)數(shù)據(jù)（輸入）兩兩構(gòu)成一個蝶型（共 N/2個蝶形）運算而得到另外 N個復(fù)數(shù)數(shù)據(jù)（輸出）。 當數(shù)據(jù)輸入到存儲器以后，每一組運算的結(jié)果， 仍然存放在這同一組存儲器中 直到最后輸出。 例：將 x(0)放在單元 A(0)中，將 x(4)放在單元 A(1)中， W80 放在一個暫存器中。 將 x(0) + W80x(4) → 送回 A(0)單元 將 x(0) W80x(4) → 送回 A(1)單元 08WX3(0) X3(1) x(0) x(4) 1） 原位運算 (亦稱同址計算 ) x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 0NW0NW0NW0NW0NW2NW0NW2NW0NW2NW1NW3NW回顧： N點 DIT―FFT 運算流圖 (N=8) 如上所述， N點 DIT―FFT 運算流圖中，每級都有N/2個蝶形。每個蝶形都要乘以因子 WNP， 稱其為 旋轉(zhuǎn)因子 ， p稱為旋轉(zhuǎn)因子的指數(shù)。 2)旋轉(zhuǎn)因子的變化規(guī)律 觀察 FFT運算流圖發(fā)現(xiàn)，第 L級共有 2L1個不同的旋轉(zhuǎn)因子。 N=23=8時的各級旋轉(zhuǎn)因子表示如下： L=1時， WNp=WN/4J， N/4 =21 =2L， J=0 L=2時， WNp =WN/2J， N/2 =22 =2L， J=0， 1 L=3時， WNp =WNJ， N =23 =2L， J=0， 1， 2， 3 對 N=2M的一般情況，第 L級的旋轉(zhuǎn)因子為： 12, . . . ,1,0 12 ??? ?LJPN JWW L?MLMLML N ?? ???? 222212,...,1,0 122 ????? ??? ?? LJNJNPN JWWW LMMLLMJp ??? 2 設(shè)序列 x(n)經(jīng)時域抽選 (倒序 )后，存入數(shù)組 X中。如果蝶形運算的兩個輸入數(shù)據(jù)相距 B個點 (B=2L1)， 應(yīng)用原位計算，則蝶形運算可表示成如下形式： pNLLLpNLLLWBJXJXBJXWBJXJXJX)()()()()()(1
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1