Convolución de secuencias

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de noviembre de 2021; las comprobaciones requieren 4 ediciones .

La convolución de secuencia es una transformación lineal de dos secuencias numéricas . El resultado de la convolución es una secuencia cuyos elementos se obtienen multiplicando y sumando los elementos de las secuencias originales de tal manera que los miembros de una secuencia se toman con índices crecientes y los miembros de la otra con índices decrecientes (lo que sirve como base para el nombre aceptado de esta operación). Hay convoluciones lineales y cíclicas, que se utilizan para secuencias finitas y periódicas, respectivamente.

La convolución de secuencias y se denota como . $a$ $b$ ${\ estilo de visualización a * b}$

El plegado de secuencias es un caso especial del plegado de funciones . La convolución también está estrechamente relacionada con la correlación cruzada .

Tipos de pliegues

Los tipos tradicionales de paquetes incluyen:

convolución lineal (aperiódica);
convolución cíclica (circular, periódica);
convolución usando la transformada discreta de Fourier.

Cálculo de convolución

Considere las reglas y la secuencia para calcular cada tipo de convolución.

Cálculo de convolución lineal

Sean dadas dos secuencias numéricas:

a=\left\{a_{0},a_{1},\ldots,a_{N_{1}-1}\right\},

b=\left\{b_{0},b_{1},\ldots,b_{N_{2}-1}\right\}.

Para calcular la convolución lineal de estas sucesiones, debes realizar los siguientes pasos:

calcule el número de elementos de la secuencia de salida usando la fórmula:

N_{{fuera}}=N_{1}+N_{2}-1,

dónde:

N_{{fuera}}

es el número de elementos en la secuencia de salida;

N_1

es el número de elementos en la primera secuencia;

N_2

es el número de elementos en la segunda secuencia;

rellenar ambas secuencias con ceros para que el número de elementos en ambas secuencias sea igual a ; $N_{{fuera}}$

mostrar simétricamente una de las secuencias con respecto al eje y;

multiplica estas dos secuencias.

Como resultado de realizar todas las operaciones descritas anteriormente, obtenemos una convolución lineal de las sucesiones y , cuyos elementos se calculan mediante una de dos fórmulas: $C$ $a$ $b$

c_{i}=\sum \limits _{k=0}^{N_{1}-1}a_{k}b_{ik},\;i=0,\ldots,N_{out}- una,

c_{i}=\sum \limits _{k=0}^{N_{2}-1}a_{ik}b_{k},\;i=0,\ldots,N_{out}- una.

Aquí se supone que para , los elementos de la secuencia correspondiente son iguales a cero. $ik<0$

Puede verificar la equivalencia de las fórmulas y, como resultado, la conmutatividad de la operación de convolución simplemente reemplazando los índices en una de las fórmulas. $j=ik$

Cálculo de convolución cíclica

Considere ahora dos secuencias numéricas de la misma longitud : $norte$

a=\left\{a_{0},a_{1},\ldots,a_{N-1}\right\},

b=\izquierda\{b_{0},b_{1},\ldots,b_{N-1}\derecha\}.

Para obtener una convolución circular periódica , es necesario imaginar que estas secuencias están ubicadas en dos círculos, uno de los cuales está dentro del otro. Los valores de cada una de estas secuencias son equidistantes entre sí. Para obtener cada valor de la convolución circular, es necesario imaginar que una de las secuencias se mueve en un círculo con respecto a la otra en el sentido de las agujas del reloj. Primero, toma el primer valor de la secuencia que gira, multiplica sucesivamente por los valores de otra secuencia y suma los resultados de las multiplicaciones y obtén el primer valor de la secuencia de salida . Luego repetimos estas acciones para cada valor de la secuencia que gira con respecto al otro. El número de elementos en la secuencia de salida será . $C'$ $C'$ $norte$

En otras palabras, los elementos de la convolución cíclica se calculan mediante la fórmula $C'$

c'_{i}=\sum \limits _{k=0}^{N-1}a_{k}b_{((ik))},\;i=0,\ldots,N- una,

donde _ $((ik))=(ik){\bmod {N))$

La secuencia resultante es equivalente a la convolución de dos señales periódicas, es decir, las secuencias y pueden considerarse definidas para todos por las fórmulas y . $a$ $b$ $i\en \mathbb {Z}$ ${\displaystyle a_{i}=a_{((i))))$ ${\displaystyle b_{i}=b_{((i))))$

Cálculo de la convolución aperiódica

Para obtener una convolución aperiódica, se realizan todas las mismas operaciones que para obtener una convolución circular, pero las secuencias pueden tener un número diferente de elementos (por ejemplo, y ) y deben completarse con ceros hasta el número de . Al realizar este tipo de convolución, se elimina el efecto de superposición circular que ocurre con la convolución circular. Esta es una forma alternativa de calcular la convolución lineal. $N_1$ $N_2$ $N_{fuera}=N_{1}+N_{2}-1$

Relación entre circunvoluciones lineales y cíclicas

El enfoque descrito anteriormente hace posible establecer una conexión entre el cálculo de convoluciones lineales y cíclicas. Para ello, en la fórmula de los elementos de la convolución cíclica, dividimos la suma por dos, correspondientes a los casos y : $ik\geqslant 0$ $ik<0$

c'_{i}=\sum \limits _{k=0}^{i}a_{k}b_{ik}+\sum \limits _{k=i+1}^{N-1 }a_{k}b_{N+ik}.

