まずはC言語・浮動小数点でFFT

FFTは40年以上前に確立されたアルゴリズムなので、Cのソースは巷に氾濫しています。まずは普通にC言語・浮動小数点で試してみましょう。これが原点になります。(コーヒーブレーク１、２） (1) C言語によるFFTの記述 VC++で行う1024ポイントFFT。 変数は浮動小数点(double)。 (2) 浮動小数点のFFTを実行する 入力波形と三角関数のファイルを読み込む。 FFTの結果6kHzにスペクトルが見つかる。 (3) 結果の検証 スペクトルの大きさは500近くある。 スペクトルは入力波形よりも500倍大きくなる。 Back	�@FFTとは どんな複雑な波形でも正弦波に分解できる・・・これはフランスの数学者フーリエが発見した定理で、それを行う手法を「フーリエ変換」といいます。フーリエ変換をデジタル化したものをDFT(Discrete Fourier Transform)といい、それを高速化したものをFFT（Fast Fourier Transform）といいます。近年ではほとんどの場合FFTが適用されます。
	�A乗算の数を減らして高速化 FFTは ab+ac = a(b+c) といった因数分解を繰り返して乗算回数を減らすアルゴリズムです。複素乗算の数はDFTの場合N^2ですが、FFTだと（N/2)log2(N)となります。以下の表は複素乗算数の比較です。 ﾎﾟｲﾝﾄ数N DFT FFT 比率％ 4 16 4 25.0 16 256 32 12.5 64 4,096 192 4.69 256 65,536 1,024 1.56 1024 1,048,576 5,120 0.49 4096 16,777,216 24,576 0.15 (今回取り上げるFFTは1024ポイントです）

Top Page