Convolución discreta (convolución).

En muchos problemas prácticos es necesario calcular la convolución de dos secuencias finitas cuando una de ellas es mucho más larga que la otra (digamos, o). Por supuesto, siempre se puede elegir lo mismo, pero este enfoque es ineficaz y, por varias razones, inconveniente. Primero, necesitas tener toda la secuencia más larga antes de calcular la convolución. En la práctica, por ejemplo en el radar o en el procesamiento de señales de voz, esta condición no siempre es factible. En segundo lugar, dado que el procesamiento comienza sólo después de recibir la secuencia completa, el resultado se obtiene con un gran retraso. Y por último, si la DFT es demasiado grande, el cálculo de la DFT se vuelve mucho más complicado, ya que requiere de una gran cantidad de memoria y alguna otra parte puramente dificultades practicas relacionado con los algoritmos FFT. Los dos métodos siguientes para calcular la convolución no presentan estas desventajas. Se basan en dividir una secuencia más larga en secciones y calcular convoluciones parciales, a partir de las cuales se forma la secuencia de salida deseada.

El primero se llama método de suma de superposición. La esencia de este método se ilustra en la Fig. 2.32. Por simplicidad, asumimos que la secuencia no está limitada y contiene muestras. Dividamos la secuencia en secciones adyacentes con una longitud de muestras (figura 2.32). La elección es bastante difícil, pero Buenos resultados se obtienen si es una cantidad del mismo orden que . Entonces, la secuencia de entrada se representa en la forma.

(2.166)

Higo. 2.32. Método de superposición con sumatoria.

(2.167)

Convolución lineal de secuencias y es igual a

(2.168)

(2.169)

Higo. 2.33. Generar valores de salida de convolución utilizando el método de suma de superposición.

La longitud de cada una de las convoluciones parciales en la suma (2.169) es igual a las muestras, es decir, hay una sección con una longitud de muestras en la que la ésima y la ésima convolución parcial se superponen, por lo que sus muestras en la sección de superposición deben ser agregado. En la Fig. La figura 2.33 muestra cómo se organizan y suman las convoluciones parciales adyacentes. Cada uno de ellos se calcula mediante el método de convolución rápida descrito en la Sección. 2.24. El método considerado se llamó método de superposición con suma precisamente porque las circunvoluciones parciales intermedias se superponen y deben sumarse para obtener el resultado final.

Higo. 2.34. Método de superposición apilada.

Otro método para calcular la convolución lineal de secuencias, una de las cuales es mucho más larga que la otra, también se basa en dividir una secuencia más larga. Se llama método de superposición de apilamiento y en en este caso las secciones de entrada se superponen, no las secciones de salida. Se descartan muestras erróneas de convoluciones circulares de secciones individuales. Las muestras restantes se acumulan y a partir de ellas se forma el resultado final. Consideremos ejemplo específico(Figura 2.34). La secuencia contiene muestras y la secuencia se divide en secciones de longitud de muestra, superponiéndose entre sí en secciones de longitud de muestra. (Tenga en cuenta que la región de superposición está al final de la secuencia. Esto es conveniente para calcular la convolución circular usando DFT).

Departamento de FP

ABSTRACTO

disciplina: “Procesamiento de señales digitales”

sobre el tema: "Convolución lineal de secuencias deterministas"

Terminado:

Comprobado:

San Petersburgo, 2014

1. Introducción 3

2. Convolución lineal 4

3. Convolución cíclica 5

4. Circunvoluciones seccionadas 7

5. Literatura 11

Introducción

Operación de convolución:

s(t) = x(t) * h(t) = (1)

En el caso discreto se distinguen dos tipos de convolución: lineal (o aperiódica) y cíclica. La convolución cíclica también suele denominarse circular o periódica.

convolución lineal

Consideremos la convolución lineal. Sean dos señales discretas a(n), n=0..N-1 y b(n), n=0..M-1. EN caso general Las longitudes de estas señales N y M pueden diferir. La convolución lineal de señales a(n) y b(n) es una señal discreta de la forma:

s(n) = a*b = (2)

Para calcular la convolución lineal, las señales a(n) y b(n) se desplazan entre sí, se multiplican y se suman por términos. Se supone que a(n) = 0 para n<0 и n>N, así como b(n)=0 para n<0 и n>METRO

