応用数学 第11回 (5) 離散フーリエ変換
離散フーリエ変換
このページは教養として読んでおいてください。
フーリエ変換は「連続パラメータを用いて、三角関数を、積分の形で足し合わせる」というものでした。
これに対し、$\bmod$ $N$ の離散的なパラメータを用いて三角関数を足し合わせた
\begin{align}
F(t)&=\sum_{x \in \ZZ/N\ZZ} f(x) e^{-2\pi i(x/N)t} \\
&=\sum_{x \in \ZZ/N\ZZ} f(x) \Big\{ \cos\left(2\pi\left(\frac{x}{N}\right)t\right)
-i\sin\left(2\pi\left(\frac{x}{N}\right)t\right) \Big\} \\
\end{align}
を「 $f(x)$ の離散フーリエ変換」と呼びます。( $\ZZ/N\ZZ$ は $\bmod$ $N$ の剰余類の集合です。)
離散フーリエ変換についてもフーリエ変換と同様に反転公式
\begin{align}
f(x)&=\frac{1}{N}\sum_{t \in \ZZ/N\ZZ} F(t) e^{2\pi i(t/N)x} \\
\end{align}
が成り立ち、次のような応用があります。
離散フーリエ変換の応用例
- 信号処理では、信号を周波数成分に分解する「スペクトル解析」に用いられます。
- 静止画像の圧縮技術である jpg は離散コサイン変換を用いています。
主要な周波数成分以外をカットすることでデータ量を減らしており、
どこまでカットするか、で画質・データ量をコントロールします。
- 次数の非常に高い多項式の乗算や、公開鍵暗号で用いるような長大な整数の乗算の高速化にも応用できます。
乗算に必要な畳み込みの計算 ( Rem.6 参照 ) が、離散フーリエ変換の世界では単なる掛け算になり、
計算量のオーダーがさがる、という仕組みです。
離散フーリエ変換を詳しく扱った教科書はあまりありませんが、
計算機でデジタル処理をするときには必要な技術です。
高速フーリエ変換
$N$ が 2 べきのときには離散フーリエ変換を高速に実装できるアルゴリズムがあり、
これを「高速フーリエ変換 ( FFT ) 」と呼びます。
( 正確には「高速離散フーリエ変換」と呼ぶべきでしょうが、
「離散」は入れないのが慣習です。)
研究室によっては卒業研究のゼミで勉強することもあろうかと思います。