高速フーリエ変換（FFT）とは

高速フーリエ変換（FFT）は、音などの波形に、どの高さ（周波数）の成分がどれだけ含まれるかを素早く求める計算方法です。和音を聞いて、どの音がどの強さで鳴っているかを聞き分ける作業を、コンピュータで行うイメージです。

フーリエ変換とDFT

波形は、さまざまな周波数のなめらかな波（正弦波）の足し合わせとして表せます。波形から各周波数の成分の大きさを求める処理がフーリエ変換です。A-D変換で得た有限個の標本に対して行うものを、離散フーリエ変換（DFT）と呼びます。横軸を周波数、縦軸を成分の強さとしたグラフがスペクトルです。

なぜ「高速」なのか

N個の標本のDFTをそのまま計算すると、約N × N回の掛け算が必要です。代表的なFFTは、大きなDFTを半分の大きさのDFTに分ける操作を繰り返し、同じ計算の重複を省きます。これにより、計算量はN × log2 Nに比例する程度まで減ります。N = 1,024なら、N × Nの1,048,576に対し、N × log2 Nは10,240で、約100分の1です。結果は近似ではなく、DFTと同じです。1965年にクーリーとテューキーが発表して広まりました。同じ考え方は、19世紀初めのガウスの計算にも見られることが、のちに指摘されています。

音声処理での使い方

音声は時間とともに性質が変わるため、20〜30ミリ秒程度の短い区間（フレーム）に区切り、少しずつずらしながら区間ごとにFFTをかけます。これを短時間フーリエ変換といい、結果を時間の順に並べた図をスペクトログラムと呼びます。MFCCやメルスペクトログラムも、このFFTの結果から求めます。周波数の細かさは標本化周波数 ÷ Nで決まり、16kHzの音声に256点のFFTを使うと、16,000 ÷ 256 = 62.5Hz刻みになります。

覚え方

「FFTは、DFTと同じ答えを速く出す計算の工夫」と覚えます。