En la Figura 1 se muestra una representación gráfica de la convolución lineal.

Foto 1: Representación grafica convolución lineal

Las muestras de señal b(n) se desplazan con respecto a las muestras de secuencia a(n); todas las posibles muestras superpuestas se multiplican y suman término por término.

La Figura 2 muestra un ejemplo de cálculo de la convolución lineal de dos señales a(n) = 4 muestras de longitud y b(n)=[-1,1,2] 3 muestras de longitud.

Figura 2: Ejemplo de cálculo de convolución lineal.

Cabe señalar que la señal b(n) al calcular la convolución se refleja de izquierda a derecha, ya que b(0)=-1 es la primera muestra (la más temprana en el tiempo) y también debe procesarse primero.

convolución cíclica

Consideremos ahora la convolución cíclica. En el caso de convolución cíclica se supone que señales discretas a(n) y b(n) son periódicos con el mismo período de N muestras. Entonces la convolución circular de las señales a(n) y b(n) es una señal de la forma:

s(norte) = (3)

El resultado de la convolución cíclica también tiene una longitud de N muestras.

Consideremos la convolución cíclica usando el ejemplo de dos señales a(n)= y b(n)=[-1,3,2,1] . Gráficamente, el cálculo de la convolución cíclica se presenta en la Figura 3.

Figura 3: Cálculo de convolución cíclica

La línea roja marca los límites de los períodos de repetición de la señal b(n-m). Tenga en cuenta que debido a la periodicidad de las señales, b(-m)=b(N-m).

Calculemos la convolución paso a paso:

Ahora calculemos s(1):

Demos un ejemplo de cálculo de una convolución lineal a través de una cíclica para a(n)= con una longitud de 4 muestras y b(n)=[-1,1,2] con una longitud de 3 muestras (este ejemplo fue discutido arriba).

Agreguemos ceros a a(n)= y b(n)=[-1,1,2,0,0,0], de modo que haya 6 muestras en cada secuencia.

Calculemos la convolución cíclica como se muestra en la Figura 4.

Figura 4: Cálculo de la convolución lineal mediante cíclico<

Puede compararlo con el resultado del primer ejemplo de convolución lineal y asegurarse de que los valores sean los mismos.

circunvoluciones seccionadas

convolución seccional se utiliza cuando el número de elementos de una de las secuencias es varias veces mayor que el número de elementos de la otra. La convolución seccional se puede realizar mediante dos métodos de cálculo. Se basan en dividir una secuencia más larga en secciones y calcular convoluciones parciales, a partir de las cuales se forma la secuencia de salida deseada.

El primero se llama método de suma de superposición. La esencia de este método se ilustra en la Fig. 5. Por simplicidad, suponemos que la secuencia x(n) no está limitada y que h(n) contiene muestras. Dividamos la secuencia x (n) en secciones adyacentes con una longitud de muestras (Fig. 5). La elección es bastante complicada, pero se obtienen buenos resultados si es una cantidad del mismo orden que . Entonces, la secuencia de entrada x(n) se representa como.

Fig.5. - Método de superposición con sumatoria.

La convolución lineal de las secuencias x(n) y h(n) es igual a

Fig.6. - Formación de valores de salida de convolución mediante el método de superposición con sumatoria.

La longitud de cada una de las convoluciones parciales en la suma (4) es igual a () muestras, es decir, hay una sección de longitud () muestras en la que las convoluciones parciales k-ésima y (k+1)-ésima se superponen, por lo que sus muestras están en la sección de superposición que debe doblarse. En la Fig. La Figura 6 muestra cómo se organizan y suman las convoluciones parciales adyacentes. El método considerado se llamó método de superposición con suma precisamente porque las circunvoluciones parciales intermedias se superponen y deben sumarse para obtener el resultado final.

Fig.7-. Método de superposición apilada.

