高速フーリエ変換 ( 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;

}

使い方は、以下の通りです。

// 高速フーリエ変換をする、入力（実数と虚数）を配列で用意します。
// 実数の配列の長さは、２の累乗にして下さい。例: 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.