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

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

高速フーリエ変換(FFT)
計算量の比較
実装例・関連記事

高速フーリエ変換(FFT)

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

(1) $\begin{eqnarray*} W^{kn}_N=W^{kn\pm mN}\\ W^{kn}_N=W^l_NW^{k-l}_N \end{eqnarray*}$

計算量の比較

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

–	乗算回数	加算回数
DFT	$N^2$	$N(N-1)$
FFT	$Nlog_2(N)$	$Nlog_2(N)$

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

実装例・関連記事

–	フーリエ変換の原理に関してはこちら
①	フーリエ変換の原理・意味
②	逆フーリエ変換の原理・意味
③	離散フーリエ変換の原理・意味
④	高速フーリエ変換の原理・意味
⑤	【フーリエ変換】サンプリング周波数とナイキスト周波数の関係性・違い

–	実装例に関してはこちら
Python	FFTの実装例, IFFTの実装例, パワースペクトル解析の実装例, ローパスフィルタでノイズ除去
C言語	–
C#	FFTの実装例