Convolución lineal y circular

Este ejemplo muestra cómo establecer una equivalencia entre convolución lineal y circular.

La convolución lineal y circular son, fundamentalmente, operaciones distintas. Sin embargo, existen condiciones en las que la convolución lineal y circular son equivalentes. Establecer esta equivalencia tiene implicaciones importantes. Para dos vectores, x e y, la convolución circular es igual a la transformada de Fourier discreta inversa (DFT) del producto de las DFT de los vectores. Conocer las condiciones en las que la convolución lineal y circular son equivalentes le permite utilizar la DFT para calcular de forma eficiente las convoluciones lineales.

La convolución lineal de un vector de N puntos, x, y un vector de L puntos, y, tiene una longitud de N + L - 1.

Para que la convolución circular de x e y sea equivalente, debe rellenar los vectores con ceros hasta la longitud N + L - 1 como mínimo antes de tomar la DFT. Después de invertir el producto de las DFT, conserve solo los primeros elementos N + L - 1.

Cree dos vectores, x e y, y calcule la convolución lineal de ambos.

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

El resultado tiene una longitud de 4+3-1.

Rellene ambos vectores con ceros hasta la longitud 4+3-1. Obtenga la DFT de ambos vectores, multiplique las DFT y obtenga la DFT inversa del producto.

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

La convolución circular de los vectores rellenados con ceros, xpad e ypad, equivale a la convolución lineal de x e y. Conserva todos los elementos de ccirc porque el resultado tiene una longitud de 4+3-1.

Represente el resultado de la convolución lineal y la inversa del producto de la DFT para mostrar la equivalencia.

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')

Rellene los vectores hasta la longitud 12 y obtenga la convolución circular utilizando la DFT inversa del producto de las DFT. Conserve solo los primeros elementos 4+3-1 para producir un resultado equivalente a la convolución lineal.

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);

El software Signal Processing Toolbox™ tiene una función, cconv, que devuelve la convolución circular de dos vectores. Puede obtener la convolución lineal de x e y utilizando la convolución circular con el siguiente código.

ccirc2 = cconv(x,y,6);

cconv utiliza internamente el mismo procedimiento basado en la DFT que se ilustra en el ejemplo anterior.