高速フーリエ変換（FFT）の原理

DFTという「重い行列積」をどう軽くするか

離散フーリエ変換（DFT）は、長さ n の数列 x[0..n-1] を、同じ長さの周波数成分 X[0..n-1] に写す変換です。定義はこうです。

X[k] = Σ_{j=0}^{n-1} x[j] · W_n^{jk}     （k = 0..n-1）
W_n = exp(-2πi / n)     ← n 乗根、これを回転因子と呼ぶ

W_n（twiddle factor、回転因子）は複素平面の単位円を n 等分する点で、W_n^{jk} は角度 -2π·jk/n の回転を表します。定義どおりに計算すると、各 X[k] が n 項の和、それを n 個求めるので乗算回数は n^2。これは n×n の行列 (W_n^{jk}) とベクトル x の積そのもので、素朴には O(n^2) です。n が数万を超える信号や多項式では、この二乗が致命的になります。

FFTはこの行列積を、回転因子が持つ周期性と対称性を突いて O(n log n) に落とすアルゴリズムです。値が変わるわけではなく、同じ X[k] を冗長な計算を畳み込んで求め直す――その意味で完全に正確な変換です。

Cooley-Tukey分割: 偶奇に割ると再帰になる

最も基本的な基数2のCooley-Tukey法は、n が2の冪のとき、入力を偶数インデックスと奇数インデックスに二分します。和を偶奇で分けて書き直すのが出発点です。

X[k] = Σ_{j even} x[j] W_n^{jk} + Σ_{j odd} x[j] W_n^{jk}
     = Σ_{m=0}^{n/2-1} x[2m]   W_n^{2mk}
     + Σ_{m=0}^{n/2-1} x[2m+1] W_n^{(2m+1)k}

ここで鍵になる恒等式が W_n^2 = W_{n/2} です。exp(-2πi·2/n) = exp(-2πi/(n/2)) だから、W_n^{2mk} = W_{n/2}^{mk}。これを使うと、偶数項の和はサイズ n/2 のDFT（これを E[k] とする）、奇数項の和は同じく n/2 のDFT（O[k]）に W_n^k を掛けたものに変形できます。

X[k] = E[k] + W_n^k · O[k]
E[k] = 長さ n/2 DFT（偶数位置の入力）
O[k] = 長さ n/2 DFT（奇数位置の入力）

つまり長さ n のDFTが、長さ n/2 のDFT2つに帰着しました。これは典型的な分割統治で、漸化式は T(n) = 2·T(n/2) + O(n)。結合の O(n) は回転因子の掛け算と加算ぶんです。マスター定理のケース2にあたり、計算量は O(n log n)。この対数倍の削減が、信号処理から大整数乗算までを一変させました。

バタフライ演算: 対称性で計算を半分にする

X[k] = E[k] + W_n^k·O[k] だけでは k = 0..n/2-1 しか埋まりません。残る上半分 X[k+n/2] を、回転因子の半周期対称性で導きます。W_n^{n/2} = exp(-πi) = -1 なので次が成り立ちます。

W_n^{k+n/2} = W_n^k · W_n^{n/2} = -W_n^k

E[k]・O[k] の周期が n/2 であることと合わせると、下半分と上半分が同じ2つの値から作れます。

X[k]       = E[k] + W_n^k · O[k]
X[k+n/2]   = E[k] - W_n^k · O[k]      （k = 0..n/2-1）

この一対の更新がバタフライ演算です。t = W_n^k·O[k] を1回だけ計算し、E[k] との和と差で2つの出力を同時に得ます。データフロー図が蝶の羽のように交差するのが名の由来です。1回のバタフライは複素乗算1回・複素加減算2回で、1段に n/2 個、段数は log_2 n 段。掛け算の総数が (n/2)·log_2 n に収まることが、O(n log n) の正体です。

逆変換と数値的な注意点

逆DFT（IDFT）は回転因子の符号を反転し、最後に 1/n で割るだけで、同じバタフライ構造をそのまま使えます。

実装では sin・cos を再計算せず、回転因子テーブルを事前計算して参照します。複素演算はIEEE 754の浮動小数点で行うため丸め誤差が乗りますが、FFTの誤差成長は段数に対しておおむね O(log n) 程度に抑えられ、定義どおりの O(n) 蓄積よりむしろ良いのが利点です。整数の厳密計算が要る場面では、浮動小数点の代わりに有限体上で同型のアルゴリズムを走らせる数論変換（NTT）を使い、丸め誤差をゼロにします。

なぜ効くのか: 畳み込みという主戦場

FFTが広く使われる最大の理由は、巡回畳み込みを高速化することにあります。畳み込み定理は「時間領域の畳み込みは周波数領域の要素ごとの積に等しい」と述べます。

a ⊛ b = IDFT( DFT(a) ⊙ DFT(b) )      ⊙ は要素ごとの積

素朴な畳み込みは O(n^2) ですが、両者をFFTで周波数領域に移し（O(n log n)）、要素積をとり（O(n)）、逆変換で戻す（O(n log n)）と、全体が O(n log n) に下がります。これが効く代表例を挙げます。

• 多項式乗算: 多項式は係数列。係数の畳み込みが積に対応するので、2つの多項式を点値表現（DFT）に移して点ごとに掛け、補間（IDFT）で係数へ戻すと O(n log n) で積が求まります。
• 大整数乗算: 桁列を係数とみなせば多項式乗算に帰着。Schönhage–Strassen 法はこの発想を整数環 Z/(2^k+1)Z 上のFFTで丸め誤差なく実現したもので、巨大数ライブラリの根幹です（素数体上のNTTを使う実装も広く用いられます）。
• 信号処理: FIRフィルタ適用、相関・自己相関、スペクトル解析、画像の周波数フィルタリングはすべて畳み込みかDFTそのものです。

文字列照合でも、ワイルドカード照合やパターンの相互相関をFFTで O(n log n) に落とす技法があり、文字列照合アルゴリズムで扱うRabin-Karp系の畳み込み解釈と地続きです。

まとめ: 周期性が二乗を対数倍に変える

FFTの本質は、DFTという O(n^2) の行列積を、回転因子 W_n が持つ周期性 W_n^2 = W_{n/2} と対称性 W_n^{k+n/2} = -W_n^k の2本で畳み込み、分割統治の O(n log n) に圧縮することです。核となるバタフライ演算は、2つの値を1回の乗算と加減算で同時に更新する最小単位。そして畳み込み定理を通じて、多項式乗算・大整数乗算・信号処理という広大な応用へつながります。「二乗を対数倍に変える対称性」を見抜く視点が、FFTを理解し使いこなす鍵です。