Otro método para calcular la convolución lineal de secuencias, una de las cuales es mucho más larga que la otra, también se basa en dividir una secuencia más larga. Se denomina método de superposición apilada y, en este caso, se superponen las secciones de entrada, no las secciones de salida. Se descartan muestras erróneas de convoluciones circulares de secciones individuales. Las muestras restantes se acumulan y a partir de ellas se forma el resultado final. Consideremos un ejemplo específico (Fig. 7). La secuencia h (n) contiene muestras, y la secuencia x (n) se divide en secciones de longitud () muestras, superpuestas entre sí en secciones de longitud () muestras. (Tenga en cuenta que la región de superposición está al final de la secuencia. Esto es conveniente para calcular la convolución circular usando DFT).

arroz. 8.- Formación de valores de salida de convolución mediante el método de superposición apilada.

Para cada sección, se calcula una convolución circular de las secuencias h(n) y , que contienen () la muestra. El resultado es un conjunto de secuencias que se muestran en la Fig. 8. Las últimas () muestras de cada una de las secuencias se descartan (son incorrectas debido a la naturaleza cíclica de la convolución), y el resto se agrega a las muestras correctas de la secuencia, etc. El resultado es la secuencia deseada, idéntica a la convolución y(n). Entonces, usando el método de suma de superposición o el método de apilamiento de superposición, es relativamente fácil encontrar la convolución de una secuencia corta y una muy larga, y el resultado se obtiene en forma de pequeñas secciones separadas que se combinan en consecuencia en una secuencia. .

Literatura

1. Procesamiento digital de señales de imágenes: libro de texto. subsidio / S.M. ibatulín; Universidad Electrotécnica Estatal de San Petersburgo que lleva el nombre. Y EN. Ulyanov (Lenin) "LETI". - San Petersburgo. : Editorial de la Universidad Electrotécnica de San Petersburgo "LETI", 2006.

2. Procesamiento de señales digitales: libro de texto. manual para universidades / A.B. Sergienko; - San Petersburgo. : Pedro, 2002.

3. Algoritmos y procesadores de procesamiento de señales digitales: Libro de texto. manual para universidades / A. I. Solonina, D. A. Ulakhovich, L. A. Yakovlev. - San Petersburgo. : BHV-Petersburgo, 2001.

4. Procesamiento de señales digitales = Comprensión del procesamiento de señales digitales / R. Lyons; carril De inglés editado por A. A. Britova. - 2ª ed. - M.: Binom, 2007.

En la sección anterior se demostró que la complejidad de las operaciones aritméticas al implementar filtros FIR usando DFT no depende del orden del filtro, mientras que la complejidad de la implementación con calculo directo la convolución es proporcional al orden del filtro. Si el orden de los filtros es bajo, se esperaría que la implementación de convolución directa fuera más eficiente, pero a medida que aumenta el orden de los filtros, la implementación de DFT eventualmente se volverá más eficiente. Para filtros de orden muy alto, la ganancia puede alcanzar decenas y cientos de veces.

Por otro lado, la implementación de DFT requiere cantidades importantes de memoria. Los métodos de partición convolucional son una solución de compromiso. Su esencia radica en el hecho de que la operación de convolución se realiza en secciones o bloques de datos utilizando DFT. Limitar el tamaño de las secciones reduce la cantidad de memoria requerida y el uso de DFT mantiene la eficiencia computacional del procedimiento.

El método de convolución particionada más sencillo de entender se llama método de suma de superposición. Dividamos la matriz bidimensional en secciones de puntos, definiendo la sección con índices de la siguiente manera:

El área de soporte para una de esas secciones se muestra en la Fig. 3.1,a. Las áreas de soporte de las secciones no se superponen y juntas cubren toda el área de soporte de la matriz, por lo que

. (3.13)

Arroz. 3.1. Método de superposición con sumatoria.

a - sección de la secuencia de entrada; b - área de soporte del resultado de la convolución de esta sección con .

Debido a que la operación convolución discreta distributivo con respecto a la suma, podemos escribir

(3.14)

La sección de salida es el resultado de la convolución con la sección de secuencia. Estos resultados parciales deben sumarse para obtener el resultado completo del filtro. Dado que el área de referencia de la sección es mayor que el área de referencia de la sección, las secciones de salida deben superponerse, aunque el grado de superposición es limitado. En la Fig. 3.1b muestra dicho área de soporte de una de las secciones de salida.

