FFT（高速フーリエ変換）をやさしく解説

FFT（fast Fourier transform、高速フーリエ変換）は、離散フーリエ変換（DFT）を高速に計算する方法です。等間隔に並んだサンプルから出発すると、DFTはそのサンプルに各離散周波数パターンがどれだけ含まれているかを教えてくれます。

重要なのは、FFTは結果そのものを変えないという点です。直接公式で計算した場合と同じDFTの値を返しますが、重複する計算を大幅に減らして求めます。

FFTを一言でいうと

FFTは、DFTで定義される同じ周波数領域の値を、より速く計算するアルゴリズムです。

DFTが測っているもの

サンプル $x_0, x_1, \dots, x_{N-1}$ があるとします。DFTは、次で定義される $X_0, X_1, \dots, X_{N-1}$ を出力します。

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

各 $X_k$ は、データがある離散周波数パターンにどれだけ強く一致しているかを表します。

サンプルがサンプリング周波数 $f_s$ で等間隔に取られているなら、隣り合う周波数ビンの間隔は

$$\frac{f_s}{N}$$

になります。

この条件は重要です。サンプリング周波数が分からなくてもDFTのビン自体は得られますが、それをヘルツのような物理的な周波数としてラベル付けすることはできません。

なぜFFTは速いのか

FFTは、DFTを効率よく計算するためのアルゴリズム群です。中心となる工夫は、複素指数因子の構造を再利用し、ほとんど同じ和を最初から何度も計算しないことです。

最もイメージしやすいのは基数2（radix-2）FFTです。これは $N$ が $2$ のべき乗のときに特に自然に働き、長さ $N$ の変換を、まず長さ $N/2$ の変換2つに分けてから結果を合成します。

直接DFTでは、計算量はおおよそ $N^2$ のオーダーで増えます。よく使われるFFTでは、それがだいたい $N \log N$ まで下がります。

この差が、実際の場面でFFTが重要になる理由です。入力が小さければどちらの方法でも問題ないように見えるかもしれません。ですが入力が大きくなると、FFTは圧倒的に高速です。

FFTはどうやって計算を分けるのか

FFTは、すべてのサンプルをすべての周波数パターンと直接比較する代わりに、問題をより小さな変換に分解し、その後で位相因子を使って再び組み合わせます。

標準的な分け方は次の通りです。

1. 偶数番目のサンプルを1つの列にまとめる。
2. 奇数番目のサンプルを別の列にまとめる。
3. それぞれの列に対して小さな変換を計算する。
4. 2つの結果を合成する。

これは周波数解析における分割統治法です。

4点FFTの例

4点の信号

$$x = [1, 0, 1, 0]$$

を考えます。

このパターンは $1$ と $0$ が交互に現れるので、完全に平坦な結果ではなく、何らかの周波数構造が現れると期待できます。

偶数番目と奇数番目に分けると、

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

となります。

偶数側の2点DFTは

$$E = [2, 0]$$

で、奇数側の2点DFTは

$$O = [0, 0]$$

です。

4点FFTでは、合成の段階は

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

となります。ここで

$$W_4 = e^{-i 2 \pi / 4}$$

です。

$O_k = 0$ なので、合成は特に簡単です。

$$X = [2, 0, 2, 0]$$

では、この結果を解釈してみましょう。

$X_0 = 2$ はゼロ周波数成分なので、サンプルの平均値がゼロでないことを反映しています。$X_2$ の非ゼロ値は、この4点の場合における交互パターンの成分を表しています。先に平均を引いておけば、$X_0$ の項は消え、交互成分がよりはっきり見えるようになります。

この例は小さいですが、考え方はそのまま拡張できます。つまり、毎回和全体を作り直すのではなく、小さな変換を解いてから合成するのです。

FFTでよくある間違い

FFTとDFTを別の結果だと思う

そうではありません。FFTはDFTをより速く計算する方法です。

ビンを早い段階で物理的な周波数とみなしてしまう

ビンの位置が物理的な周波数になるのは、サンプル間隔が分かっているときだけです。サンプリング周波数が $f_s$ なら、等間隔サンプルに対するビン間隔は $f_s/N$ です。

ゼロ埋めで新しい情報が増えると思う

ゼロ埋めをすると、もとの変換をより細かくサンプリングするため、スペクトルが滑らかに見えることがあります。しかし、新しい観測データが増えるわけではありません。

信号の前処理を無視する

平均値の除去、窓関数、適切なサンプリングの選び方はとても重要です。これらを無視すると、FFTの出力は与えられたサンプルに対して数学的には正しくても、解釈としては誤解を招くことがあります。

FFTはどこで使われるのか

FFTは、サンプルデータから周波数領域の情報を高速に得たいあらゆる場面で使われます。代表例としては、スペクトル解析、フィルタリング、画像処理、振動解析、微分方程式の数値計算、高速な多項式計算や畳み込み計算などがあります。

理由は実用的です。多くの操作は、サンプル領域から周波数領域へ移ることで、より簡単になったり高速になったりします。

似たケースを試してみる

1周期分の正弦波を、等間隔な $8$ 個のサンプルで取り、電卓やスクリプトでDFTを計算してみてください。次に定数オフセットを加えて、新しい出力と比べます。$X_0$ が強くなる様子を見ると、FFTが何を分離しているのかが簡単に分かります。