※ 引述《bernachom (Terry)》之銘言： : 請教一題.. : http://ppt.cc/(i27 : 應該是算很基本的題目，可是看課本就是看不太懂應該要怎麼算.. : 麻煩前輩們指導一下了 : 謝謝幫忙。 --- 我先大概說一下常見的 FFT alg. 假設 input signal x[n] 有 N-bits ( n=0~(N-1) ) 即 x[]: { x[0], x[1], ..., x[N-1] } 且令 N 為 power of 2， 則對 x[n] 做 N-bit DFT: DFT{ x[n], N } N-1 -j(2π/N)*k*n ≡ Σ x[n]*W(N,kn) , where W(N,kn) = e n=0 (N/2)-1 (N/2)-1 = Σ x[2r]*W(N/2,rk) + W(N,k) * Σ x[2r+1]*W(N/2,rk) r=0 r=0 = DFT{ x[2n], N/2 } + W(N,k)*DFT{ x[2n+1], N/2 } 所以可根據此遞迴快速算出 DFT{ x[n], N } 的值 ( 簡單說就是 Divide-and-Conquer ) 然後實作上 因為有很多 data 可以共用 所以最後畫出來的 flow diagram 如下: ( 以 4-bits DFT 為例 ) first level second level ↓ ↓ x[0] ────→─→ ⊕ ────→────→ ⊕ ─→ X[0] ＼／ ＼ ／ ／＼ ＼ ／ x[2] ────→─→ ⊕ ────→──＼─→ ⊕ ─→ X[1] W(4,0) (-1) ＼／ ＼／ ／＼ ／＼ x[1] ────→─→ ⊕ ────→──＼─→ ⊕ ─→ X[2] ＼／ W(4,0) ／ ＼ (-1) ／＼ ／ ＼ x[3] ────→─→ ⊕ ────→────→ ⊕ ─→ X[3] W(4,0) (-1) W(4,1) (-1) Note: 直線下標代表 weighted 、 斜線間沒相連 附帶一提 每層 level 可用 register 隔開儲存，可提高 working frequency 也能用 multiplexer 之類妥善安排每個 stage 的運算規則 以省下 register 所需個數 ------ 若上面的 flow diagram 原理 ok 的話 那剩下就只是簡單的 加法 + 乘法 + 時序性 問題 令 stage{ x[], N, i} 代表每層 level 的加法做完後的結果 且定義 state{ x[], N, 0} = { x[0], x[1], ..., x[N-1] } 而 stage{ x[], N, (logN)/(log2)} = { X[0], X[1], ..., X[N-1] } 是我們想要的最後結果 則原po問的問題: (a) a[] = { 1, -3, 0, 0} 為了符號上的簡化 定義 state{ a[], 4, i} = S(a,i) S( a,0 ;0) = a[0] = 1 S( a,0 ;1) = a[1] = -3 S( a,0 ;2) = a[2] = 0 S( a,0 ;3) = a[3] = 0 < 1st cycle> S( a,1 ;0) = a[0] + W(4,0)*a[2] = 1 + 1*0 = 1 S( a,1 ;1) = a[0] - W(4,0)*a[2] = 1 - 1*0 = 1 S( a,1 ;2) = a[1] + W(4,0)*a[3] = (-3) + 1*0 = (-3) S( a,1 ;3) = a[1] - W(4,0)*a[3] = (-3) - 1*0 = (-3) < 2nd cycle> S( a,2 ;0) = S( a,1 ;0) + W(4,0)*S( a,1 ;2) = 1 + 1*(-3) = (-2) S( a,2 ;1) = S( a,1 ;1) + W(4,1)*S( a,1 ;3) = 1 + (-j)*(-3) = 1+3j S( a,2 ;2) = S( a,1 ;0) - W(4,0)*S( a,1 ;2) = 1 - 1*(-3) = 4 S( a,2 ;3) = S( a,1 ;1) - W(4,1)*S( a,1 ;3) = 1 - (-j)*(-3) = 1-3j 也就是 DFT_4(a) = S( a,2) = { (-2), (1+3j), 4, (1-3j)} 相同的 b[] = { 2, 4, 0, 0} S( b,1 ;0) = b[0] + W(4,0)*b[2] = 2 S( b,1 ;1) = b[0] - W(4,0)*b[2] = 2 S( b,1 ;2) = b[1] + W(4,0)*b[3] = 4 S( b,1 ;3) = b[1] - W(4,0)*b[3] = 4 S( b,2 ;0) = S( b,1 ;0) + W(4,0)*S( b,1 ;2) = 6 S( b,2 ;1) = S( b,1 ;1) + W(4,1)*S( b,1 ;3) = (2-4j) S( b,2 ;2) = S( b,1 ;0) - W(4,0)*S( b,1 ;2) = (-2) S( b,2 ;3) = S( b,1 ;1) - W(4,1)*S( b,1 ;3) = (2+4j) DFT_4(b) = S( b,2) = { 6, (2-4j), (-2), (2+4j)} (b) (c) 小題只是想練習不要直接算 circular convolution 利用 DFT 會變成相乘的性質 再用 IDFT 得到 circular convolution 的結果 要注意的是 兩個 polynomial 相乘 其係數可以有類似 linear convolution 性質 但為了要套用 DFT 因此才會對 a 和 b 的 coefficient, extend 到 4-bit 不然頻譜上會發生 alasing 的問題 原 po 可以練習做 2-bits DFT 的 case 看最後結果會如何 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.47.130