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