直線畳み込みと循環畳み込み

離散時間信号同士の循環畳み込みと直線畳み込みの比較です．
2つの信号を \(x[n]\), \(h[n]\) とし，それぞれを周期 \(N\) の周期信号とみなしたものを \(\tilde{x}_N [n]\), \(\tilde{h}_N [n]\) とすると，

循環畳み込み：	\(x[n]\)N\(\displaystyle h[n]=\sum_{m=0}^N \tilde{x}_N [m] \tilde{h}_N [n-m]\)
直線畳み込み：	\(\displaystyle x[n]*h[n] = \sum_{m=-\infty}^\infty x[m]h[n-m]\)

と表されます．

直線畳み込みは通常の意味での畳み込みです．信号の先頭は先頭，末尾は末尾として扱い，\(N\) 点の信号同士の直線畳み込みを行うと，長さが \(2N-1\) 点になります．一方，循環畳み込みは信号の末尾と先頭をつなげ周期信号として扱い，畳み込みを行った信号の長さは \(N\) 点のままです．通常の（直線）畳み込みを行った際に元の信号長 \(N\) の範囲を超える部分が，先頭に回り込んできます．

線形時不変システムの出力は，システムへの入力信号とシステムのインパルス応答との畳み込みです．一般に，\(N\) 点の信号同士の畳み込みを行うには，\(O(N^2)\) の演算が必要ですが，時間領域での畳み込みは周波数領域での積になりますので，周波数領域でスペクトルの積を計算すれば，この計算自体は \(O(N)\) で済みます．信号を周波数領域へ変換し，積を行ってその結果を時間領域へ戻すには計3回のDFT演算が必要ですが，DFTの高速計算アルゴリズムであるFFTの計算量は \(O(N \log_2 N)\) ですので，ある程度以上長い信号であれば定義式通り時間領域で畳み込みを行うよりも周波数領域経由で畳み込みを計算した方が全体としての計算量は少なくなります．

ここで注意が必要なのは，時間領域と周波数領域の間の変換をDFT/FFTにより計算する場合，信号を周期信号として扱っていることです（DFTの計算は，数式上離散時間フーリエ級数 (DTFS) と同じ）．つまり，DFT/FFTにより周波数スペクトルへ変換し，積をとってから逆DFT/FFTにより時間領域へ戻した場合，計算されるのは循環畳み込みです．これが意図した結果ならば構わないのですが，信号の先頭は先頭，末尾は末尾として扱いたい場合，つまり直線畳み込みを計算したい場合は少なくありません．そのような場合は，信号をゼロ詰めして信号の長さを伸ばしてから周波数領域経由の計算を行います．

このページの信号は，初期値として \(x[n]\) の末尾付近に値がある信号となっており，循環畳み込みでは先頭に回り込んでいます．この末尾付近の信号の値をゼロにする，もしくは信号の長さを伸ばすと，先頭への信号の回り込みが解消され循環畳み込みと直線畳み込みが等しくなる様子が確認されます．

\(x[n]\)
\(h[n]\)
\(x[n]\)N\(h[n]\)
\(x[n]*h[n]\)
	\(k=\) 0
	強調表示 \(x[n]\|_{n=k}\) \(h[n]\|_{n=k}\)