離散フーリエ変換

理論上はな。だが章の最後にお前自身が言った困りごとが2つある。覚えているか。

その2つだ。整理しよう。DTFT がそのままでは計算機に乗らない理由は、

• 周波数 $\omega$ が連続（$0 \le \omega < 2\pi$ の中に無限個の点がある）
• 時間 $n$ が無限に長い（和が $-\infty$ から $\infty$ まで）

時間側の問題は、実は簡単に片付く。実際に手元にあるデータは有限個、例えば $N$ 個 $x[0], x[1], \dots, x[N-1]$ だけだ。それ以外を $0$ とすれば和は $N$ 項で止まる。残るのは周波数が連続という問題だ。

それだ。発想がもう身についてきたな。時間軸でやった「とびとびに拾う」を、そっくり周波数軸でやる。

連続な $\omega$ の代わりに、$0$ から $2\pi$ までを $N$ 等分したとびとびの周波数だけを見る。

DTFT の1周期 $[0, 2\pi)$ に等間隔で $N$ 本の「物差しの目盛り」を打つイメージだ。この $\omega_k$ を式 (5.3) に代入し、和を有限の $N$ 項に切ると

これが離散フーリエ変換（Discrete Fourier Transform、DFT）だ。$N$ 個の数列 $x[n]$ から $N$ 個のスペクトル値 $X[k]$ を作る。

そうだ。$X[k]$ は「$k$ 番目の周波数ビン」と呼ばれる。$k$ が大きいほど高い周波数（ただし $k$ が $N/2$ を超えると負の周波数側になる、これは後で見る）。下のデモで、固定した信号（長さ8の矩形パルス）の DTFT 曲線の上に、$N$ 点 DFT のビンがどう乗るかを見てみろ。$N$ を動かせる。

完璧な観察だ。DFT は DTFT という連続曲線を、$\omega_k = 2\pi k/N$ という点で拾った標本値にすぎない。$N$ は「周波数の物差しを何目盛りで刻むか」を決めるだけで、信号そのものの情報量を増やしも減らしもしない。棒が乗っている曲線が真実で、棒はその上の点を拾っているだけだ。

いいまとめだ。そして、ここでまた双対が顔を出す。第3章で「時間側が周期的だと周波数側は離散」、第5章で「時間側が離散だと周波数側は周期」を見た。今度は周波数側を離散化した。すると鏡写しに、時間側が周期的とみなされる。

そこが DFT の最大の落とし穴だ。逆変換でわかるが、$X[k]$ から $x[n]$ を組み立て直すと、$n$ が $0 \sim N-1$ の外でも値が出てきて、それは周期 $N$ で同じパターンを繰り返す。DFT は心の中で「$x[n]$ は周期 $N$ で無限に続く周期信号だ」と思い込んで計算している。だから第3章の対応の鏡写しが完成する。

• 周波数を離散化（DFT のビン）した ⇒ 時間側が周期 $N$ とみなされる

第3章「時間が周期的⇔周波数が離散」を、左右ひっくり返した形だ。

順変換 (6.2) で $N$ 個の $x[n]$ から $N$ 個の $X[k]$ を作った。逆に戻す離散フーリエ逆変換（IDFT）はこうだ。

その通り。第5章の逆変換 (5.5) では $\frac{1}{2\pi}\int$ だったのが、周波数も離散になったので積分が和に変わり、$\frac{1}{N}\sum$ になった。係数 $\frac{1}{2\pi}$ が $\frac{1}{N}$ に化けたのも、周波数の刻み幅が $\frac{2\pi}{N}$ になったことの帳尻合わせだ。順変換が「全周波数のビンで和」、逆変換も「全時間で和」。どちらも有限和で、対称的にきれいだろ。

そうだ。ここに至って、信号処理はついに「紙の上の積分」を完全に離れて、配列と足し算と掛け算だけの世界に降りてきた。これが実際に走るフーリエ変換だ。

DFT (6.2) をもう一度眺める。$N$ 個の入力 $x[n]$ から $N$ 個の出力 $X[k]$ への変換だ。各 $X[k]$ は $x[0] \dots x[N-1]$ の重み付き和。これは行列とベクトルの掛け算そのものだ。

$W_N^{kn}$ を $(k, n)$ 成分とする $N \times N$ 行列を $x$ ベクトルに掛ければ $X$ ベクトルが出る、というわけだ。

その通り、回転因子と呼ぶ。行列の各行 $k$ は「周波数 $\omega_k = 2\pi k/N$ の複素正弦波」、すなわち DFT の基底ベクトル $e^{j2\pi kn/N}$ になっている。DFT とは結局「入力ベクトルを、これら $N$ 本の正弦波基底に分解する」操作だ。各基底がどんな波か、下のデモで $k$ を動かして見てみろ。上が実部 $\cos$、下が虚部 $\sin$ だ（$N=16$ 固定）。

そこが急所だ。$k=8$（$=N/2$）を境に、$k > N/2$ のビンは負の周波数を表す。$k=15$ は $k=1$ の逆回転、つまり $\omega = 2\pi \cdot 15/16$ は $\omega = -2\pi/16$ と同じこと。第4章・第5章でやった「$\omega$ と $\omega + 2\pi$（あるいは $-\omega$）は区別がつかない」がここでも生きている。だから $N$ 点 DFT の出力は、低い周波数から最高周波数（$k=N/2$）まで上がって、また負側の低い周波数へ折り返す並びになる。

