Линейная и круговая свертка

В этом примере показано, как установить эквивалентность между линейной и круговой сверткой.

Линейная и круговая свертка является существенно различными операциями. Однако существуют условия, при которой линейной и круговой свертке эквивалентны. Установление этой эквивалентности имеет важные последствия. Для двух векторов, x и y, круговая свертка равна обратному дискретному преобразованию Фурье (DFT) продукта ДПФ векторов, знающих условия, при которой линейной и круговой свертке эквивалентны, позволяет вам использовать ДПФ, чтобы эффективно вычислить линейные свертки.

Линейная свертка вектора N значений, x, и вектор L-точки, y, имеет длину N + L - 1.

Для круговой свертки X и Y, чтобы быть эквивалентными, необходимо заполнить векторы нулями к длине, по крайней мере, N + L - 1, прежде чем вы возьмете ДПФ. После того, как вы инвертируете продукт ДПФ, сохраняете только первый N + L - 1 элемент.

Создайте два вектора, x и y, и вычислите линейную свертку этих двух векторов.

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

Выход имеет длину 4+3-1.

Заполните оба вектора нулями к длине 4+3-1. Получите ДПФ обоих векторов, умножьте ДПФ и получите обратного ДПФ продукта.

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

Круговая свертка дополненных нулем векторов, xpad и ypad, эквивалентно линейной свертке x и y. Вы сохраняете все элементы ccirc потому что выход имеет длину 4+3-1.

Постройте выход линейной свертки и инверсию продукта ДПФ, чтобы показать эквивалентность.

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 и получите круговую свертку с помощью обратного ДПФ продукта ДПФ, сохраняют только первый 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™ имеет функцию, cconv, это возвращает круговую свертку двух векторов. Можно получить линейную свертку x и y использование круговой свертки со следующим кодом.

ccirc2 = cconv(x,y,6);

cconv внутренне использует ту же основанную на ДПФ процедуру, проиллюстрированную в предыдущем примере.