離散 Fourier 変換（DFT）

信号処理論入門　第5章 §5.3　★★ 行列表現・数値計算・実列からの復元

有限長 $N$ の離散信号 $x[0],\dots,x[N-1]$ に対し、DTFT の周波数 $\Omega$ を$N$ 等分点 $\Omega_k=2\pi k/N$ で標本化したものが離散 Fourier 変換である。

DFT は「信号ベクトル $\bm x\in\mathbb{C}^N$ を、$N$ 本の離散複素正弦波$\bm w_k=(\mathrm{e}^{\mathrm{j}2\pi kn/N})_n$ という正規直交基底へ展開する座標変換」であり、第1章の固有値分解・ユニタリ変換の枠組みそのものである（$\{\bm w_k\}$ は巡回シフト行列の固有ベクトルにあたる）。行列で書けば $\bm X=\bm F\bm x$、$\bm F$ は成分 $W_N^{kn}$ のDFT 行列で、$\bm F^{-1}=\tfrac1N\bm F^{*}$（定数倍を除いてユニタリ）となる。

DFT は暗黙に信号を周期 $N$ で周期化して扱う（§5.1の下行）。このため DFT 領域での積は巡回畳み込みに対応する（第1章§1.5）。通常の（線形）畳み込みを DFT で計算したいときは、零詰め（次章）で周期化の巻き込みを避ける必要がある。