2012/01/15

FFT 基礎実験 Java

FFT(Fast Fourier Transform)高速フーリエ変換も作ってみる。昨日の音声ファイル用DFTの一部を改造してFFTを組み込む。機能ごとにクラスをきれいに分けて作ると簡単に組み込むことができることを実感。

FFTのアルゴリズムはコンピュータ処理に適した巧妙なしくみになっている。バタフライ演算で計算を減らす工夫がされている。データが多くなればなるほど、DFTとの差が出てくる。DFTだとデータ数Nとすると、N^2の乗算が必要なのに対して、FFTはN log2N/2で済むようだ。少ないサンプル数で乗算を数えてみたら、計算式通りではないが、まぁ近い数かな。同じ計算で符号違いも多いので、うまく最適化すれば、より高速になる。実際の実用レベルのFFTではそのように作られているようだ。とりあえず理屈どおりに組み込んで試してみると、DFTに比べて、圧倒的な処理スピードは体感できた。これなら1万サンプル以上でも苦ではない。

音声ファイルにおけるフーリエ変換の細々したことはこっちのDFTページを見てください。とりあえず結果だけは下のようになった。

sin波1000, 5000, 10000,15000,20000Hzを合成した波形をFFTにかけてみる。出力ファイルをLibreOfficeのCalcでグラフ化。出力を確認。ピンクはdB表示でグリーンはリニア表示。



sound programming 目次はこちら