Convolución circular

Operación matemática

La convolución circular , también conocida como convolución cíclica , es un caso especial de convolución periódica , que es la convolución de dos funciones periódicas que tienen el mismo período. La convolución periódica surge, por ejemplo, en el contexto de la transformada de Fourier de tiempo discreto (DTFT). En particular, la DTFT del producto de dos secuencias discretas es la convolución periódica de las DTFT de las secuencias individuales. Y cada DTFT es una suma periódica de una función de transformada de Fourier continua (véase Transformada de Fourier de tiempo discreto § Relación con la transformada de Fourier ). Aunque las DTFT suelen ser funciones continuas de frecuencia, los conceptos de convolución periódica y circular también son directamente aplicables a secuencias discretas de datos. En ese contexto, la convolución circular desempeña un papel importante en la maximización de la eficiencia de un cierto tipo de operación de filtrado común.

Definiciones

La convolución periódica de dos funciones T-periódicas, y se puede definir como : ${\displaystyle h_{_{T}}(t)}$ ${\displaystyle x_{_{T}}(t)}$

${\displaystyle \int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau ,}$   ^{[1] [2]}

donde es un parámetro arbitrario. Una definición alternativa, en términos de la notación de convolución lineal normal o aperiódica , se deduce de expresar y como sumas periódicas de componentes aperiódicas y , es decir : ${\displaystyle t_{o}}$ ${\displaystyle h_{_{T}}(t)}$ ${\displaystyle x_{_{T}}(t)}$ ${\displaystyle h}$ ${\displaystyle x}$

${\displaystyle h_{_{T}}(t)\ \triangleq \ \sum _{k=-\infty }^{\infty }h(t-kT)=\sum _{k=-\infty }^{\infty }h(t+kT).}$

Entonces :

Ambas formas pueden denominarse convolución periódica . ^[a] El término convolución circular ^{[2] [3]} surge del importante caso especial de restringir las partes distintas de cero de ambos y al intervalo Entonces la suma periódica se convierte en una extensión periódica ^[b] , que también puede expresarse como una función circular : ${\displaystyle h}$ ${\displaystyle x}$ ${\displaystyle [0,T].}$

${\displaystyle x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} \,}$( cualquier número real ) ^[c]

Y los límites de integración se reducen a la longitud de la función : ${\displaystyle h}$

${\displaystyle (h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )\cdot x((t-\tau )_{\mathrm {mod} \ T})\ d\tau .}$^{[d] [e]}

Secuencias discretas

De manera similar, para secuencias discretas y un parámetro N , podemos escribir una convolución circular de funciones aperiódicas y como : ${\displaystyle h}$ ${\displaystyle x}$

