Voltear la respuesta al impulso en convolución

26

Durante la convolución en una señal, ¿por qué necesitamos voltear la respuesta al impulso durante el proceso?

winuall
fuente
55
La última mitad de esta respuesta podría ayudarlo a comprender.
Dilip Sarwate
3
Además de leer la excelente respuesta de @ DilipSarwate, es un buen ejercicio tomar una hoja de papel y calcular la salida de un sistema LTI gráficamente sumando versiones de la respuesta al impulso desplazadas en el tiempo y escaladas.
Deve
1
Tenga en cuenta que puede voltear cualquier argumento: el resultado es el mismo.
wakjah

Respuestas:

29

Adaptado de una respuesta a una pregunta diferente (como se menciona en un comentario) con la esperanza de que esta pregunta no sea planteada repetidamente por Community Wiki como una de las preguntas principales ...

No hay "volteo" de la respuesta al impulso por un sistema lineal (invariante en el tiempo). La salida de un sistema lineal invariante en el tiempo es la suma de versiones escaladas y retardadas en el tiempo de la respuesta al impulso, no la respuesta al impulso "invertida".

Desglosamos la señal de entrada x en una suma de señales de pulso de unidad escalada. La respuesta del sistema a la señal de pulso de la unidad , 0, 0, 1, 0, 0, es la respuesta al impulso o la respuesta al pulso

h[0], h[1],, h[n],
y así propiedad de escala el valor de entrada único x[0], o, si prefiere
x[0](, 0, 0, 1, 0, 0,)= 0, 0, x[0], 0, 0,
crea una respuesta
x[0]h[0],  x[0]h[1],,  x[0]h[n],

Del mismo modo, el valor de entrada único o crea x [ 1 ] ( , 0 , 0 , 0 , 1 , 0 , ) = 0 , 0 , 0 , x [ 1 ] , 0 , crea una respuesta 0 , x [ 1 ] h [ 0 ] , x [ 1x[1]

x[1](, 0, 0, 0, 1, 0,)= 0, 0, 0, x[1], 0,
Observe el retraso en la respuesta a x [ 1 ] . Podemos continuar más en este sentido, pero es mejor cambiar a una forma más tabular y mostrar las distintas salidas alineadas correctamente en el tiempo. Tenemos tiempo 0 1 2 n n + 1 x [
0,x[1]h[0],  x[1]h[1],,  x[1]h[n1],x[1]h[n]
x[1] Las filas en la matriz anterior son precisamente las versiones escaladas y retrasadas de la respuesta de impulso que se suman a la respuestaya la señal de entradax. Pero si haces una pregunta más específica como
time012nn+1x[0]x[0]h[0]x[0]h[1]x[0]h[2]x[0]h[n]x[0]h[n+1]x[1]0x[1]h[0]x[1]h[1]x[1]h[n1]x[1]h[n]x[2]00x[2]h[0]x[2]h[n2]x[2]h[n1]x[m]000x[m]h[nm]x[m]h[nm+1]
yx

¿Cuál es la salida en el tiempo ?n

n

y[n]=x[0]h[n]+x[1]h[n1]+x[2]h[n2]++x[m]h[nm]+=m=0x[m]h[nm],
y[n]=x[n]h[0]+x[n1]h[1]+x[n2]h[2]++x[0]h[n]+=m=0x[nm]h[m],
n
Dilip Sarwate
fuente
4

Aquí hay un ejemplo de C / C ++ que muestra que la convolución se puede hacer sin usar la respuesta de impulso en reversa. Si inspecciona la convolve_scatter()función, no se niega ninguna variable en ninguna parte. Esta es una convolución de dispersión donde cada muestra de entrada se dispersa (suma) a múltiples muestras de salida en la memoria, utilizando pesos dados por la respuesta al impulso. Esto es un desperdicio porque las muestras de salida deberán leerse y escribirse varias veces.

Normalmente, la convolución se realiza como convolución de reunión , como en convolve_gather(). En este método, cada muestra de salida se forma por separado, reuniendo (sumando) muestras de entrada, con la respuesta de impulso invertida como los pesos. La muestra de salida reside en el registro de un procesador utilizado como acumulador mientras se hace esto. Normalmente, este es el método de elección, porque solo habrá una escritura de memoria por cada muestra filtrada. Ahora hay más lecturas de memoria de la entrada, pero solo tantas como lecturas de memoria de la salida en el método de dispersión.

#include <stdio.h>

const int Nx = 5; 
const int x[Nx] = {1, 0, 0, 0, 2};
const int Ny = 3; 
const int y[Ny] = {1, 2, 3};
const int Nz = Nx+Ny-1;
int z[Nz];

void convolve_scatter() { // z = x conv y
  for (int k = 0; k < Nz; k++) {
    z[k] = 0;
  }
  for (int n = 0; n < Nx; n++) {
    for (int m = 0; m < Ny; m++) {
      z[n+m] += x[n]*y[m]; // No IR reversal
    }
  }
}

void convolve_gather() { // z = x conv y
  for (int k = 0; k < Nz; k++) {
    int accu = 0;
    for (int m = 0; m < Ny; m++) {
      int n = k+m - Ny + 1;
      if (n >= 0 && n < Nx) {
        accu += x[n]*y[Ny-m-1]; // IR reversed here
      }
    }
    z[k] = accu;
  }
}

void print() {
  for (int k = 0; k < Nz; k++) {
    printf("%d ", z[k]);
  }
  printf("\n");
}

int main() {
  convolve_scatter();
  print();
  convolve_gather();
  print();
}

Convoluciona las secuencias:

1 0 0 0 2
1 2 3

y usando ambos métodos de convolución salidas:

1 2 3 0 2 4 6

No puedo imaginar a nadie usando el método de dispersión, a menos que el filtro varíe en el tiempo, en cuyo caso los dos métodos producirán resultados diferentes y uno puede ser más apropiado.

Olli Niemitalo
fuente
¡Interesante! Entonces, ¿cuál es la conclusión final que me interesa ver
Científico fallido
Su interés arquitectónico es interesante. Teniendo en cuenta los cachés disponibles, las instrucciones SIMD (SSE, AVX) y las arquitecturas multinúcleo, ¿el método disperso parece más adecuado para cálculos paralelos? Sin embargo, no he realizado un análisis detallado ...
Fat32
@ Fat32 yo tampoco! ¿Quiere decir que la acumulación en la convolución puede convertirse en un cuello de botella con múltiples núcleos trabajando en multiplicaciones? Eso podría mitigarse dando a cada núcleo su propio acumulador y sumándolos al final. Creo que esta sobrecarga no sería mucho en comparación con las escrituras de memoria adicionales en convolución dispersa.
Olli Niemitalo
En realidad, estaba más preocupado por la eficiencia del formulario disperso que por el cuello de botella de los formularios de recopilación. Mis códigos de filtrado C actuales están (muy probablemente) en el formulario de recopilación, pero cuando se trata de códigos ASM tiendo a escribirlos en extensiones SIMD SSE que son más Adecuado para forma dispersa. Sin embargo, tengo que actualizar mis tiendas :-))) La memoria IO es definitivamente un problema en comparación con la acumulación de registros. Y probablemente me estoy perdiendo la pena de memoria repetida IO ...
Fat32
¿Alguien sabe mejores palabras que dispersarse y reunirse? No estoy seguro de si están reservados para núcleos de convolución dispersos.
Olli Niemitalo
3

