Reference:

1. 金谷 健一. これなら分かる応用数学教室―最小二乗法からウェーブレットまで― . 共立出版, 2003.↩

Plot

  • N個の離散点に対してフーリエ変換を適応させた離散フーリエ変換について学ぶ
  • パワースペクトルと自己相関係数を導入して、（連続）フーリエ変換と同じような世界を構築できることを示す。
  • 離散コサイン変換を説明する。(今回はここまで）
  • 離散フーリエ変換の世界におけるサンプリング定理を導く
  • 高速フーリエ変換を目指す。

この章を読むのに必要な復習

3.3 フーリエ級数展開

周期Tの関数f(t)をフーリエ級数展開すると、 $$ f(t) = \sum_{k = -\infty}^{\infty}C_k e^{ikwt} $$ $$ C_k = \frac{1}{T} \int_{-\frac{T}{2}}^{\frac{T}{2}} f(t) e^{-ikwt} dt $$ となる。ただし、 $$ \omega = \frac{2 \pi}{T} $$ とおいた。

離散フーリエ変換

円周に沿って値が定義された関数$f(\theta)\,0\leq\theta\leq2\pi$を考える

$$ \begin{eqnarray} F_k &=& \frac{1}{N} \sum_{l=0}^{N-1} f_l e^{\frac{-i2\pi kl}{N}} \end{eqnarray} $$

で離散フーリエ変換を定義するとき、逆離散フーリエ変換を求める。今、 $$ \sum_{k=0}^{N-1} F_k e^{i2\pi kl}{N} $$ を考えると、

$$ \begin{eqnarray} \sum_{k=0}^{N-1} F_k e^\frac{i2\pi kl}{N} &=& \sum_{k=0}^{N-1} \left( \frac{1}{N} \sum_{m=0}^{N-1} f_m e^{\frac{-2\pi km}{N}} \right) e^\frac{i2\pi kl}{N} \\ &=& \sum_{k=0}^{N-1} \left( \frac{1}{N} \sum_{m=0}^{N-1} f_m e^{\frac{2\pi k(l-m)}{N}} \right) \\ &=& \sum_{m=0}^{N-1} \left( \frac{1}{N} f_m \sum_{k=0}^{N-1} e^{\frac{2\pi k(l-m)}{N}} \right) \\ \end{eqnarray} $$

今$\sum_{k=0}^{N-1} e^{\frac{2\pi k(l-m)}{N}} $は等比級数の総和であり、これを解くと、 $$ \sum_{k=0}^{N-1} e^{\frac{2\pi k(l-m)}{N}} = \begin{cases} N (l=m) \\ 0 (Other) \end{cases} $$ となる。ゆえに $$ \sum_{m=0}^{N-1} \left( \frac{1}{N} f_m \sum_{k=0}^{N-1} e^{\frac{2\pi k(l-m)}{N}} \right) = f_l $$ となるから、逆離散フーリエ変換は $$ f_l = \sum_{k=0}^{N-1} F_k e^{i2\pi kl}{N} $$ (答えありきの変形で済まない)

たたみこみ和定理

以下で定義されるものを（循環）たたみこみ和という。これは3章でやった畳み込み積分の離散版に対応する $$ f_l * g_l = \frac{1}{N} \sum_{m=0}^{N-1} f_m g_{l-m} $$ そのために、畳み込み積分の性質と同じような性質を有する。つまり、線型法則、結合法則、交換法則が成立する。 $$ \begin{eqnarray} f_l * g_l &=& g_l * f_l \\ f_l * (ag_l + bh_l) &=& a f_l * g_l + b f_l * h_l \\ (f_l * g_l) * h_l &=& f_l * (g_l * h_l) \end{eqnarray} $$

たたみこみ和$f_l * g_l$を離散フーリエ変換をすると、どうなるか見てみる。 $$ \begin{eqnarray} \frac{1}{N} \sum_{l=0}^{N-1} f_l * g_l e^{\frac{-i2\pi kl}{N}} &=& \frac{1}{N} \sum_{l=0}^{N-1} \left( \frac{1}{N} \sum_{m=0}^{N-1} f_m g_{l-m} \right) e^{\frac{-i2\pi kl}{N}} \\ &=& \frac{1}{N} \sum_{m=0}^{N-1} f_m \left( \frac{1}{N} \sum_{l=0}^{N-1} g_{l-m} e^{\frac{-i2\pi k(l-m)}{N}} \right) e^{\frac{-i2\pi km}{N}} (\because 外と内のΣを入れ替えた) \\ &=& \left( \frac{1}{N} \sum_{m=0}^{N-1} f_m e^{\frac{-i2\pi km}{N}} \right) \left( \frac{1}{N} \sum_{l=0}^{N-1} g_{l-m} e^{\frac{-i2\pi k(l-m)}{N}} \right) \\ &=& F_k G_k \end{eqnarray} $$ 故に、たたみこみ和の離散フーリエ変換はそれらのデータ列の離散フーリエ変換の積になることがわかった。

パワースペクトル

パーセバルの式と呼ばれる次の式が成り立つ $$ \frac{1}{N} \sum_{l=0}^{N-1} f_l \overline{g_l} = \sum_{k=0}^{N-1} F_k \overline{G_k} \\ \frac{1}{N} \sum_{l=0}^{N-1} |f_l|^2 = \sum_{k=0}^{N-1} |F_k|^2 $$

証明

第一式が示せれば第二式が成立するのは明らか（$\because g_l$に$f_l$を代入)。よって第一式だけを示せば良い