DFT は実用の本命だが、素直に計算すると重い。式 (6.2) で $X[k]$ を1個求めるのに掛け算が $N$ 回。それを $k = 0 \sim N-1$ の $N$ 個ぶん。合計 $N^2$ 回の掛け算が要る。$N = 10^6$ なら $10^{12}$ 回。さすがに遅すぎる。

なる。これを劇的に速くするのが高速フーリエ変換（Fast Fourier Transform、FFT）だ。まず強調しておく。FFT は DFT とは別物ではない。式 (6.2) とまったく同じ $X[k]$ を、計算の順番を工夫して速く出すだけの計算法だ。結果は1ビットも変わらない。

肝は「分割」だ。$N$ を偶数として、和を偶数番目の $n$ と奇数番目の $n$ の2つに分ける。

偶数番を $x[2m]$、奇数番を $x[2m+1]$（$m = 0 \dots N/2-1$）と書き直す。鍵は回転因子の指数が半分の長さの回転因子になることだ。偶数番の和に現れる $W_N^{k\cdot 2m}$ を変形すると

$2$ が分母の $N$ と打ち消し合って、ちょうど長さ $N/2$ の回転因子 $W_{N/2}$ に化ける。つまり偶数番だけの和は、それ自身が長さ $N/2$ の DFTになっている。奇数番のほうは、$x[2m+1]$ に掛かる $W_N^{k(2m+1)} = W_N^{k}\, W_N^{2km} = W_N^{k}\, W_{N/2}^{km}$ から、$m$ に依らない共通因子 $W_N^{k}$ を和の外にくくり出せて、残りがまた長さ $N/2$ の DFT になる。

偶数番だけの DFT を $E[k]$、奇数番だけの DFT を $O[k]$ と名付ければ、くくり出した $W_N^{k}$ を奇数側に掛けて足し合わせるだけで

長さ $N$ の DFT が、長さ $N/2$ の DFT 2個と、たった1回の掛け算＋足し算でつながった。

そこに気づけば勝ちだ。$N/2$ の DFT を、また偶数・奇数に割って $N/4$ の DFT 2個に。それをまた割って…と再帰的に繰り返す。$N$ が $2$ のべき乗なら、最後は長さ $1$ の DFT（＝そのまま）まで割れる。

ここがコストの急所だ。半分に割る段数は $\log_2 N$ 回。各段で全 $N$ 個のデータを結合 (6.7) するのに $N$ 回程度の計算。だから全体は

$N = 10^6$ なら $N^2 = 10^{12}$ が $N \log_2 N \approx 2 \times 10^7$。約5万倍速い。リアルタイム音声処理も画像のスペクトル解析も、この差で初めて実用になった。

その通り。素朴な計算は、$k$ ごとに同じ部分和を何度も計算し直していた。FFT はそれを共有して二度手間を省く。発想は「分割統治」、賢いプログラムの王道だ。

そこが一番うまい所だ。実はただ同然で手に入る。$E[k]$ も $O[k]$ も長さ $N/2$ の DFT だから $N/2$ で周期的、つまり $E[k+N/2] = E[k]$、$O[k+N/2] = O[k]$。さらに回転因子は $W_N^{k+N/2} = W_N^{N/2} W_N^{k} = -W_N^{k}$（半周ぶん回すと符号が反転）だ。これを (6.7) に入れると

それが「バタフライ」と呼ばれる演算だ。入力 $a = E[k]$ と $b = O[k]$ から、掛け算 $W_N^{k} b$ をたった1回やって、$a + W_N^{k} b$ と $a - W_N^{k} b$ の2出力を作る。流れ図に描くと羽を広げた蝶のように線が交差するから蝶々形だ。下のデモで、その配線そのものを見てみろ。

配線の交差が「再帰木をほどいて1枚に広げた姿」だと思えばいい。再帰木（さっきのデモ）が縦の分割を、このバタフライ図が横の結合を見せている。両方あわせて FFT の全体像だ。とはいえ細かい配線を暗記する必要はない。FFT は DFT の高速計算法、答えは同じ——これだけは絶対に外すな。

これで4つのフーリエ変換が出そろった。バラバラに見えるが、**「時間と周波数が、それぞれ連続/離散・周期/非周期のどれか」**で整理すると、見事に1枚の表に収まる。

それがこの2章で何度も言ってきた双対の正体だ。法則はたった一行にまとまる。

片方の領域が「離散」なら、もう片方は必ず「周期的」。片方が「周期的」なら、もう片方は必ず「離散」。

• FS: 時間が周期的 ⇒ 周波数が離散（第3章 (3.8)）
• DTFT: 時間が離散 ⇒ 周波数が周期的（第5章 (5.4)）
• DFT: 時間も離散かつ周期、周波数も離散かつ周期（両方の合わせ技）

DFT が両方とも「離散・周期」なのは、時間も周波数も離散化した当然の帰結だ。そして両方が離散・有限だからこそ、唯一コンピュータの中で完全に閉じられる。

それがこの章までの一番の収穫だ。ここまでで「フーリエ解析」という大きな道具立ては完成した。次章からは、この道具を使って信号を操作するときに成り立つ便利な性質——線形性、時間シフト、そして信号処理の心臓部である「たたみこみ」——を見ていく。変換の式を覚える段階から、変換を武器として使う段階へ進むぞ。