高速 Fourier 変換（FFT）

信号処理論入門　第6章 §6.3　★ バタフライとIFFTの流用

DFT を定義通り計算すると、各 $k$ について $N$ 回の積和を $N$ 個の $k$ に対して行うので$O(N^2)$ の演算量になる。FFTは、回転因子 $W_N$ の対称性・周期性を使ってこれを $O(N\log N)$ に落とすアルゴリズムである（$N$ が2の冪のとき最も簡明）。

基本アイデアは分割統治である。長さ $N$ の DFT を、偶数番目の標本と奇数番目の標本から成る長さ $N/2$ の DFT 二つに分け（時間間引き）、それらを回転因子で結合する。

$$X[k]=\underbrace{E[k]}_{\text{偶成分の }N/2\text{-DFT}}+W_N^{k}\underbrace{O[k]}_{\text{奇成分の }N/2\text{-DFT}},\quad X[k+N/2]=E[k]-W_N^{k}O[k].$$

この一組の加減算をバタフライ演算と呼ぶ。同じ分割を再帰的に $\log_2 N$ 段くり返すと全体で $O(N\log N)$ になる。たとえば $N=1024$ なら $N^2\approx10^6$ に対し$N\log_2 N\approx10^4$ で、約100倍速い。

時間間引きでは、入力を偶奇に振り分けることを繰り返す都合上、入力（または出力）の並びがビットリバース順（添字の2進表現を逆順にした並び）になる。実装ではこの並べ替えを最初か最後に一度行う。

FFT の重要な応用が高速畳み込みである。長い畳み込み $y=x* h$ を直接計算すると$O(N^2)$ だが、畳み込み定理より $Y[k]=X[k]H[k]$ だから、「FFT →周波数領域で要素ごとの積→逆FFT」とすれば $O(N\log N)$ で済む。ただし DFT は巡回畳み込みを計算するので、線形畳み込みを得るには$x,h$ を十分に零詰めして周期化の巻き込みを防ぐ必要がある（§5.3参照）。