※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

FFT Butterfly DIT動作

基数2

A = A * W0 + (B * Wn)
B = A * W0 - (B * Wn)
  • Wn: Twiddle Factor
  • W0: 回転子が0の位置、正規化値ともいえる。次のように規定される。
    • Real=(入力Twiddle Factorビット幅-2)^2
    • Imagine=0

FFT Butterfly DIF動作

基数2

A = (A + B) * W0
B = (A - B) * Wn

基数4

A = (A + B + C + D) * W0
B = (A -iB - C +iD) * Wn
C = (A - B + C - D) * Wn1
D = (A +iB - C -iD) * Wn2

A出力は「Twiddle Factorビット幅-2)^2」を乗算することで出力を正規化している。
A出力の0ビットから下位「入力Twiddle Factorビット幅-2」ビットはZ(ハイインピーダンス)になるので、代わりに0をassignしておくこと。

基数2FFT

ω:回転子
A = A + B
B = (A - iB)ω

基数4FFT

A = A + B + C + D
B = (A - iB - C + iD)ω
C = (A - B + C - D)ω2
D = (A + iB - C - iD)ω3

16ポイントFFT時の基数2、基数4FFTの回転子の変化

基数2DIT

要素 回転子
0 0 0 0 0
1 0 0 0 8
2 0 0 8 4
3 0 0 8 12
4 0 8 4 2
5 0 8 4 10
6 0 8 12 6
7 0 8 12 14
8 8 4 2 1
9 8 4 2 9
10 8 4 10 5
11 8 4 10 13
12 8 12 6 3
13 8 12 6 11
14 8 12 14 7
15 8 12 14 15
stage1 stage2 stage3 stage4
  • θの計算:
要素の添え字を二進数で桁ごとにn3,n2,n1,n0と割り当てる
桁(2^x) 3 2 1 0
stage0 n3 0 0 0
stage1 n2 n3 0 0
stage2 n1 n2 n3 0
stage3 n0 n1 n2 n3

基数2DIF

要素 回転子
0 0 0 0 0
1 0 0 0 8
2 0 0 0 4
3 0 0 0 12
4 0 0 0 2
5 0 0 0 10
6 0 2 0 6
7 0 2 0 14
8 0 0 0 1
9 1 0 0 9
10 2 0 4 5
11 3 0 4 13
12 4 4 0 3
13 5 4 0 11
14 6 6 4 7
15 7 6 4 15
stage1 stage2 stage3 stage4
  • θの計算:毎ステージごとにTwiddleの刻みを半分に

基数4 DIF

要素 回転子
0 0 0
1 0 0
2 0 0
3 0 0
4 0 4
5 1 4
6 2 4
7 3 4
8 0 8
9 2 8
10 4 8
11 6 8
12 0 12
13 3 12
14 6 12
15 9 12
stage1 stage2
  • θの計算:毎ステージごとにTwiddleの刻みを1/4に


  • θの計算
    • 毎ステージごとにTwiddleの刻みを半分に
  • 配列の要素をスペクトルに
    • √(実数^2 + 虚数^2)
  • DIFとDITがある
  • 基数4と基数2でやる方法がある
    • 基数4:クロックあたりの効率がいい(高速)が回路規模は大きくなる
    • 基数2:クロックあたりの効率は悪い(低速)が回路規模は小さくなる



リンク