1. DFT は「N 本の内積」 — 基底との照合作業
N 点の信号 x[n] に対して、DFT は周波数ビン k ごとに次の計算をします。「1周期に k 回転する基底波」を信号に点ごとに掛けて、全部足す — つまり内積です。内積は「形がどれだけ似ているか」の点数。信号と基底の山が揃えば積は正に偏って総和が大きくなり、無関係なら正負が打ち消し合ってゼロに近づきます。
下のデモは N = 16。ビン k を動かして、どの基底のときに総和 |X[k]| が跳ね上がるかを確かめてください。
DFT の内積計算 — 信号 × 基底の総和が X[k] になる
①信号（水色の点）に基底の cos（オレンジ）と sin（紫）を重ね、②点ごとの積を棒で表示、n = 0 から順に加算していきます。③加算が終わるとそのビンの |X[k]| がスペクトルに積まれます。k=8（N/2）を軸に鏡像になることにも注目。
X[k] = Σn=0N−1 x[n]·e−i2πkn/N (k = 0, 1, …, N−1)
e−i2πkn/N = cos(2πkn/N) − i·sin(2πkn/N)。ビン1本に掛け算 N 回 × ビン N 本 ＝ 全体で N² 回
POINT — DFT は積分の「点値バージョン」
前章の ∫f(t)e−iωtdt の連続の t を、サンプル番号 n に置き換えただけ。「巻き付けて重心」の巻き付け先が、1周期を N 等分した円周上の点に限定されたのが DFT である。
2. 回転因子 WN — 時計の針は N 種類しかない
DFT の中身 e−i2πkn/N は、WN = e−i2π/N の nk 乗と書けます。WN は「円周を N 等分する1目盛り」。つまり nk がいくつ大きくても、針の向きは nk mod N で決まる N 種類だけです。
N = 8 で確かめましょう。n と k を動かすと、針が nk 目盛りぶん回って止まります。右の 8×8 の表は DFT の計算 64 マス全部の針の向き — 同じ向きのマスがいくつも見つかるはずです。
回転因子 W₈ⁿᵏ — 64 マスの掛け算、中身は 8 種類
左＝複素平面の単位円。8つの点が W₈ の 0〜7 乗で、オレンジの針が nk 目盛りぶん回転して W₈nk mod 8 に到達します。右＝DFT 行列（行 = k, 列 = n）の全マス。緑にハイライトされた「同じ向きのマス」は同じ値 — この重複が FFT の伏線です。
WN = e−i2π/N, WNm+N = WNm, WNm+N/2 = −WNm
周期性と対称性。N=8 なら値は8種類、しかも半周ずらすと符号が反転するだけ
注意 — 意味のあるビンは N/2 まで
実数の信号では X[N−k] は X[k] の複素共役になり、大きさは鏡像（k=8 を軸に対称）。独立な情報は k = 0 〜 N/2 だけで、これはサンプリング定理のナイキスト周波数に対応する。また隣のビンとの間隔（周波数分解能）は Δf = fs/N。細かく見たければ長く録るしかない。
3. FFT — 同じ掛け算を二度しない
N² 回の掛け算のうち、回転因子の重複ぶんは使い回せるはず — それを体系的にやるのが FFT（高速フーリエ変換）です。信号を偶数番目と奇数番目に分けると、N 点の DFT は「N/2 点の DFT 2つ ＋ 合成 N 回」に化けます。これを再帰的に繰り返すと log₂N 段のバタフライ演算だけが残ります。
X[k] = E[k] + WNk·O[k], X[k+N/2] = E[k] − WNk·O[k]
E = 偶数番サンプルの DFT、O = 奇数番サンプルの DFT。1回の掛け算 WNk·O[k] で出力が2つ求まる — この十字の流れが「バタフライ」
下のデモで N = 8 の FFT をステージごとに進めてください。右のグラフは N を大きくしたときの計算量の差です。
FFT バタフライ — 3ステージで8点DFTが完成する
左＝バタフライ図。入力はビット反転順（x[0], x[4], x[2], …）に並べ、ステージ1で「2点DFT×4」、ステージ2で「4点DFT×2」、ステージ3で完成。オレンジ＝計算中、緑＝計算済み。右＝N²（赤）と N·log₂N（緑）の差。両軸対数なので、まっすぐ見えても差は指数的に開いています。
N = 1,000,000 のとき：N² = 1012 回 vs N·log2N ≈ 2×107 回 — 約 50,000 倍
1回の演算を1ナノ秒とすると「約17分」対「0.02秒」。リアルタイム音声処理は FFT なしには成立しない
一歩先へ — 「20世紀で最も重要なアルゴリズム」
FFT は 1965 年に Cooley と Tukey が発表して広まったが、実は 1805 年にガウスが天体軌道の計算で同じ方法を使っていた。スペクトログラム、MP3・AAC の圧縮、ノイズ除去、OFDM 通信（Wi-Fi・5G）、さらには大きな数の掛け算まで — 現代の信号処理はほぼすべて FFT の上に載っている。
4. まとめ — 内積を、使い回して速く
- DFT：N 点の信号と「k 回転する基底」との内積を N 本計算する。素朴にやると N² 回の掛け算。
- 回転因子 WN：DFT の掛け算の中身は N 種類しかなく、周期性・対称性で大量に重複している。
- FFT：偶奇分解を再帰して重複を使い回す。計算量は N² → N·log₂N、N=100万で約5万倍速い。
- 実信号のスペクトル：k = N/2（ナイキスト）を軸に鏡像。分解能は Δf = fs/N。