FFTを1から理解する — なぜ畳み込みが掛け算になるのか

音を周波数に分解するフーリエ変換を、比喩→回転する針の直感→DFTの式→分割統治のFFTの順に前提知識ゼロから解説。畳み込みがなぜ周波数領域では掛け算1回になるのか、多項式の積の視点で腹落ちさせる。

An Algorithm for the Machine Calculation of Complex Fourier Series (Cooley & Tukey

和音を聞き分ける耳

ピアノで「ド・ミ・ソ」を同時に鳴らしたとき、空気を伝わる振動はたった1本の波です。マイクが記録するのも「各瞬間の空気圧」がずらっと並んだ1本の数値列で、そこに3つの音が溶けて混ざっています。ところが私たちの耳は、その1本の波から3つの音を聞き分けられます。

耳がやっているこの「混ざった波を、高さごとの成分にほどく」操作を数学にしたものがフーリエ変換です。そして FFT（Fast Fourier Transform／高速フーリエ変換） は、その計算を桁違いに速くするアルゴリズムです。1965年の Cooley と Tukey の論文で世界に広まり（原型は19世紀のガウスのノートにまで遡ります）、「20世紀で最も重要なアルゴリズム」の筆頭に挙げられることが多い、信号処理の心臓部です。

比喩: スムージーから材料を言い当てる

信号の見方には2つの「言葉」があります。

• 時間領域: 完成品のスムージー。「各瞬間の値」の列。マイクやセンサーが直接くれるのはこちら
• 周波数領域: レシピ。「バナナ2本、イチゴ5個、牛乳200ml」— つまり「どの高さの波が、どれだけ、どんなタイミングのずれで入っているか」の一覧

フーリエ変換は、スムージーを一口飲んでレシピを完全に言い当てる装置です。逆変換はレシピどおりに作り直す装置。行き来しても情報は一切失われません。同じものを2つの言葉で書いているだけです。

なぜわざわざ翻訳するのか。やりたい操作によって、楽な言葉が違うからです。「低い音だけ残して高い音を消したい」は、時間領域の波形をどういじればいいか見当もつきませんが、レシピ側なら「高音の行を消す」だけ。この記事の後半で見る畳み込みも、時間領域では大仕事なのに、周波数領域ではただの掛け算になります。

直感: 波を「回転する針」に巻きつける

では「ある高さの波がどれだけ入っているか」をどう測るのか。ここがフーリエ変換のいちばん美しいところです。

時計の針を思い浮かべてください。ただし速さは自由に選べます。周波数 $f$ の成分を調べたいときは、信号を1秒あたり $f$ 回転の針に巻きつけて、円板の上にグラフを描きます。信号の値が大きい瞬間は針の先に重いおもりを、小さい瞬間は軽いおもりを置いていくイメージです。

• 信号の中に $f$ Hz の波が入っていると、おもりが円板の同じ側にばかり積もり、円板の重心が中心からずれます
• 入っていなければ、おもりは円板中にまんべんなく散らばり、重心はほぼ中心に残ります

この重心のずれの大きさが「その周波数の含有量」、ずれの方向が「波のタイミングのずれ（位相）」です。回転を1つの数で表すために複素数 $e^{i\theta}$（$= \cos\theta + i\sin\theta$、半径1の円周上を角度 $\theta$ だけ進んだ点）を使います。複素数が出てくるのは難しくするためではなく、「回転」を掛け算1回で書ける便利な記法だからです。

仕組み: 離散フーリエ変換（DFT）

コンピュータが扱うのは連続の波ではなく、一定間隔で測った $N$ 個のサンプル $x_0, x_1, \dots, x_{N-1}$ です。これをほどくのが離散フーリエ変換（DFT）で、定義は次の1本です。

言い換えると「$N$ 個のサンプルの間にちょうど $k$ 回転する針に信号を巻きつけ、重心を求めよ（の $N$ 倍）」です。$x_n$ は時刻 $n$ の信号の値、$e^{-2\pi i\,kn/N}$ は時刻 $n$ における針の向き、$\sum$ はおもりを全部載せて重心を出す操作にあたります。$k$ を $0$ から $N-1$ まで変えれば、遅い波から速い波まで全成分が出そろいます。

出てくる $X_k$ は複素数で、絶対値がその周波数の強さ、角度が位相です。音声解析アプリが出すスペクトル表示は、この $|X_k|$ を並べたものです。

素朴に計算すると N² 回

式(1)をそのまま計算すると、1つの $X_k$ に掛け算と足し算が $N$ 回、それが $k$ の数だけあるので全体で約 $N^2$ 回の演算になります。CD品質の音声はわずか1秒で44100サンプル。$44100^2$ はおよそ19億回です。1秒の音を分析するのに19億回では、リアルタイム処理も、毎秒何十枚も届く画像への適用も話になりません。

$N^2$ と $N \log N$ がどれほど違うかは、口で言うより動かすのが早いです。

ここからが本題です。この $N^2$ を $N \log N$ に潰すからくりと、「畳み込みが掛け算になる」というこの記事の副題の種明かしに入ります。