線形畳み込みと循環畳み込み

畳み込み演算

線形畳み込み

ここで、線形畳み込みについて説明しておきます。線形畳み込みは次の式で表されます。

$$h(n) * x(n) = \sum_{m=0}^{N-1} h(m) x(n-m)$$

\(x[n]\)、\(h[n]\)が下記のような場合を考えます。

$$h[n] = [1, 3, 1]$$

$$x[n] = [2, 1, 5, 3]$$

\(n\)	0	1	2	3	4	5
\(h[0]\times x[n]\)	\(h[0]\times x[0]\) =1 × 2	\(h[0]\times x[1]\) = 1 × 1	\(h[0]\times x[2]\) =1 × 5	\(h[0]\times x[3]\) =1 × 5
\(h[1]\times x[n-1]\)		\(h[1]\times x[0]\) = 3 × 2	\(h[1]\times x[1]\) =3 × 1	\(h[1]\times x[2]\) =1 × 5	\(h[1]\times x[3]\) =3 × 3
\(h[2]\times x[n-2]\)			\(h[2]\times x[0]\) =1 × 2	\(h[2]\times x[1]\) =1 × 5	\(h[2]\times x[2]\) =1 × 5	\(h[0]\times x[4]\) =1 x 3
\(y\)	2	7	10	19	14	3

このことからわかるように、畳み込みは出力信号の長さが入力信号より長くなっていることがわかります。出力信号の長さはインパルス応答長を\(N\), 入力信号の長さを\(L\)とすると、

$$L+N-1$$

で出力信号の長さが決定されます。

循環畳み込み

循環畳み込みは次式で定義されます。Nを法とする巡回畳み込みは次式のようになります。

$$x(n) \otimes h(n) = \sum_{m=0}^{N-1} h(m) x((n-m))_N$$

$$ = \sum_{m=0}^{N-1} x(m) h((n-m))_N$$

\(x[n]\)、\(h[n]\)が下記のような場合を考えます。

$$h[n] = [1, 3, 1]$$

$$x[n] = [2, 1, 5, 3]$$

巡回畳み込みの場合、信号は周期性が仮定されるためxは以下のようになります。

n	-4	-3	-2	-1	0	1	2	3	4	5	6	7
x	2	1	5	3	2	1	5	3	2	1	5	3

したがって、巡回畳み込みの信号は以下のようになります。

\(n\)	0	1	2	3
\(h[0]\times x[n]\)	\(h[0]\times x[0]\) =1 × 2	\(h[0]\times x[1]\) = 1 × 1	\(h[0]\times x[2]\) =1 × 5	\(h[0]\times x[3]\) =1 × 5
\(h[1]\times x[n-1]\)	\(h[1]\times x[-1]\) =3 × 3	\(h[1]\times x[0]\) = 3 × 2	\(h[1]\times x[1]\) =3 × 1	\(h[1]\times x[2]\) =1 × 5
\(h[2]\times x[n-2]\)	\(h[1]\times x[-2]\) =1 × 5	\(h[2]\times x[-1]\) =1 × 3	\(h[2]\times x[0]\) =1 × 2	\(h[2]\times x[1]\) =1 × 5
\(y\)	16	10	10	19

以上のように、巡回畳み込みの場合、畳み込み後の信号の長さは入力信号と同じになります。

また、上記の線形畳み込みと異なる結果が得られていることがわかります。

線形畳み込みと循環畳み込みが等価になる条件

上記の結果から分かるように、線形畳み込みと循環畳み込みは異なる演算です。しかし、同じ結果を得られる条件があります。

まず、両者を比較すると出力される信号の長さが異なることがあります。x, hという2つの信号があり、それぞれN, Lの長さだとすると線形畳み込みの結果は長さN+L-1の信号となります。一方で、Nを法とする巡回畳み込みの結果は長さNの信号となります。結果を一致させるためには、少なくとも同じ信号の長さを得る必要があります。

そのために巡回畳み込みでは、x, hともに同じ信号長N+L-1に0づめするという操作を追加します。この操作を行うと一致させることができます。

実際に例を見てみましょう。

$$h[n] = [1, 3, 1]$$

$$x[n] = [2, 1, 5, 3]$$

このとき、N=4, L=3のため、線形畳み込みの結果の長さは4+3-1=6となります。

したがって、以下のように0づめを行います。

$$h[n] = [1, 3, 1, 0, 0, 0]$$

$$x[n] = [2, 1, 5, 3, 0, 0]$$

このとき、周期性のためx[n]は次のようになります。

n	-4	-3	-2	-1	0	1	2	3	4	5	6	7
x	5	3	0	0	2	1	5	3	0	0	2	1

これらの信号に対する循環畳み込みの結果は以下のようになります。

\(n\)	0	1	2	3	4	5
\(h[0]\times x[n]\)	\(h[0]\times x[0]\) =1 × 2	\(h[0]\times x[1]\) = 1 × 1	\(h[0]\times x[2]\) =1 × 5	\(h[0]\times x[3]\) =1 × 3	\(h[0]\times x[4]\) =1 × 0	\(h[0]\times x[5]\) =1 × 0
\(h[1]\times x[n-1]\)	\(h[1]\times x[-1]\) =3 × 0	\(h[1]\times x[0]\) = 3 × 2	\(h[1]\times x[1]\) =3 × 1	\(h[1]\times x[2]\) =3 × 5	\(h[1]\times x[3]\) =3 × 3	\(h[1]\times x[4]\) =3 × 0
\(h[2]\times x[n-2]\)	\(h[2]\times x[-2]\) =1 × 0	\(h[2]\times x[-1]\) =1 × 0	\(h[2]\times x[0]\) =1 × 2	\(h[2]\times x[1]\) =1 × 1	\(h[2]\times x[2]\) =1 × 5	\(h[0]\times x[3]\) =1 x 3
\(h[3]\times x[n-3]\)	\(h[3]\times x[-3]\) =0 ×3	\(h[3]\times x[-2]\) =0 ×0	\(h[3]\times x[-1]\) =0 × 0	\(h[3]\times x[0]\) =0 × 2	\(h[3]\times x[1]\) =1 × 0	\(h[3]\times x[2]\) =0 × 5
\(h[4]\times x[n-4]\)	\(h[4]\times x[-4]\) =0 × 5	\(h[4]\times x[-3]\) =0 × 3	\(h[4]\times x[-2]\) =0 × 0	\(h[4]\times x[-1]\) =0 × 0	\(h[4]\times x[0]\) =1 × 2	\(h[4]\times x[1]\) =0 × 0
\(h[5]\times x[n-5]\)	\(h[5]\times x[-5]\) =0 × 1	\(h[5]\times x[-4]\) =0 × 5	\(h[5]\times x[-3]\) =0 × 3	\(h[5]\times x[-2]\) =0 × 0	\(h[5]\times x[-1]\) =1 × 0	\(h[5]\times x[0]\) =0 × 2
\(y\)	2	7	10	19	14	3

上記のように結果が一致することがわかります。

まとめ

本記事では、２つの畳み込み演算について紹介しました。線形畳み込みと循環畳み込みの２つの演算を紹介し、それぞれは異なる演算であることを示しました。また、それらの結果が一致するような条件も示しました。