FFTとDFTの比較
フーリエ変換の時間軸を離散化したものが
離散フーリエ変換(discrete fourier transform)で
その対象性を利用して早く計算できるようにしたものが
工学的には非常に良く見る高速フーリエ変換(Fast Fourier Transform)。
理屈はいまいち良くわかっていませんがWikiに詳しく書いてあります。
これと信州大学のWebサイト(高速フーリエ変換（FFT))
を参考になんとなくの理解は
信号の配列に複素平面上の単位円上をぐるぐる回る信号をかけて総和を取ると
そのぐるぐる回る周波数のレベルがでてくるイメージ。
DFTはそのまま実装すれば良いのでわかりやすいですが
FFTはwikiに乗ってるプログラム例をそのまま実装してみても
いまいち正しいかわからないのでまずはDFTとFFTを比べてみます。
■入力
とりあえずサンプリング周波数は48k 1kのサイン派を入れることにする。
■結果
FFTかけたものとDFTかけたものをグラフにしてみるとぴったり重なるので
実装はミスがなさそう。1kのところにもピークが立っているのがわかる。
直流成分が見えているのは4のn乗の配列を入力としてるので
平均値が0にならないからだと思います。
横軸周波数をログにしないと良く見る左右対称のグラフが書けます
47kHzにも同じピークが見えているのは
sinx * siny = {cos( x + y ) + cos( x - y )} / 2 のx-yの部分が見えてるのかな？
サンプリング周波数48k-信号周波数1k = 47kHzがいる。
ただしサンプリング定理によると
サンプリング周波数の半分までしか信号を表せないのでこれに何の意味があるのか謎。
あとでちゃんと考えよう。
■FFTはどれくらい早いのか
理論上はDFTはO(n^2), FFTはO(n logn)なので logn / n 倍くらい早いはず。
窓を4^7=16384サンプルとしたときは4.2倍早い。
・・・明らかに実測はもっと早くて他のサイトによると違うのであとで確認します。
とりあえず実測を比較
高速というだけのことはあって確かにすごく早い。
DFTでn=4^8ではもうやる気が起きない。
FFTでもだいたいn=4^9くらいまでが現実的な気がします。
大体理論どおり。
ただDVDなどで一般的に使用される
サンプリングレート48kの音声信号を対象とすると
65536サンプルは既に1.5秒程度となり
応答を見るにはちょっと長すぎる感じ。
画像を対象にするにしても4k2k程度が限界で
4096サンプル程度までできれば十分な気がします。
■結論
FFTはすごく早い。
結果はDFTと同じ。
