高速フーリエ変換 【FFT】 Fast Fourier Transform

概要

高速フーリエ変換（FFT）とは、時系列に並んだデジタル信号の標本列を周波数成分の集合で表す離散フーリエ変換(DFT：Discrete Fourier Transform)をコンピュータで高速に計算する手法。画像や音声、映像などの処理で多用される。

フーリエ変換は信号の中にどの周波数成分がどれだけ含まれているかを抽出する処理だが、FFTでは入力波形をいくつかのグループに分け、計算順序を工夫することにより通常の計算方式よりも大幅に少ない計算量で変換を行うことができる。標本数がNのとき、素朴なフーリエ変換はO（N²）の計算量となるが、FFTでは（Nが2の累乗ならば）O（NlogN）で済む。

1965年にAT&Tベル研究所（当時）のジェームズ・クーリー（James W. Cooley）氏とジョン・テューキー（John W. Tukey）氏が考案した、クーリー・テューキー型（Cooley-Tukey algorithm）が最も有名だが、他にも様々な手法が提唱されている。逆変換は逆高速フーリエ変換（IFFT：Inverse Fast Fourier Transform）という。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。