Las convoluciones se pueden calcular utilizando transformadas discretas de Fourier, siempre que el tamaño de la transformada sea lo suficientemente grande como para proporcionar una región de soporte. Al controlar el tamaño de las secciones, limitamos el tamaño del DFT, reduciendo la cantidad de memoria requerida. Sin embargo, en la práctica esto va acompañado de cierta pérdida de eficiencia.

Otra variación de la convolución particionada es el método de superposición apilada. Mirando de nuevo a la Fig. 3.1, se puede observar que si el tamaño de la sección excede significativamente el tamaño del área de referencia de respuesta, entonces las muestras en el centro de cada sección no se superponen con las muestras de las secciones vecinas. De manera similar, cuando una secuencia se convoluciona cíclicamente con otra secuencia que tiene un área de referencia mucho más pequeña, solo una parte de las muestras de convolución cíclica experimentarán aliasing espacial. Las muestras restantes serán idénticas a las muestras de convolución lineal. La ubicación de estas lecturas se muestra en la Fig. 3.2. Por lo tanto, si realiza una convolución cíclica de una sección de puntos de una secuencia con una respuesta de impulso de puntos utilizando DFT de puntos, el resultado de esta convolución contendrá una región que consta de muestras idénticas a las muestras de la convolución lineal. La matriz de salida completa se puede componer de estas "buenas" muestras eligiendo adecuadamente las áreas de referencia de las secciones de entrada. Si las secciones de entrada se superponen, es posible garantizar que las áreas "buenas" de las secciones adyacentes sean adyacentes entre sí. Por lo tanto, el método de superposición apilada requiere que las secciones de entrada se superpongan, mientras que el método de superposición apilada requiere que las secciones de salida se superpongan.

Arroz. 3.2. Método de superposición apilada. El área sombreada contiene muestras para las cuales la convolución cíclica con período y la convolución lineal dan resultados idénticos.

Tanto para los procedimientos de superposición de suma como de acumulación, la elección de los tamaños de partición influye en gran medida en la eficiencia de la implementación. En primer lugar, esta elección afecta obviamente a la cantidad de memoria necesaria, así como a la cantidad de cálculos. De la Fig. 3.2 se puede ver que la proporción de muestras útiles de convolución cíclica aumenta a medida que aumenta el tamaño de la sección en relación con el tamaño de la respuesta al impulso. Aunque es difícil hacer afirmaciones generales sobre el tamaño de las secciones de entrada porque los resultados son muy específicos de la computadora, los experimentos de Toogood et al han demostrado que los filtros con tamaños de área de referencia que van desde hasta muestras requieren un tamaño de sección de . Esto es demasiado para la mayoría de las minicomputadoras. Por tanto, resulta que el rendimiento del algoritmo está limitado por la memoria disponible. Si este es el caso, entonces deberías seleccionar secciones de entrada del mayor tamaño posible.

La convolución es un proceso fundamental en el procesamiento de señales digitales. Por tanto, es importante poder calcularlo de forma eficaz.

Ecuación de convolución discreta Se pueden obtener dos funciones (señales) directamente de la ecuación de convolución integral reemplazando la integración sumando los valores instantáneos de las funciones con un paso Dt:

y(kDt) = Dth(nDt) s(kDt-nDt). (8.11)

Al realizar una convolución discreta, estamos tratando con matrices digitales, y el paso de muestreo para matrices según el argumento físico de la convolución debe ser igual y tomarse como 1, y la numeración de muestras en las matrices se utiliza como argumento:

