付録：デジタル社会の基盤 —— 離散フーリエ変換（DFT）と高速フーリエ変換（FFT）
これまで学んできたフーリエ変換は、連続的な時間や空間の関数 を扱うものでした。しかし、コンピューターは連続なデータをそのまま扱うことができず、トビトビの「離散的なデータ」として処理する必要があります。 この付録では、連続な波をデジタルデータとして処理するための**離散フーリエ変換（DFT）と、それを魔法のように高速化する高速フーリエ変換（FFT）**の仕組みを解説します。
連続から離散へ：離散フーリエ変換（DFT）
連続なフーリエ級数展開における係数 の積分計算を、区間を 個に分割したトビトビの足し算（シグマ）で近似してみましょう。 このとき、波の周期性を考慮すると、係数 には という** ごとの周期性**が現れます。これにより、無限まで足し合わせていたシグマの範囲を から までの有限個にまとめることができます。
こうして誕生するのが、デジタル信号処理の基礎となる**離散フーリエ変換（DFT）**の公式です。
行列で見るDFTとユニタリ行列
このトビトビの計算は、線形代数の「行列とベクトル」を使うと非常にスッキリと表現できます。 変換の要となる を と置きます。データベクトルを 、周波数成分のベクトルを とすると、DFTは単なる行列の掛け算になります。
ここで登場する変換行列 の各要素は と表されます。 この行列 と、その複素共役をとって転置した随伴行列 を掛け合わせると、美しい直交性によって単位行列 になります。
つまり、DFTの変換行列はユニタリ行列であり、情報を一切失うことなく「時間の世界」と「周波数の世界」を相互に行き来できる完全な変換であることがわかります。
計算量の壁：DFTは重すぎる
DFTを行列計算として定式化できましたが、ここで実用上の大きな壁にぶつかります。 要素数が 個のベクトルに対して の行列を掛け合わせるため、掛け算と足し算の回数は 回に比例します。つまり、計算量が になってしまうのです。
例えば、1秒間の音声を一般的なサンプリングレートである 44100Hz で取り込んだ場合、 となり、たった1秒のデータを変換するのに約20億回もの計算が必要になります。これではリアルタイムなデジタル処理は不可能です。
魔法のアルゴリズム：高速フーリエ変換（FFT）
この の呪縛を解き放つために開発されたのが、20世紀最大のアルゴリズムの一つと呼ばれる高速フーリエ変換（FFT：Fast Fourier Transform）です。 基本的なアイデアは、計算を半分ずつに分けていく分割統治法です。データ数 を2の累乗（）に制限し、足し算のインデックス を「偶数（）」と「奇数（）」に分割してみます。
ここで、 の性質を利用して式を変形します。
この性質を元のDFTの式に代入すると、次のような驚くべき形に変形できます。
大きな括弧の中を見てください。なんと、データ数が のDFTが、データ数が半分の のDFTの2つの組み合わせに分解されています！
バタフライ演算と圧倒的な高速化
半分に分割できるということは、その半分もさらに半分にでき、最終的にデータ数が 個になるまで徹底的に分割し続けることができます。 計算の過程を図に描くと、蝶が羽を開いたような交差するパターンが現れるため、これをバタフライ演算と呼びます。
この分割統治を行うことで、元々 だった計算量が まで激減します。 先ほどの の例で言えば、約20億回必要だった計算が、わずか70万回程度（約3000分の1の軽さ）で完了することになります。
このFFTの発見により、画像圧縮（JPEG）や音声圧縮（MP3）、スマートフォンの通信からMRI画像まで、ありとあらゆるデジタル信号処理が現実の速度で動くようになったのです。