推 bernachom :謝謝您詳細的說明，我來看一下，但是我反應沒這麼快 12/25 14:11
→ bernachom :需要一些時間看一下，謝謝您 12/25 14:11
※ 引述《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