FFTライブラリ開発

　Web上にある複数のFFTコードを参考にした。いずれも、C で記述されており、VB.NETに、置きかえた。当然、Cooly-Turky アルゴリズムである。C の場合、Forループはかなり柔軟なので、VB のForループでは置きかえられないことが多く、While などにする必要がある。そのまま真似たとしても、文法エラーやコンパイルエラー、実行時エラーなど一切起こらなく、一見まことしやかに動いているように見えるので、要注意である。FFT自体が目的ではないので、ここではこれ以上突っ込まない。

　Sin、Cos は、頻繁に使うので、一々関数を呼び出していると時間が掛かってしまう。そこで、予め必要なものをテーブル化する。原理的には1/4周期があれば、再現できるが、面倒なので、2π 分もつ。一般に、データ数をNとすれば、原始根は、2π/N から求められる。また、各回転子は、i = 0～N-1 の範囲で、2π*i/N から算出する。一見、Nが変わると、テーブルも作り直しと思われるが、以下のように考えると、Nmax で作成しておけば、良いことが分かる。

　データ数N は、2^m なので、Nmax と、N との比は、必ず整数(2^k= 2^(Lm-m))となる。つまり、最大のテーブルを2^kきざみとしてアクセスすれば良い。今、Nmax = 8 とすれば、N = 4 で、i = 3 は、

なので、テーブルのインデックスの6 = 3 * 2^(3-2)を参照すれば良い。

　Cos は、Sinテーブルにて参照できる。2の冪乗は計算しないで、テーブル参照で行っている。

入力は、整数の複素数として、FFT順変換と逆変換したものである。逆変換で、元に戻っているのが分かる。但し、結果は全て整数化している。

入力は、二組の整数の実数を、同時にFFTしている。順変換の結果と、その逆変換の結果である。逆変換で、入力の実数が再生しているのが分かる。但し、結果は全て整数化している。

　データ数が16の例で、後半を0にして、循環畳み込みした例。つまり、疑似線形化した例。

100進数の1020304 * 1020304 =1041020252416 の乗算と同じ。結果は合っている。　

全くことなる結果となった。しかし、循環の意味は、要素がサイクリックに扱われることで、以下のように考えると良い。

1	2	3	4
1	2	3	4
4	8	12	16
6	9	12	3	3*1は循環し後ろにつながる
6	8	2	4	同じく循環(赤)
4	1	2	3	同じく循環(赤)
20	26	28	26	緑の26が先頭で、右方向に循環して読みとる

上位の結果が後ろに回り込むことになる。これを、後ろに0を埋めると、以下のようになる。

1	2	3	4	0	0	0	0
1	2	3	4	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	4	8	12	16
0	0	0	3	6	9	12	0
0	0	2	4	6	8	0	0
0	1	2	3	4	0	0	0
0	1	4	10	20	25	24	16

赤は、回り込みである。同様に、結果は、緑の1を先頭に、右方向に循環する。最後が0となる。これは、線形畳み込みと同じ結果となる。つまり、フーリエ変換を騙すのである。