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

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

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