y(k) =h(n) s(k-n) ºh n s k-n º y k . (8,11")

y(k) = h(n) * s(k-n) º s(k) * h(n) º s k * h n .

técnica de convolución mostrado en la Fig. 8.8. Para calcular la convolución, la matriz de una de las funciones (s k - señal de entrada) se ubica en orden de números crecientes. La matriz de la segunda función (h n - operador de convolución más corto) se construye paralela a la primera matriz en orden inverso(a medida que los números disminuyen, en modo de tiempo inverso). Para calcular y k, el valor de h 0 se ubica frente a s k, todos los valores de s k-n se multiplican por los valores de h n ubicados frente a ellos y se suman. Los resultados de la suma son el valor de salida de la función y k, después de lo cual el operador h n se desplaza hacia adelante un número k (o la función s k se desplaza hacia él) y el cálculo se repite para el número k+1, etc.

Arroz. 8.8. Técnica de convolución discreta

EN momento inicial convolución al calcular los valores y k el operador h n , construido en modo de tiempo inverso, se “congela” durante valores kn para n>k contra muestras faltantes de la función de entrada. El "colgado" se elimina estableciendo condiciones iniciales: muestras adicionales, generalmente cero o igual a la primera muestra de la función de entrada, o iniciando la convolución desde la muestra de función de entrada k = n con la correspondiente reducción en el intervalo de salida. función. Para operadores con valores -n (hacia adelante en el tiempo), el mismo momento puede ocurrir al final de la matriz de entrada.

Ejemplo. Ecuación de convolución: y k =b n x k-n = b o x k + b 1 x k-1 + b 2 x k-2 .

Los valores del operador bn son: b o = 5, b 1 = 3, b 2 = 2.

Señal de entrada: x k = (0,1,0,0,0), condiciones iniciales: x-n = 0.

Cálculo de la señal de salida:

y o = 5x o + 3x -1 + 2 x -2 = 5 0 + 3 0 + 2 0 = 0, y 1 = 5x 1 + 3x o + 2x -1 = 5 1 + 3 0 + 2 · 0 = 5,

y 2 = 5x 2 + 3x 1 + 2x o = 5 0 + 3 1 + 2 0 = 3, y 3 = 5x 3 + 3x 2 + 2x 1 = 5 0 + 3 0 + 2 1 = 2,

y 4 = 5x 4 + 3x 3 + 2x 2 = 5 0 + 3 0 + 2 0 = 0, y 5 = 5x 5 + 3x 4 + 2x 3 = 5 0 + 3 0 + 2 0 = 0

Señal de salida: yk = (0, 5, 3, 2, 0)

Nota: La convolución de una función de operador con una única señal de entrada es una repetición de la función de operador de convolución en la salida.

En la Fig. La Figura 8.9 muestra un ejemplo de cómo realizar una convolución discreta con un operador causal (unidireccional) y uno par (simétrico, bidireccional) en la misma señal.

Arroz. 8.9. Ejemplos de realización de convolución discreta

Cálculo directo la convolución requiere K·N multiplicaciones, donde K es la longitud de la señal original y N es la longitud del núcleo de convolución. Tanto la longitud de la señal como la longitud del núcleo de convolución pueden alcanzar varios miles de puntos y el número de multiplicaciones se vuelve enorme.

Para convolución discreta, todas las propiedades y teoremas de convolución integral son válidos. En particular, la convolución de funciones en el dominio de coordenadas está representada por el producto de sus espectros en el dominio de frecuencia, y la multiplicación en el dominio de coordenadas es equivalente a la convolución en el dominio de frecuencia. Esto significa que para realizar la convolución de dos señales, puede convertirlas en dominio de la frecuencia, multiplique sus espectros y convierta el resultado nuevamente al dominio del tiempo, es decir proceder de acuerdo al siguiente esquema:

s(k) Û S(w), h(n) Û H(w), Y(w) = S(w)×H(w), Y(w) Û y(k).

Con la llegada de los algoritmos FFT que pueden calcular rápidamente las transformadas de Fourier, el cálculo de la convolución a través del dominio de la frecuencia se ha utilizado ampliamente. En tamaño significativo señales y la longitud del núcleo de convolución, este enfoque hace posible reducir el tiempo de cálculo de la convolución cientos de veces.

El producto de los espectros sólo se puede realizar si tienen la misma longitud, y el operador h(n) antes de la DFT debe rellenarse con ceros hasta el tamaño de la función s(k).

El segundo factor que se debe tener en cuenta es la ciclicidad de la convolución cuando se realiza en región espectral, debido a la periodización funciones discretas. Los espectros que se multiplican son los espectros. funciones periódicas, y el resultado en los intervalos finales puede no coincidir con la convolución lineal discreta, donde las condiciones para extender los intervalos (condiciones iniciales) se especifican en lugar de repetirse. periodo principal.

En la Fig. La Figura 8.10 muestra los resultados de la convolución de la señal s k , especificada en el intervalo k=(0-50), con la función h n = a×exp(-a×n), a = 0,1. La convolución realizada mediante DFT en el lado izquierdo del intervalo difiere marcadamente de la convolución lineal. La naturaleza de la distorsión queda clara si complementamos el intervalo principal del lado izquierdo con su continuación periódica (la figura muestra una parte del período del lado izquierdo, cuya convolución ingresa al período principal). Para los operadores h n con valores n adelante en posición, aparecerán distorsiones similares en el lado derecho del período principal. Para eliminar tales distorsiones, la función de señal debe ampliarse en ceros por el tamaño del operador h(n), lo que eliminará la superposición de períodos laterales de la traza principal de la función.

Arroz. 8.10. Resultados de dos tipos de convolución.

Al realizar convolución a través de FFT, aparece un aumento notable en la velocidad de cálculo solo cuando distancia larga funciones y operadores (por ejemplo, M>1000, N>100). También debes prestar atención a la profundidad de bits de los resultados, porque multiplicar números da un aumento del doble en la profundidad de bits. Con un número limitado de dígitos y un redondeo adecuado, esto puede provocar errores de suma.

En los sistemas de procesamiento de datos en línea, a menudo existe la necesidad de calcular la convolución de una señal que llega a la entrada del sistema en porciones sucesivas (por ejemplo, desde sensores de instrumentos de fondo de pozo). En tales casos se aplica convolución seccional. Su esencia es que cada una de estas partes se dobla con el núcleo por separado y las partes resultantes se combinan. Para combinar, basta con colocarlos uno tras otro con una superposición de N-1 puntos (N es la longitud del núcleo de convolución) y realizar la suma en los puntos de superposición.

convolución seccional

Para implementar este tipo de convolución, debe hacer lo siguiente:

1. divida una secuencia grande en secciones, es deseable que cada sección tenga la misma cantidad de elementos;

2. cuente el número de valores de la secuencia de salida parcial (POS) usando la fórmula:

N chwp =N s +N-1 donde N chwp es el número de valores en la secuencia de salida parcial; Nс - cantidad: valor en esta sección; N - número de valores en la segunda secuencia.

3. convolucionar cada sección de la primera secuencia con la segunda secuencia. El número de convoluciones debe coincidir con el número de secciones de la primera secuencia.

Para la convolución seccional que utiliza el método de superposición con suma, se pueden utilizar los siguientes tipos de convolución:

lineal;
circular sin superposición circular (aperiódico);
convolución mediante transformada discreta de Fourier.

4. ensamblar la secuencia de salida a partir de secuencias de salida parciales.

Para la convolución de superposición seccional, solo se utiliza convolución circular. Para la convolución seccional utilizando el método de superposición con suma, el ensamblaje se realiza de la siguiente manera: en el segmento de (N-1) a N chvp, sume los valores de las secciones 1 y 2 a las secciones Z-1 y Z (donde Z es el número de secciones). Y para convolución seccional usando el método de superposición y acumulación: últimos valores en el segmento (N - 1) a N se deben descartar los chvp, es decir, no se tienen en cuenta al armar la secuencia de salida, y así sucesivamente desde la sección 1 hasta la sección Z-1.

Fundación Wikimedia. 2010.

Sekhukhune
puertas seccionales

Vea qué es "convolución seccional" en otros diccionarios:

Convolución de secuencia es el resultado de multiplicar los elementos de dos dados secuencias numéricas de tal manera que los miembros de una secuencia se toman con índices crecientes y los miembros de la otra con índices decrecientes (que sirve de base para el nombre adoptado de esta ... ... Wikipedia

Procesamiento de señales digitales- (DSP, procesamiento de señales digitales en inglés DSP) conversión de señales presentadas en formulario digital. Cualquier señal continua (analógica) puede someterse a muestreo de tiempo y cuantificación de nivel (digitalización), entonces... ... Wikipedia

Pandeo- así se llama la operación preparatoria en el tejido, destinada a preparar la urdimbre (ver). Consiste, en términos generales, en que el número de hilos necesarios para la urdimbre se rebobina de bobinas individuales en un gran eje común, llamado... ... diccionario enciclopédico F. Brockhaus y I.A. Efrón