${\displaystyle (h*x_{_{N}})[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot \underbrace {x_{_{N}}[n-m]} _{\sum _{k=-\infty }^{\infty }x[n-m-kN]}}$

Esta función es N -periódica. Tiene como máximo N valores únicos. Para el caso especial en que la extensión no nula de x y h sea ≤ N , es reducible a la multiplicación de matrices donde el núcleo de la transformación integral es una matriz circulante .

Ejemplo

La convolución circular se puede acelerar con el algoritmo FFT, por lo que se suele utilizar con un filtro FIR para calcular de forma eficiente las convoluciones lineales. Estos gráficos ilustran cómo es posible. Tenga en cuenta que un tamaño de FFT mayor (N) evitaría la superposición que hace que el gráfico n.° 6 no coincida exactamente con todo el n.° 3.

En la figura se ilustra un caso de gran interés práctico. La duración de la secuencia x es N (o menor) y la duración de la secuencia h es significativamente menor. Por lo tanto, muchos de los valores de la convolución circular son idénticos a los valores de x∗h , que es en realidad el resultado deseado cuando la secuencia h es un filtro de respuesta al impulso finito (FIR). Además, la convolución circular es muy eficiente de calcular, utilizando un algoritmo de transformada rápida de Fourier (FFT) y el teorema de convolución circular .

También existen métodos para tratar una secuencia x que es más larga que un valor práctico para N. La secuencia se divide en segmentos ( bloques ) y se procesa por partes. Luego, los segmentos filtrados se vuelven a unir cuidadosamente. Los efectos de borde se eliminan superponiendo los bloques de entrada o los bloques de salida. Para ayudar a explicar y comparar los métodos, los analizamos en el contexto de una secuencia h de longitud 201 y un tamaño de FFT de  N  = 1024.

Bloques de entrada superpuestos

Este método utiliza un tamaño de bloque igual al tamaño de FFT (1024). Lo describimos primero en términos de convolución normal o lineal . Cuando se realiza una convolución normal en cada bloque, hay transitorios de inicio y decaimiento en los bordes del bloque, debido a la latencia del filtro (200 muestras). Solo 824 de las salidas de convolución no se ven afectadas por los efectos de borde. Las demás se descartan o simplemente no se calculan. Eso causaría espacios en la salida si los bloques de entrada son contiguos. Los espacios se evitan superponiendo los bloques de entrada en 200 muestras. En cierto sentido, se "guardan" 200 elementos de cada bloque de entrada y se transfieren al siguiente bloque. Este método se conoce como solapamiento-guardado [ ^4], aunque el método que describimos a continuación requiere un "guardado" similar con las muestras de salida.

Cuando se utiliza una FFT para calcular las 824 muestras DFT no afectadas, no tenemos la opción de no calcular las muestras afectadas, pero los efectos de borde de entrada y de salida se superponen y se suman debido a la convolución circular. En consecuencia, la salida de FFT inversa (IFFT) de 1024 puntos contiene solo 200 muestras de efectos de borde (que se descartan) y las 824 muestras no afectadas (que se mantienen). Para ilustrar esto, el cuarto cuadro de la figura de la derecha representa un bloque que se ha extendido periódicamente (o "circularmente"), y el quinto cuadro representa los componentes individuales de una convolución lineal realizada en toda la secuencia. Los efectos de borde son donde las contribuciones de los bloques extendidos se superponen a las contribuciones del bloque original. El último cuadro es la salida compuesta, y la sección de color verde representa la parte no afectada.

Bloques de salida superpuestos

Este método se conoce como overlap-add . ^[4] En nuestro ejemplo, utiliza bloques de entrada contiguos de tamaño 824 y rellena cada uno con 200 muestras de valor cero. Luego superpone y suma los bloques de salida de 1024 elementos. No se descarta nada, pero se deben "guardar" 200 valores de cada bloque de salida para la adición con el siguiente bloque. Ambos métodos avanzan solo 824 muestras por IFFT de 1024 puntos, pero overlap-save evita el relleno inicial con ceros y la adición final.

Véase también

• Teorema de convolución
• Matriz circulante
• Transformada de Hilbert discreta

Citas de páginas

1. McGillem y Cooper, pág. 172 (4-6)
2. McGillem y Cooper, pág. 183 (4-51)
3. Oppenheim y Shafer, pág. 559 (8.59)
4. Oppenheim y Shafer, pág. 571 (8.114), mostrado en formato digital
5. McGillem y Cooper, pág. 171 (4-22), mostrado en formato digital

Referencias

1. Jeruchim, Michel C.; Balaban, Philip; Shanmugan, K. Sam (octubre de 2000). Simulación de sistemas de comunicación: modelado, metodología y técnicas (2.ª ed.). Nueva York: Kluwer Academic Publishers. págs. 73–74. ISBN 0-30-646267-2.
2. Udayashankara, V. (junio de 2010). Procesamiento de señales digitales en tiempo real . India: Prentice-Hall. pág. 189. ISBN 978-8-12-034049-7.
3. Priemer, Roland (julio de 1991). Introducción al procesamiento de señales. Serie avanzada en ingeniería eléctrica e informática. Vol. 6. Teaneck, NJ: World Scientific Pub Co Inc. págs. 286–289. ISBN 9971-50-919-9.
4. Rabiner, Lawrence R.; Gold, Bernard (1975). Teoría y aplicación del procesamiento de señales digitales . Englewood Cliffs, NJ: Prentice-Hall. pp. 63–67. ISBN 0-13-914101-4.

5. Oppenheim, Alan V. ; Schafer, Ronald W. ; Buck, John R. (1999). Procesamiento de señales en tiempo discreto (2.ª ed.). Upper Saddle River, NJ: Prentice Hall. págs. 548, 571. ISBN 0-13-754920-2.
6. McGillem, Clare D.; Cooper, George R. (1984). Análisis de señales y sistemas continuos y discretos (2.ª edición). Holt, Rinehart y Winston. ISBN 0-03-061703-0.

Lectura adicional

• Oppenheim, Alan V.; Willsky, con S. Hamid (1998). Señales y sistemas . Pearson Education. ISBN 0-13-814757-4.