離散フーリエ変換(5) - 畳み込み定理の証明

"相互相関関数はそれぞれDFTしてから掛け合わせて逆DFTすれば計算できるよ"

なんていわれてもにわかには信じ難いですよね。

ということで簡単に証明してみたいと思います。

データ長 $N$ の二つのデータ $f_i$ と $t_i$ を考えます。

一応、元のデータが $f_i$ でその中から長さ $M \left( \le N\right)$ のテンプレートがどこにあるかを探す、的な状況を想定しています。

そういう時はテンプレートの末尾に $N - M$ 個の0を追加して $f_i$ と $t_i$ の長さがどちらも $N$ になるようにしておきます。

このとき、相互相関関数は

$c_\tau = \sum^{N - 1}_{n = 0} f_n t_{n - \tau}$

です。

こいつをDFTしてみます。

$C_k = \sum^{N-1}_{\tau = 0} c_\tau \exp\{- \frac{2 \pi i}{N} \tau k\}$
$= \sum^{N-1}_{\tau = 0} \left( \sum^{N-1}_{n = 0} f_n t_{n - \tau} \right) \exp\{- \frac{2 \pi i}{N} \tau k\}$
$= \sum^{N-1}_{\tau =0} \sum^{N-1}_{n = 0} f_n t_{n- \tau} \exp\{ - \frac{2 \pi i}{N} \left( \tau - n + n \right) k \}$
$= \sum^{N-1}_{n =0} f_n \left( \sum^{N-1}_{\tau = 0} t_{n - \tau} \exp\{ - \frac{2 \pi i}{N} \left(n - \tau \right) \left( -k \right) \} \right) \exp\{ - \frac{2 \pi i}{N} n k \}$

第２回でチラッと言いましたが $f_i$ も $t_i$ も長さNのデータが無限に繰り返されているものと仮定します。
したがって $f_{N + i} = f_i$ になります。

また、自明ですが、
$\exp\{ - \frac{2 \pi i}{N} \left(n - \tau + N \right) \left( -k \right) \} = \exp\{ - \frac{2 \pi i}{N} \left(n - \tau \right) \left( -k \right) \}$
も成立します。

これを踏まえると、

$\left( \sum^{N-1}_{\tau = 0} t_{n - \tau} \exp\{ - \frac{2 \pi i}{N} \left(n - \tau \right) \left( -k \right) \} \right) = T_{-k}$

が成り立ちます。

$T_k$ はもちろん

$T_k = \sum^{N-1}_{\tau = 0} t_{\tau} \exp\{- \frac{2 \pi i}{N} \tau k\}$

です。

”おいおいちょっとまってくれよ！　外側のΣのnに依存してるじゃねーか！　さらにτの符号が負だからtの順番が逆になっちゃうよ！　なのに普通にDFTが成り立つことにしちゃって良いのかよ！”

と、僕は思いました。　が、少し落ち着いて考えると順番もnも関係なかったのでした。

小さいNで例を挙げるとわかりやすいと思います。

たとえば、 $N = 5, t = \{t_0, t_1, t_2, t_3, t_4\}$ を考えて見ます。
$T_k = \sum^{N-1}_{\tau = 0} t_{\tau} \exp\{- \frac{2 \pi i}{N} \tau k\}$

は

$T_k = t_0 \exp\{- \frac{2 \pi i}{5} 0 k\} + t_1 \exp\{- \frac{2 \pi i}{5} 1 k\} + t_2 \exp\{- \frac{2 \pi i}{5} 2 k\} + t_3 \exp\{- \frac{2 \pi i}{5} 3 k\} + t_4 \exp\{- \frac{2 \pi i}{5} 4 k\}$

と書き下せるわけです。

nを3として

$\left( \sum^{N-1}_{\tau = 0} t_{n - \tau} \exp\{ - \frac{2 \pi i}{N} \left(n - \tau \right) \left( -k \right) \} \right)$

を書き下してみます。

$t_3 \exp\{- \frac{2 \pi i}{5} 3 \left( -k \right) \} + t_2 \exp\{- \frac{2 \pi i}{5} 2 \left( -k \right) \} + t_1 \exp\{- \frac{2 \pi i}{5} 1 \left( -k \right) \} + t_0 \exp\{- \frac{2 \pi i}{5} 0 \left( -k \right) \} + t_{-1} \exp\{- \frac{2 \pi i}{5} \left( -1 \right) \left( -k \right) \}$