フーリエ変換(2)

フーリエ変換（まとめ）

ある関数を別の関数に何らかの方法で変形することを「変換」と呼ぶ．

キーワード：フーリエ変換，離散フーリエ変換，高速フーリエ変換の違いを理解しよう．

  1. フーリエ変換は，任意の連続関数を周期関数（sin, cos）の和に変換する．
  2. コンピュータでは連続関数（＝無限にデータが必要）を扱うことはできないので，「離散化」を行い「有限個」の配列データに格納する．
  3. 離散化された有限個のデータに対して行うフーリエ変換を「離散フーリエ変換(DFT)」と呼ぶ．
  4. DFTは，大変計算時間がかかるので，計算アルゴリズムの工夫で計算を高速化させたものを「高速フーリエ変換(FFT)」と呼ぶ．
  5. 一般的にFFTではデータ数 $N$ が2の累乗のときに計算時間が大幅に短縮される．
  6. DFTとFFTの計算結果は（計算時の丸め誤差分を除いて）同じである．

フーリエ変換に関する用語を，以下のようにまとめておく．

対象とする信号の長さ 扱う周波数 特徴
フーリエ変換 無限に続く連続信号 無限の周波数の$\cos, \sin$の重ね合わせで表現 任意の連続関数に適用できるが，コンピュータでは連続関数（＝無限個の値の集合）は扱えない
離散フーリエ変換(DFT)：今日の実習 有限長の$N$ 個の離散信号 有限の$N$ 個の周波数の$\cos, \sin$の和で表現 ある有限長の信号を離散化（サンプリング）し，その刻みに相当する周波数まで分解できる．ある有限長の信号が，繰り返されることを前提とする
高速(離散)フーリエ変換(FFT) 同上 同上 データ数が小さな素数の累乗(特に2n)で表される時，計算量が劇的に少なくなる

実際のスペクトル解析には FFT（高速フーリエ変換）が広く用いられているが，フーリエ変換の原理を知るにはまず DFT について学ぶと良い．
DFT と FFTの違いは，計算量（つまり計算時間）にあり，計算結果は基本的に同じになるはずである．

DFT の計算時間は $N^2$ に比例するのに対し，FFTは $N \log_2(N/2)$ の計算時間しかかからないので， 特にデータ数 $N$ が大きくなるほど，FFTによる時間短縮の効果は大きくなる．

DFT（離散フーリエ変換）の参考ソースファイル

参考までにDFTを行う関数を示す．
複素数クラス complex を使用する．

離散フーリエ変換の式と見比べて，処理内容を確認しよう．
\begin{align} F[\omega]=\sum_{t=0}^{N-1} f[t]\ e^{-j\omega \frac{t}{N}}\ dt \end{align}

 
#include <complex>
#include <cmath>
using namespace std;

const double pi = 2.0*asin(1.0);

void dft(const double in[], complex<double> out[], const int N)
//
//  離散フーリエ変換(DFT) 配列版
//  元データは実数，変換後は複素数
//
//  in	:  元データ．これは変更しない．実数の配列．
//  out :  計算結果．こちらは複素数． 呼び出しもとで確保する必要あり．
//  N   :  データ個数．複素数は1個と数える
//
{
    const double dt = 1.0 / 44100.0;   /* サンプリング周期 */

    /*  出力用の配列を初期化 */
    for(int i=0; i<N; i++) {
        out[i] = complex<double>(0,0);  /* これでゼロに初期化できる */
    }

    for(int f=0; f<N; f++) {

        /* 以下のループで 1個のF[omega]を計算する．内積の計算 */
        double omega = 2.0 * pi * f;
        for(int t=0; t<N; t++) {
            /*  積分の中身の計算 */
            out[f] += in[t] * exp( complex<double>(0.0, -omega * t/N) ) * dt;
        }
    }
}