$$ \begin{eqnarray} \frac{1}{N} \sum_{l=0}^{N-1} f_l \overline{g_l} &=& \frac{1}{N} \sum_{l=0}^{N-1} f_l \sum_{k=0}^{N-1} \overline{G_k} e^{\frac{-i2\pi kl}{N}} \\ &=& \frac{1}{N} \sum_{l=0}^{N-1} f_l \sum_{k=0}^{N-1} \overline{G_k} e^{\frac{-i2\pi kl}{N}} \\ &=& \sum_{k=0}^{N-1} \left( \frac{1}{N} \sum_{l=0}^{N-1} f_l e^{\frac{-i2\pi kl}{N}} \right) \overline{G_k} \\ &=& \sum_{k=0}^{N-1} F_k \overline{G_k} \end{eqnarray} $$

以上によりパーセバルの式が示された。

今

$$ \frac{1}{N} \sum_{l=0}^{N-1} |f_l|^2 (= \sum_{k=0}^{N-1} |F_k|^2) $$

が平均エネルギーを表しているとすると,右辺はそれを周波数ごとにまとめたものだと解釈できる。パワースペクトルを $$ P_k = |F_k|^2 $$ と定義すると、 $$ \begin{eqnarray} \frac{1}{N} \sum_{l=0}^{N-1} |f_l|^2 (&=& \sum_{k=0}^{N-1} |F_k|^2) \\ &=& \sum_{k=0}^{N-1} P_k \end{eqnarray} $$ となる。

自己相関係数

$$ R_n = \frac{1}{N} \sum_{l=0}^{N-1} f_l \overline{f_{l-n}} $$

これで定義された数列を$\{f_l\}$の自己相関係数という。$\{R_n\}$は長さNの数列となる。また、$R_0$は上の段落で示した平均エネルギーと同じ式になる。

こちらも3章でおこなった（連続）フーリエ変換における自己相関係数と同じような性質を持つことを確かめる。いくつか性質はあるが、特に

「自己相関係数をフーリエ変換するとパワースペクトルになる」

という性質がこの自己相関係数とパワースペクトルに対しても成立するか見てみることにする。自己相関係数を離散フーリエ変換して

$$ \begin{eqnarray} 　　\frac{1}{N} \sum_{n=0}^{N-1} R_n e^{\frac{-i2\pi kn}{N}} &=& \frac{1}{N} \sum_{n=0}^{N-1} \left( \frac{1}{N} \sum_{l=0}^{N-1} f_l \overline{f_{l-n}} \right) e^{\frac{-i2\pi kn}{N}} \\ &=& \frac{1}{N} \sum_{l=0}^{N-1} f_l \left( \frac{1}{N} \sum_{n=0}^{N-1} \overline{f_{l-n}} e^{\frac{-i2\pi kn}{N}} \right) (\because \sum を入れ替えた) \\ &=& \frac{1}{N} \sum_{l=0}^{N-1} f_l \left( \frac{1}{N} \sum_{n=0}^{N-1} \overline{f_{l-n}e^{\frac{i2\pi kn}{N}} } \right) \\ &=& \frac{1}{N} \sum_{l=0}^{N-1} f_l \left( \frac{1}{N} \sum_{n=0}^{N-1} \overline{f_{l-n}e^{\frac{i2\pi k(-(l-n))}{N}}e^{\frac{i2\pi kl}{N}} } \right) \\ &=& \frac{1}{N} \sum_{l=0}^{N-1} f_l \left( \frac{1}{N} \sum_{n=0}^{N-1} \overline{f_{l-n}e^{\frac{i2\pi k(-(l-n))}{N}} } \right)e^{\frac{-i2\pi kl}{N}} \\ &=& \left( \frac{1}{N} \sum_{l=0}^{N-1} f_l e^{\frac{-i2\pi kl}{N}} \right) \left( \frac{1}{N} \sum_{n=0}^{N-1} \overline{f_{l-n}e^{\frac{i2\pi k(-(l-n))}{N}} } \right) \\ &=& F_k \overline{F_k} (\because ()内はf_lのフーリエ変換になっている) \\ &=& |F_k|^2 \\ &=& P_k \end{eqnarray} $$

