線形および循環畳み込み

この例は、線形畳み込みと循環畳み込みの等価性を証明する方法を示しています。

線形畳み込みと循環畳み込みは、基本的には別の演算です。ただし、線形畳み込みと循環畳み込みが等価になる条件があります。この等価性の立証は重要な意味をもちます。2 つのベクトルxとyに対して、循環畳み込みはそれらのベクトルの離散フーリエ変換 (DFT) の積の逆離散フーリエ変換と等価です。線形畳み込みと循環畳み込みが等価になる条件を知ることによって、DFT を使用して線形畳み込みを効率的に計算することができます。

N点のベクトルxとL点のベクトルyの線形畳み込みの長さはN+L-1 です。

xとyの循環畳み込みが等価になるためには、DFT を実行する前にベクトルにゼロを付加して長さを少なくともN+L- 1 にしなければなりません。DFT の積の逆変換を求めると、最初のN+L- 1 の要素だけが残ります。

2 つのベクトルxとyを作成し、2 つのベクトルの線形畳み込みを計算します。

x = [2 1 2 1]; y = [1 2 3]; clin = conv(x,y);

出力の長さは 4+3-1 です。

両ベクトルにゼロを付加して長さを 4+3-1 にします。両ベクトルの DFT を求め、2 つの DFT を乗算します。その積の逆 DFT を求めます。

xpad = [x zeros(1,6-length(x))]; ypad = [y zeros(1,6-length(y))]; ccirc = ifft(fft(xpad).*fft(ypad));

ゼロが付加されたベクトルxpadとypadの循環畳み込みは、xとyの線形畳み込みと等価です。出力の長さが 4+3-1 なので、ccircのすべての要素が残ります。

等価性を示すために、線形畳み込みと DFT の積の逆出力をプロットします。

subplot(2,1,1) stem(clin,'filled') ylim([0 11]) title('Linear Convolution of x and y') subplot(2,1,2) stem(ccirc,'filled') ylim([0 11]) title('Circular Convolution of xpad and ypad')

ベクトルにゼロを付加して長さを 12 にします。DFT の積の逆 DFT を使用して循環畳み込みを求めます。最初の 4+3-1 の要素だけ残して、線形畳み込みと等しい結果になります。

N = length(x)+length(y)-1; xpad = [x zeros(1,12-length(x))]; ypad = [y zeros(1,12-length(y))]; ccirc = ifft(fft(xpad).*fft(ypad)); ccirc = ccirc(1:N);

Signal Processing Toolbox™ ソフトウェアには、2 つのベクトルの循環畳み込みの結果を返す関数cconvがあります。次のコードにより、循環畳み込みを使用してxとyの線形畳み込みが求められます。

ccirc2 = cconv(x,y,6);

cconvは、前の例で説明したものと同じ DFT を使用した手順を内部で使用しています。