Search on the blog

2011年8月7日日曜日

サルでも分かるFFT(2)

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

 結局のところ、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を利用した多倍長整数乗算の高速化」にトライしようかと思います。

0 件のコメント:

コメントを投稿