したがって、「自己相関係数を離散フーリエ変換するとパワースペクトルになる」。

故に

  • 数列$f_l$
  • 離散フーリエ変換$F_k$
  • パワースペクトル$P_k$
  • 自己相関係数$R_n$

の間には以下のような関係が存在する。

$$ \begin{eqnarray} &f_l& \rightarrow & F_k & \\ &\downarrow& ~~~ &\downarrow& \\ &R_n& \rightarrow &P_k& \end{eqnarray} $$

これは3章で（連続）フーリエ変換でみたものとほぼ同じ関係式である。

離散コサイン変換

フーリエ級数展開まで戻って考える。フーリエ級数展開というのは関数を$\{\cos kx, \sin kx, \frac{1}{2}\}$で表す方法でした。$\frac{1}{2}$は直流成分と呼ばれ波で近似できない部分を担当していました。例えば$f(t)=1$のような関数をフーリエ級数展開するとこの直流成分だけが残ります。

$\sin kx$ はすべて奇関数なので、これらで表される関数も奇関数です。逆に$\cos kx$ はすべて偶関数なので、これで表される関数も偶関数です。

今N個の実数データ点$\{f_l\} \ (0\leq l < N)$ が与えられたとき、これを反転して加えるとこれは偶関数と見ることができる。つまり

$$ f_{N-1}, f_{N-2}, ..., f_0, f_0, f_1, ..., f_{N-1} $$

