按時間抽選的基2-fft算法(ppt30頁)(編輯修改稿)
2025-03-22 12:37 本頁面
【文章內容簡介】 ??NkNNkN kkXWkXkXkXWkXkXX2(k)也可以進行相同的分解： 注意：通常我們會把 寫成 。 kNW 2/ kNW 2)()( 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個蝶形 ，每個蝶形有一次復乘兩次復加。 NN 2lo g2 NN 2log2)、所以 M級共有 次復乘和 次復加。 3)、若直接計算 DFT， 需 N2次復乘和 N(N1)次復加。 顯然，當 N較大時，有： 例如 ， N=210=1024時 221048576 ( /2)log 5120NNN ??FFT算法與直接計算 DFT所需乘法次數(shù)的比較曲線 DIT―FFT 的運算規(guī)律及編程思想 FFT的每級（列）計算都是由 N個復數(shù)數(shù)據(jù)（輸入）兩兩構成一個蝶型（共 N/2個蝶形）運算而得到另外 N個復數(shù)數(shù)據(jù)（輸出）。 當數(shù)據(jù)輸入到存儲器以后，每一組運算的結果， 仍然存放在這同一組存儲器中 直到最后輸出。 例：將 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
教學課件相關推薦
鄂ICP備17016276號-1