Suponiendo ahora que en la primera suma en , y en la segunda suma en , podemos cambiar los límites de la suma y obtener una relación entre las circunvoluciones lineales y cíclicas en la forma $b_{ik}=0$ ${\ Displaystyle k> i}$ $b_{N+ik}=0$ ${\ estilo de visualización k <i}$

c'_{i}=\sum \limits _{k=0}^{N-1}a_{k}b_{ik}+\sum \limits _{k=0}^{N-1 }a_{k}b_{N+ik}=c_{i}+c_{N+i},\;i=0,\ldots,N-1.

La convolución lineal se puede calcular como cíclica si el segundo término de esta fórmula es igual a cero, es decir, los productos para todos y son iguales a cero . Para garantizar que se cumpla esta condición, se puede elegir la longitud de la convolución cíclica para que no sea menor que , mientras se rellenan las secuencias de entrada con ceros. ${\ Displaystyle a_ {k} b_ {N + ik}}$ $i$ $k$ $norte$ $N_{fuera}=N_{1}+N_{2}-1$

Cálculo de una convolución usando la transformada de Fourier

Para calcular la convolución utilizando la transformada discreta de Fourier, es necesario rellenar ambas secuencias de entrada con ceros para que el número de elementos en estas secuencias sea igual a . A continuación, es necesario realizar transformadas directas de Fourier de cada una de las secuencias. Luego, las secuencias transformadas se multiplican elemento por elemento, después de lo cual se realiza la transformación inversa del resultado de la multiplicación. $N_{{fuera}}$

El cálculo de la convolución de la forma descrita es factible gracias al teorema de convolución.

Para verificar la exactitud de los cálculos de una convolución lineal, cíclica o con la transformada de Fourier, puede calcular adicionalmente uno de los otros dos tipos de convolución, ya que las secuencias de salida deben ser iguales cuando las secuencias de entrada son las mismas.

Complejidad computacional

Calcular una convolución requiere operaciones. Este número se puede reducir significativamente calculando la convolución mediante varios algoritmos rápidos. $O(N^2)$

La mayoría de las veces, para reducir el número de operaciones, la convolución se calcula usando dos transformadas de Fourier, cada una de las cuales se calcula usando algoritmos rápidos . Esto reduce la complejidad computacional de la operación de convolución a . $O(N\log N)$

Reduciendo la dimensión del espacio con convolución multidimensional

Sean dos señales complejas discretas y dadas en el espacio . Definimos la convolución de estas señales como ${\ estilo de visualización \ mathbb {Z} ^ {n}}$ $F$ $gramo$ ${\ estilo de visualización y = f * g}$

y(k_{1},\ldots ,k_{n})=\sum \limits _{i_{1}=-\infty }^{+\infty }\ldots \sum \limits _{i_{ n}=-\infty }^{+\infty }f(i_{1},\ldots,i_{n})g(k_{1}-i_{1},\ldots,k_{n}-i_{ norte}).

Establezcamos también la operación de reducir la dimensión del espacio midiendo o sumando la señal como $yo_{j}$ $yo_{j}$

f[\mathbb {Z} ^{n}-i_{j}]=\sum \limits _{i_{j}=-\infty }^{+\infty }f(i_{1},\ ldots ,i_{n}),j\en 1...n.

Teorema. Para una dimensión arbitraria del espacio, el resultado de la convolución seguida de la sumatoria es , que es equivalente a la sumatoria preliminar de las señales y la subsiguiente convolución: . $yo_{j}$ ${\ estilo de visualización \ mathbb {Z} ^ {n}}$ ${\ estilo de visualización y = f * g}$ $yo_{j}$ $y[\mathbb {Z} ^{n}-i_{j}]$ $yo_{j}$ $F$ $gramo$ $y[\mathbb {Z} ^{n}-i_{j}]=f[\mathbb {Z} ^{n}-i_{j}]*g[\mathbb {Z} ^{n} -i_{j}]$ [una]

Ejemplo de programa

A continuación se muestra un ejemplo de implementación de convolución lineal, escrito en C++ :

/* * El tamaño de la secuencia de salida es M + N - 1 */ vector < doble > conv ( const vector < doble >& x , const vector < doble >& h ) { if (( x . tamaño () == 0 ) && ( h . tamaño () == 0 )) { vector de retorno < doble > (); } vector < doble > a ; vector < doble > b ; if ( x .tamaño () < h .tamaño ( ) ) { una = x _ segundo = h _ } más { un = h _ b = x ; } vector < doble > resultado ( a . tamaño () + b . tamaño () - 1 , 0 ); para ( tamaño_t k = 0 ; k < a . tamaño (); k ++ ) { para ( tamaño_t l = 0 ; l < b . tamaño (); l ++ ) { resultado [ l + k ] += a [ k ] * b [ l ]; } } resultado devuelto ; }

Véase también

Convolución Seccional

Notas

↑ Grishentsev A. Yu., Korobeinikov A. G. Reducción de la dimensión del espacio durante la correlación y convolución de señales digitales // Izv. universidades Instrumentación. : impreso. - 2016. - Nº 3 . - S. 211-218 . — ISSN 0021-3454 . Archivado desde el original el 12 de mayo de 2016.

Literatura

Rabiner L., Gould B. Capítulo 2. Teoría de sistemas lineales discretos // Teoría y aplicación del procesamiento digital de señales. - M. : Mir, 1978. - S. 72-81. — 848 pág.
Blahut R.Algoritmos rápidos de procesamiento de señales digitales. — M.: Mir , 1989.