俺総研

FFT についてわかりやすいサイトA DFT and FFT TUTORIAL


FFT のバタフライダイアグラムのコードをみても、いまいち何をやって
いるのかわからない。なので、自分で書いてみました。
自分のコードとほかの人のコードはだいたい同じになったので、ここまで
やってやっと人のが読めそうな気がしてきました。手を動かすのは大事。

前述のサイトのバタフライダイアグラム をみながらコードにしてみました。
演算の中身はないです。画面に "回転因子はこれ" で "xとyをバタフライ"
というメッセージを出すだけ。

N=8 でのバタフライ演算(中身なし)のコード


output

0
twiddle(0, 2)
butterfly(0, 1)
2
twiddle(0, 2)
butterfly(2, 3)
4
twiddle(0, 2)
butterfly(4, 5)
6
twiddle(0, 2)
butterfly(6, 7)
0
twiddle(0, 4)
butterfly(0, 2)
twiddle(1, 4)
butterfly(1, 3)
4
twiddle(0, 4)
butterfly(4, 6)
twiddle(1, 4)
butterfly(5, 7)
0
twiddle(0, 8)
butterfly(0, 4)
twiddle(1, 8)
butterfly(1, 5)
twiddle(2, 8)
butterfly(2, 6)
twiddle(3, 8)
butterfly(3, 7)