FFT（Fast Fourier Transform）

FFTとは、1965年にベル研究所のJames W. Cooley氏とJohn W. Tukey氏が考案した、離散的フーリエ変換と逆変換を高速に計算する手法。画像や音声、映像などのマルチメディアデータの処理で多用される重要なアルゴリズムである。

信号の中にどの周波数成分がどれだけ含まれているかを抽出する処理をフーリエ変換という。入力波形をいくつかのグループに分けて計算し、計算順序を工夫することにより計算量を大幅に減少させたアルゴリズムがFFTである。グループの数をNとした時の演算の回数は、通常の変換ではNの2乗に比例するが、FFTでは NlogN に比例する。

　○　

　⇒