※ 引述《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