Convolucion Usando Dft

CONVOLUCION USANDO LA DFT

Enrique Rosales Gaytán
enrrosales@udec.cl





INTRODUCCIÓN


Este trabajo consiste en analizar dos métodos propuestos para trabajar la convolución a través de la transformada de Fourier discreta: El metodo de Overlap-add y Overlap save. Además, se mostrarán ejemplos para cada una de ella, y gráficos que ayuden a comprender mejor dichos métodos.METODO DE OVERLAP-ADD


Este método es utilizado para calcular la convoloción de dos señales a traves de la DFT. Principalmente se utiliza para calcular la salida de una señal a un filtro del tipo FIR. Asi se puede tomar una señal x(n) definida por:


[pic] (1)


que será convolucionada con una señal de h(n) de largo L, de la siguiente manera.[pic] (2)


Debe asumirse que la señal x(n) es una señal de un largo mucho mayor a L. El metodo consiste en particionar x(n) en subsecuencias de manera que estas no se superpongan unas con las otras, cada una de un

largo M. Asi x(n) debe ser escrita como una suma de subseñales

[pic] (3)

O de otra forma: [pic] (4)

Donde[pic]

Luego laconvolucion de la señal x(n) con h(n), esta dada por:

[pic] (5)
[pic] (6)

O de otra manera [pic] (7)


Debido a que cada secuencia yi (n) es de longitud N = L + M - I. que se puede encontrar multiplicando el DFT de N puntos de
xi (n) y h (n)


La razon del nombre “ overlap-add”, que en ingles significasuperposiciones agregadas. Es debido a que las salidas del sistema [pic] y [pic]para cualquier valor de i, se superponen en N-M puntos, y a medida que se va realizando la suma, estos puntos de acumulación se añaden. A continuación se verá una forma grafica para la representación de el metodo estudiado.


[pic]
Fig 1 Señal de entrada particionada

Que representa la secuencia de los i-esimo terminosde la entrada x(n), particionados en subsecuencias de largo M.

[pic]

Fig 2. Señal de salida en overlap-add
La figura anterior muestra cada una de las i-esimas salidas del sistema y como se van agregando los puntos, en la parte achurada de dicha figura.


METODO DE OVERLAP-SAVE



Este metodo, es de la misma utilidad del metodo anterior, es decir ayuda a calcular laconvolucion, pero en este caso la convolucion circular, usando la transformada discreta de Fourier . Este método toma ventaja del hecho de que el alias que ocurre en una convolucion circular sólo afecta a una parte de la secuencia. Si se tienen x(n) y h(n) dos secuencias de largo finito, L y N respectivamente, la convolucion lineal y(n) es una secuencia de largo N+L-1. Así y por otra parte si suponemosque N>L , y realizamos una convolucion circular entre ambas señales x(n) e h(n) se obtiene:

[pic] (8)

Debido a que el termino y(n+N), es el unico termino que tiene un alias en el intervalo de [pic], y ademas porque de la señal y(n+N) solo se superponen las primeras L-1 muestras , el resto de la señal de convolucion circular para el intervalo restante, no será un alias. Así, con la separacionen subsecuencias de x(n). la convolucion lineal, es realizada reuniendo convoluciones circulares.




Luego se puede establecer un procedimiento a seguir de la siguiente manera:


Sea [pic], la secuencia:

[pic][pic] [pic]

Se realiza la convolucion circular de N puntos de x1(n) con h(n), para formar el producto H(K)X1(K), asi luego a este resultado se le aplica la IDFT, paraencontrar y1(n) , así los primero L-1 valores de la secuencia son alias. Y por ende los ultimos N-L+1 valores de la secuencia corresponden a la convolucion de x(n) con h(n) = y(n)
Así debido al relleno con ceros al inicio de la señal x1(n) los ultimos N-L+1 de la señal, serán los primeros N-L+1 valores de y(n).

[pic] ; [pic] (9)


Luego se define un x2(n) de N puntos, que se extrae...