と並べるとこれは偶関数となる。これをrenameして、 $$ \overline{f_l} = \begin{cases} f_l \ (0 \leq l < N) \\ f_{-l-1} \ (-N \leq l < 0) \end{cases} $$ とした$\bar{f_l}$にたいしてフーリエ級数展開すると、(これらは実数で上線の意味は共役でないことと、添字lはーN～N-1で定義されていることに注意）

$$ \begin{eqnarray} \bar{f_l} &=& \sum_{k=-N}^{N-1} \bar{F_k} e^{\frac{i2\pi kl}{2N}} \\ \bar{F_k} &=& \frac{1}{2N} \sum_{l=-N}^{N-1} \bar{f_l} e^{\frac{-i2\pi kl}{2N}}...(1) \end{eqnarray} $$

これを解いていく。これは偶関数なので、最終的にはeの虚数乗を消してcosだけで表すことを目指す。まずは第2式 $$ \begin{eqnarray} \bar{F_k} &=& \frac{1}{2N} \sum_{l=-N}^{N-1} \bar{f_l} e^{\frac{-i\pi kl}{N}} \\ &=& \frac{1}{2N} \sum_{l=-N}^{-1} \bar{f_l} e^{\frac{-i\pi kl}{N}} + \frac{1}{2N} \sum_{l=0}^{N-1} \bar{f_l} e^{\frac{-i\pi kl}{N}} \\ &=& \frac{1}{2N} \sum_{l=-N}^{-1} f_{-l-1} e^{\frac{-i\pi kl}{N}} + \frac{1}{2N} \sum_{l=0}^{N-1} f_l e^{\frac{-i\pi kl}{N}} \\ &=& \frac{1}{2N} \sum_{l=0}^{N-1} f_{l} e^{\frac{-i\pi k(-l-1)}{N}} + \frac{1}{2N} \sum_{l=0}^{N-1} f_l e^{\frac{-i\pi kl}{N}} (\because 第一項のlを変えた) \\ &=& \frac{1}{2N} \sum_{l=0}^{N-1} \left( f_{l} e^{\frac{i\pi k(l+1)}{N}} + f_l e^{\frac{-i\pi kl}{N}} \right) \\ &=& \frac{1}{2N} \sum_{l=0}^{N-1} \left( f_{l} e^{\frac{i\pi k(l+\frac{1}{2})}{N}} e^{\frac{i\pi k\frac{1}{2}}{N}} + f_l e^{\frac{-i\pi k(l+\frac{1}{2})}{N}} e^{\frac{i\pi k\frac{1}{2}}{N}} \right) \\ &=& \frac{1}{2N} \sum_{l=0}^{N-1} f_{l} \left( e^{\frac{i\pi k(l+\frac{1}{2})}{N}} + e^{\frac{-i\pi k(l+\frac{1}{2})}{N}} \right) e^{\frac{i\pi k\frac{1}{2}}{N}} \\ &=& \frac{1}{N} \sum_{l=0}^{N-1} f_{l} \frac{1}{2} \left( e^{\frac{i\pi k(l+\frac{1}{2})}{N}} + e^{\frac{-i\pi k(l+\frac{1}{2})}{N}} \right) e^{\frac{i\pi k\frac{1}{2}}{N}} \\ &=& \frac{1}{N} e^{\frac{i\pi k}{2N}} \sum_{l=0}^{N-1} f_{l} \cos(\frac{\pi k(l+\frac{1}{2})}{N}) \end{eqnarray} $$

これで、第2式は解けた。 形を整えるために $$ F_k = e^{\frac{-i\pi k}{2N}} 2 \bar{F_k} ...(2) $$ と定義すると $$ F_k = \frac{2}{N} \sum_{l=0}^{N-1} f_{l} \cos(\frac{\pi k(l+\frac{1}{2})}{N}) $$ となる

次は第一式。最終的に求めたいのは$f_l$なので、$0\leq l<N$と仮定して考える。先の式より$F_k$が実数であること(※)を用いる。

$$ \begin{eqnarray} f_l &=& \bar{f_l} \\ &=& \sum_{k=-N}^{N-1} \bar{F_k} e^{\frac{i2\pi kl}{2N}} \\ &=& \bar{F_0} + \sum_{k=1}^{N-1} \bar{F_k} e^{\frac{i\pi kl}{N}} + \sum_{k=-N+1}^{-1} \bar{F_k} e^{\frac{i\pi kl}{N}}(\because \bar{F}_{-N}=0) \\ &=& \bar{F_0} + \sum_{k=1}^{N-1} \bar{F_k} e^{\frac{i\pi kl}{N}} + \sum_{k=1}^{N-1} \bar{F_{-k}} e^{\frac{-i\pi kl}{N}} \\ &=& \bar{F_0} + \sum_{k=1}^{N-1} \bar{F_k} e^{\frac{i\pi kl}{N}} + \sum_{k=1}^{N-1} \overline{\bar{F_k}} e^{\frac{-i\pi kl}{N}} (\because (1)) \\ &=& \frac{F_0}{2} + \sum_{k=1}^{N-1} (\frac{1}{2} e^{\frac{i\pi k}{2N}} F_k) e^{\frac{i\pi kl}{N}} + \sum_{k=1}^{N-1} \overline{(\frac{1}{2} e^{\frac{i\pi k}{2N}} F_k) } e^{\frac{-i\pi kl}{N}} \\ &=& \frac{F_0}{2} + \frac{1}{2} \sum_{k=1}^{N-1} (e^{\frac{i\pi k(2l+1)}{2N}} F_k) + \frac{1}{2} \sum_{k=1}^{N-1} e^{\frac{-i\pi k(2l+1)}{2N}} F_k(\because (※)) \\ &=& \frac{F_0}{2} + \frac{1}{2} \sum_{k=1}^{N-1}F_k (e^{\frac{i\pi k(2l+1)}{2N}} +e^{\frac{-i\pi k(2l+1)}{2N}} ) \\ &=& \frac{F_0}{2} + \sum_{k=1}^{N-1}F_k \cos {\frac{\pi k(2l+1)}{2N}} \end{eqnarray} $$

よって離散コサイン変換が求まった $$ f_l = \frac{F_0}{2} + \sum_{k=1}^{N-1}F_k \cos {\frac{\pi k(2l+1)}{2N}} \\ F_k = \frac{2}{N} \sum_{l=0}^{N-1} f_{l} \cos(\frac{\pi k(l+\frac{1}{2})}{N}) $$