高速フーリエ変換（FFT）の計算式の原理・意味

この記事では、高速フーリエ変換（FFT）の公式と原理について入門者向けに紹介します。

[latexpage]

高速フーリエ変換(FFT)

コンピュータでフーリエ変換を実装する場合、離散フーリエ変換を利用します。
しかし、離散フーリエ変換は計算量が多く、処理時間が掛かるという欠点があるためあまり実用的ではありません。
そこで、実際には計算量の少ない「高速フーリエ変換（FFT：Fast Fourier Transform）」が用いられます。
高速フーリエ変換では、回転子$W^kn_N$の「周期性」「指数性」を使って、計算式の結合・分解を行い、計算量を削減します。
\begin{eqnarray} W^{kn}_N=W^{kn\pm mN}\\ W^{kn}_N=W^l_NW^{k-l}_N \end{eqnarray}

計算量の比較

離散フーリエ変換（DFT）と高速フーリエ変換（FFT）の計算量を比較します。
離散信号のサンプル数が$N$のときの計算回数を以下にまとめました。

特に乗算はコンピュータにとって重い処理なので、この回数を$N^2$から$Nlog_2(N)$に削減できることは大きな利点です。
ただし、FFTはサンプル数Nが2のべき乗の時にしか利用できません。

実装例・関連記事