高速フーリエ変換

1965年にベル研究所のJames W. CooleyとJohn W. Tukeyが考案したアルゴリズム。

離散的フーリエ変換を高速に計算出来る。FFT (Fast Fourier Transform)。

離散的フーリエ変換は通常O(N*N)の計算量だが、高速フーリエ変換を使う事により最良の場合はO(N*logN)まで計算量を削減できる。(ここでNはサンプリング数)

Nが小さい素数に素因数分解出来れば出来るほど計算量が削減できる。Nが素因数分解出来ない場合が最悪で、計算量はO(N*N)。通常Nには2の累乗の数を用いる。

高速フーリエ変換を応用すると多倍長のかけ算を高速で計算出来る事が知られ、円周率などの高精度計算の世界記録更新では、高速フーリエ変換が使われている事が多い。

工学分野では広い分野で利用されている。最近では地上波ディジタル放送や無線LANなどで使用されるOFDM変復調にFFTが使われる。OFDMでは多数の小電力キャリア（ビン）のそれぞれにシンボル情報を変調して一挙に多数のシンボルを伝送する。変調時に逆FFTを使うと、この変調を一気に行うことができる。復調時にはFFTを使って広帯域に広がるビンから一気にシンボル群を抽出することができる。

リスト::数学関連