高速フーリエ変換 ( Fast Fourier Transsformation )
離散フーリエ変換の対称性に着目して、計算量を大幅に削減することができます。
これを高速フーリエ変換と言います。今回は、高速フーリエ変換のお話...。
のはずだったのですが、きんくまデザイン様が既に AS3.0 用のコードを公開しておられましたので、こちらにほんの少しだけ手を加えます。きんくまデザイン様、ありがとうございます。
きんくまデザイン様のコードは、こちらです。
/** * FFT * Fast Fourier Transformation 高速フーリエ変換 * @usage <pre> Fourier.FFT( inputReal, inputImaginary, outputReal, outputImaginary, spectrum );</pre> * @param inputReal (Array) * @param inputImaginary (Array) * @param outputReal (Array) * @param outputImaginary (Array) * @param spectrum (Array) * @return (Boolean) */ public static function FFT( inputReal:Array, inputImaginary:Array, outputReal:Array, outputImaginary:Array, spectrum:Array ):Boolean { var N:uint = inputReal.length; var ar:Array, ai:Array; var m:int, mh:int, i:int, j:int, k:int, irev:int; var wr:Number, wi:Number, xr:Number, xi:Number; ar = new Array(); ai = new Array(); for(i = 0; i < N; i++) { ar[i] = inputReal[i]; ai[i] = inputImaginary[i]; } i = 0; for (j = 1; j < N - 1; j++) { for (k = N >> 1; k > (i ^= k); k >>= 1); if (j < i) { xr = ar[j]; xi = ai[j]; ar[j] = ar[i]; ai[j] = ai[i]; ar[i] = xr; ai[i] = xi; } } var angle:Number = 2 * Math.PI / N; for (mh = 1; (m = mh << 1) <= N; mh = m) { irev = 0; for (i = 0; i < N; i += m) { wr = Math.cos(angle * irev); wi = Math.sin(angle * irev); for (k = N >> 2; k > (irev ^= k); k >>= 1); for (j = i; j < mh + i; j++) { k = j + mh; xr = ar[j] - ar[k]; xi = ai[j] - ai[k]; ar[j] += ar[k]; ai[j] += ai[k]; ar[k] = wr * xr - wi * xi; ai[k] = wr * xi + wi * xr; } } } for(i = 0; i < N; i++) { outputReal[i] = ar[i]; outputImaginary[i] = ai[i]; spectrum[i] = Math.sqrt( ar[i]*ar[i] + ai[i]*ai[i]); } return true; }
使い方は、以下の通りです。
// 高速フーリエ変換をする、入力(実数と虚数)を配列で用意します。 // 実数の配列の長さは、2の累乗にして下さい。例: 512, 1024, 2048,... // 虚数が無い場合は、実数と同じ長さで、要素が全て 0 の配列を用意します。 // 高速フーリエ変換後の値を保持する配列を用意します。 var outputReal:Array = new Array(); // 実数部 var outputImaginary:Array = new Array(); // 虚数部 var spectrum:Array = new Array(); // スペクトル // 実行します。 // FFT メソッドは、Fourier クラスのクラスメソッドとします。 Fourier.FFT( inputReal, inputImaginary, outputReal, outputImaginary, spectrum ); // 結果が、outputReal (実数部)、outputImaginary (虚数部)、 spectrum (スペクトル) に入っています。
以上です。
graphakt.