Solo se 'voltea' para el cálculo puntual.

@Dilip explica lo que representa la integral / suma de convolución, pero para explicar por qué una de las dos funciones de entrada (a menudo h(t)) se invierte para fines de cálculo, considere un sistema de tiempo discreto con entrada x[n]y respuesta de impulso h[n]:

  • Puede tomar su función de entrada x[n], y para cada muestra que no sea cero * x[n]calcule la respuesta de impulso escalada de la muestra ny así sucesivamente hasta que el cambio de tiempo se h[n]reduzca a cero (suponiendo un causal h[n]). Esto implicaría no 'voltear' (o más exactamente 'inversión de tiempo') de cualquiera x[n]o h[n]. Sin embargo, al final tendría que agregar / superponer todos estos 'ecos' escalados + desplazados de la respuesta de impulso para cada no-cero x[n].

  • x[0]k

    k=x[k]h[nk]
    h[n]x[n], Que es x[0]h[0]. Luego, kal aumentar en uno, se desplazará h[n]hacia la derecha un paso de tiempo, de modo que la h[n]segunda entrada ( h[1]) de tiempo invertido ahora se colocará encima x[0], esperando ser multiplicada. Esto producirá la contribución deseada x[0]h[1]en el momento n=1, tal como se habría hecho en el método anterior.

x[n]

x[n]=0
h[n]y[n]
a B C
fuente
n
@Dilip. Todos n son iguales, excepto 'h [n] desplazado en el tiempo', que implica 'h [nk]', donde 'k' es una constante utilizada para desplazar la respuesta al impulso al punto deseado de la señal x [n ] es decir: h [n-2] para calcular la respuesta a la señal en x [2].
abc
3

En el índice c [n], la convolución de a [n] yb [n] es tal que:

"c [n] es una suma de todos los productos (a [k] b [m]) tal que m + k = n", entonces m = n - k o k = n - m, lo que significa que una de las secuencias tiene que ser volteado.

Ahora, ¿por qué la convolución se comporta de esta manera en primer lugar? Debido a su conexión con la multiplicación de polinomios.

Multiplicar dos polinomios da como resultado un nuevo polinomio con coeficientes. Los coeficientes del polinomio del producto definen el funcionamiento de la convolución. Ahora, en el procesamiento de señales, las funciones de transferencia: las transformadas de Laplace o las transformadas z son estos polinomios, y cada coeficiente corresponde a un retardo de tiempo diferente. Unir los coeficientes del producto y los multiplicandos da como resultado el hecho de que "la multiplicación en una representación corresponde a la convolución en la representación transformada".

ingrese la descripción de la imagen aquí

Mahesh Shastry
fuente
0

Durante la convolución, no debe producirse ningún "giro" de la respuesta al impulso ...

Sin embargo, si desea evitar cualquier alteración de fase, puede convolucionar una señal con una respuesta de impulso y luego revertir la respuesta de impulso y volver a convolucionar para cancelar los efectos de fase.

En el procesamiento fuera de línea, podría revertir la señal con la misma facilidad después de la primera convolución para llegar a la misma conclusión (como sugieren los comentarios).

aprender
fuente
3
y(t)=x(τ)h(tτ)dτh(t)x(t)h(t)=h(t)x(t)
@JasonR Ah, ¡vaya! A veces es difícil ver a qué se dirige la pregunta. Izhak, una vez que entiendas la respuesta que estabas buscando, entenderás a dónde iba. ¡Ignórame por ahora!
learnvst
0

f(τ)g(tτ)dτ
t1+t2=tf(t1)g(t2)dt1dt2
fgt

t1,t2f(t1)g(t2)δ(tt1t2)dt1dt2
t1f(t1)dt1t2g(t2)δ(tt1t2)dt2
t1f(t1)dt1g(tt1)

fuente