読み方：こうそくフーリエへんかん

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

概要

高速フーリエ変換とは、時系列のデジタル信号を周波数成分の集合として表す離散フーリエ変換（DFT）を、コンピュータで高速に計算するアルゴリズム。音声や画像、映像の処理から、通信や科学計算まで様々な分野で応用されている。

「フーリエ変換」（Fourier transform）とは、複雑な波形を複数の正弦波・余弦波の組み合わせとして表す数学的手法で、ある信号にどの周波数成分がどの程度含まれているかを明らかにする。音声信号の音高・音量分析や、画像処理における周期成分の抽出・圧縮などに応用される。離散フーリエ変換（DCT：Discrete Fourier Transform）はこれを整数など離散的な数値の系列に対して行う。

離散フーリエ変換を素朴に計算すると、標本数をNとした場合の計算量は O（N²）となり、データ量が増えるほど処理コストが急激に増大する。高速フーリエ変換はこの問題を、入力データを小さなグループに分割し計算の重複部分を再利用するというテクニックにより緩和し、計算量を O（N log N）にまで削減する。例えば、N=1024のとき、離散フーリエ変換では約100万回の演算が必要だが、高速フーリエ変換では約1万回程度で済む。Nが2の累乗である場合に計算効率が最も高くなる性質がある。

高速フーリエ変換は特定の一手法を指すのではなく、用途やデータ長に応じた様々なアルゴリズムが提案されている。中でも最も知られる手法は、1965年にジェームズ・クーリー（James W. Cooley）とジョン・テューキー（John W. Tukey）が発表したクーリー・テューキー法（Cooley-Tukey algorithm）である。入力を偶数・奇数インデックスに再帰的に分割しながら計算する方式で、現在の信号処理の基礎を確立した。

周波数領域から元の時系列信号に復元する逆変換は「逆高速フーリエ変換」（IFFT：Inverse Fast Fourier Transform）と呼ばれ、高速フーリエ変換とセットで用いられることが多い。例えば、デジタルフィルタ設計や音響エフェクト処理では、信号をFFTで周波数領域に変換して操作した後、IFFTで時系列に戻す手順が定石となっている。また、畳み込み演算や相関演算の高速化にも利用され、音声認識、無線通信、レーダー信号処理、JPEGなどの画像圧縮法、MPEGなどの動画圧縮法にも組み込まれている。

(2026.6.30更新)