FFT - aroe's memopad

FFT Butterfly DIT動作

基数２

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動作

基数２

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

基数４

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出力の０ビットから下位「入力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時の基数２、基数４FFTの回転子の変化

基数２DIT

要素	回転子
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

基数２DIF

要素	回転子
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の刻みを半分に

基数４ 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：クロックあたりの効率は悪い（低速）が回路規模は小さくなる

---

• ６４点高速フーリエ変換回路

リンク