【DFT】離散フーリエ変換の原理・計算式

この記事では、離散フーリエ変換（DFT）の公式と原理について入門者向けに紹介します。 [latexpage]

離散フーリエ変換(DFT)の計算式
【計算例】離散フーリエ変換
サンプリング周波数、ナイキスト周波数、エイリアシング
【実装例】C言語でDFT
関連ページ

離散フーリエ変換(DFT)の計算式

音楽や画像データはデジタルの周期信号です。そのため、アナログの周期信号を前提とする「フーリエ変換」の計算式はそのまま利用できません。つまり、フーリエ変換の元の式そのままではコンピュータで利用できません。

そこでコンピュータ上では「離散フーリエ変換（Discrete Fourier Transform）」と呼ばれる離散データ向けのフーリエ変換を使います。

離散周期信号$f(n)$を離散フーリエ変換する式は次のようになります。 \begin{eqnarray} F(k)=\sum^{N-1}_{n=0}f(n)W^{kn}_N \end{eqnarray}

ここで、$N$はサンプル数、$W_N=e^{-j\frac{2\pi}{N}}$は回転子（位相回転因子）です。一方、離散逆フーリエ変換の式は次のようになります。

\begin{eqnarray} f(n)=\frac{1}{N}\sum^{N-1}_{k=0}F(k)W^{-kn}_N \end{eqnarray}

【計算例】離散フーリエ変換

次のようなアナログ周期信号$f(t)$を用意します。

\begin{eqnarray} f(t)=sin(2\pi f_1t)+sin(2\pi f_2t)+Noise \end{eqnarray}

ここで$f_1=10, f_2=20$, Noiseは雑音とします。次にアナログ周期信号$f(t)$をンプル数$N=256$、サンプリング周波数$f_s=100$でデジタル周期信号$f(n)$に変換します。そして、デジタル周期信号$f(n)$を離散フーリエ変換した結果は次の通りです。

右が入力信号$f(n)$、左が振幅スペクトル$|F(k)|$です。振幅スペクトルを見ると、周波数10, 20のピークが大きいことがわかります。これは、入力信号に周波数10と20の周波数成分が多く含まれていることを表しています。このように、振幅スペクトルから入力信号の周波数成分を解析できます。

サンプリング間隔が0.01なのでサンプリング周波数は100Hzとなります。高周波側(80, 90Hz)のスペクトルは、0Hz～50Hzの正の周波数(sin)に対して、-50Hz～0Hzの負の周波数(cos)に相当する成分です。入力信号が実数の場合、低周波側と高周波側のスペクトルは対称になりますが、複素数の場合は非対称になります。

サンプリング周波数、ナイキスト周波数、エイリアシング

用語	概要
サンプリング周波数$f_s$	1秒間にサンプリングされるデータ数です。例えば、サンプリング周波数$f_s$が100[Hz]ならば1秒間に100個の割合でデータを取得します。
ナイキスト周波数$f_n$	サンプリングしたときに表現できる、周波数の最大値をナイキスト周波数$f_n$といいます。標本化定理よりサンプリング周波数$f_s$の半分となります。つまり、ナイキスト周波数$f_n$は正しく検出できる最大の周波数となります。例えば、サンプリング周波数$f_s=100[Hz]$なのでナイキスト周波数$f_n$は50[Hz]となります。高速フーリエ変換で周波数解析を正確に行うためには、入力信号の最大周波数の2倍以上のサンプリング周波数でサンプリングする必要があります。先程の数値例では入力信号の最大周波数が20[Hz]なので、サンプリング周波数は最低でも40[Hz]にすることになります。
エイリアシング	サンプリング周波数$f_sが不十分な場合（ナイキスト周波数$f_n$より高い周波数の信号を標本化）、標本化した際に折り返し (エイリアシング) という現象を生じ、元信号に忠実に復元できません。