サルでも分かるFFT（2）

　ふーむ、前回の「サルでも分かるFFT(1)」から時間が空きましたが、第２弾。（※サルは無知な自分のこと。）

　結局のところ、DFTでやるのは、単なる一次変換なので、実装するのはそんなに難しくないです。行列の積と、複素数の扱いくらいが書ければ、簡単にできます。（難しいのは、えられた結果の物理的か解釈だと思います。）また、FFTは、DFTを高速に実施するための一手法であると、前回書きました。

　前回の疑問点が解決したので、それを書きます。

1. 連続信号を離散でとっているので、周波数成分分解のパターンはいくつか存在するはず。DFTでは、解が一意に求まるが、どんな解が選ばれてるの？

これは、実際にvisualizingするツールを作っているときにいろいろ気付きました。

DFTによってえられる周波数成分は、以下の2式の条件を満たしています。

1つ目の式は、周波数スペクトラムが、ある周波数を中心に左右対称になっていることを表しています。

2つ目の式は、中心周波数から同じ距離にある対象な周波数成分は、反対の位相を持っているということを意味します。

以下は、私が作ったvisualizer(※Google Chromeでの閲覧推奨)が吐き出した周波数スペクトラムです。極座標系にプロットしているので、これを見ると、式の意味が一目瞭然です。（上：時間軸波形、下：対応する周波数スペクトラム）

2. F[i]のiって何？F[1]は周波数が1っていうのは分かるけど、これは1[Hz]?それともサンプリング間隔に対して、1倍の周波数を持っているという意味?

これは、サンプリング間隔に対する周波数です。実際の物理的な時間単位とは違います。

すべてのサンプリングをとるのに要した時間を1[s]と考えたときに、F[i]は、i[Hz]の周波数成分となっています。

3. その他

DFTしてえられた周波数成分（F[i], i=0,1, ... N.）を実際の物理的な波に変換するときどうすればいいか？

F[i]に対応する正弦波は以下の式で表されます。

さてさて、記事のタイトルが「サルでも分かるFFT」なので、FFTをやらないといけません。FFTの効果を実感したいなら、サンプル数が10^5とか10^6とかないといけません。(O(N^2)とO(N*log N)の対比なので。)

音楽CDのデータをとってきてそれにDFTかけてみる。

にチャレンジしようと思いましたが、データの抽出に時間がかかりそうなので、「FFTを利用した多倍長整数乗算の高速化」にトライしようかと思います。