Inverser la réponse impulsionnelle en convolution

26

Pendant la convolution sur un signal, pourquoi devons-nous inverser la réponse impulsionnelle pendant le processus?

winuall
la source
5
La seconde moitié de cette réponse pourrait vous aider à comprendre.
Dilip Sarwate
3
En plus de lire la grande réponse de @ DilipSarwate, c'est un bon exercice de prendre une feuille de papier et de calculer graphiquement la sortie d'un système LTI en ajoutant des versions décalées dans le temps et à l'échelle de la réponse impulsionnelle.
Deve
1
Notez que vous pouvez inverser l'un ou l'autre argument - le résultat est le même.
wakjah

Réponses:

29

Adapté d'une réponse à une question différente (comme mentionné dans un commentaire) dans l'espoir que cette question ne sera pas soulevée à plusieurs reprises par Community Wiki comme l'une des principales questions ....

Il n'y a pas de "retournement" de la réponse impulsionnelle par un système linéaire (invariant dans le temps). La sortie d'un système linéaire invariant dans le temps est la somme des versions échelonnées et temporisées de la réponse impulsionnelle, et non la réponse impulsionnelle "inversée".

Nous décomposons le signal d'entrée en une somme de signaux d'impulsions unitaires mis à l'échelle. La réponse du système au signal impulsionnel unitaire est la réponse impulsionnelle ou la réponse impulsionnelle et ainsi par la propriété de mise à l'échelle la valeur d'entrée unique , ou, si vous préférez crée une réponse X, 0, 0, 1, 0, 0,

h[0], h[1],, h[n],
x [ 0 ] ( , 0 , 0 , 1 , 0 , 0 , ) = 0 , 0 , x [ 0 ] , 0 , 0 , x [ 0 ] h [ 0 ] , x [ 0 ] h [ 1 ] , , x [X[0]
x[0](, 0, 0, 1, 0, 0,)= 0, 0, x[0], 0, 0,
x[0]h[0],  x[0]h[1],,  x[0]h[n],

De même, la valeur d'entrée unique ou crée crée une réponse Notez le retard dans la réponse à . Nous pouvons continuer plus loin dans cette veine, mais il est préférable de passer à une forme plus tabulaire et d'afficher les différentes sorties correctement alignées dans le temps. On a x [ 1 ] ( , 0 , 0 , 0 , 1 , 0 , ) = 0 , 0 , 0 , x [ 1 ] , 0 , 0 , x [ 1 ] h [ 0 ] , x [ 1 ] h [ 1 ] , ,X[1]

X[1](, 0, 0, 0, 1, 0,)= 0, 0, 0, X[1], 0,
x [ 1 ] temps 0 1 2 n n + 1 x [ 0 ] x [ 0 ] h [ 0 ] x [ 0 ] h [ 1 ] x [ 0 ] h [
0,X[1]h[0],  X[1]h[1],,  X[1]h[n-1],X[1]h[n]
X[1]
temps012nn+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[n-1]X[1]h[n]X[2]00X[2]h[0]X[2]h[n-2]X[2]h[n-1]X[m]000X[m]h[n-m]X[m]h[n-m+1]
\ ddots \ end {array} Les lignes du tableau ci-dessus sont précisément les versions échelonnées et retardées de la réponse impulsionnelle qui s'ajoutent à la réponse pour entrer le signal . yX Mais si vous posez une question plus spécifique telle que

Quelle est la sortie au temps ?n

alors vous pouvez obtenir la réponse en additionnant la -ième colonne pour obtenir la formule de convolution bien-aimée qui embrouille des générations d'étudiants parce que la réponse impulsionnelle semble être "retournée" ou reculée dans le temps. Mais, ce que les gens semblent oublier, c'est qu'au lieu de cela, nous aurions pu écrire pour que ce soit l' entrée qui semble "retournée" ou qui recule dans le temps! En d'autres termes, ce sont les êtres humainsn

y[n]=X[0]h[n]+X[1]h[n-1]+X[2]h[n-2]++X[m]h[n-m]+=m=0X[m]h[n-m],
y[n]=X[n]h[0]+X[n-1]h[1]+X[n-2]h[2]++X[0]h[n]+=m=0X[n-m]h[m],
qui inversent la réponse impulsionnelle (ou l'entrée) lors du calcul de la réponse au temps utilisant la formule de convolution, mais le système lui-même ne fait rien de tel.n
Dilip Sarwate
la source
4

Voici un exemple C / C ++ qui montre que la convolution peut être effectuée sans utiliser la réponse impulsionnelle à l'envers. Si vous inspectez la convolve_scatter()fonction, aucune variable n'est nulle part. Il s'agit d'une convolution de diffusion où chaque échantillon d'entrée est diffusé (additionné) à plusieurs échantillons de sortie en mémoire, en utilisant des poids donnés par la réponse impulsionnelle. C'est un gaspillage car les échantillons de sortie devront être lus et écrits plusieurs fois.

Normalement, la convolution se fait en rassemblant la convolution, comme dans convolve_gather(). Dans cette méthode, chaque échantillon de sortie est formé séparément, en rassemblant (sommant) des échantillons d'entrée, avec la réponse impulsionnelle inversée comme poids. L'échantillon de sortie réside dans le registre d'un processeur utilisé comme accumulateur pendant que cela est fait. C'est normalement la méthode de choix, car il n'y aura qu'une seule écriture en mémoire pour chaque échantillon filtré. Il y a maintenant plus de lectures en mémoire de l'entrée, mais seulement autant qu'il y a eu de lectures en mémoire de la sortie dans la méthode de diffusion.

#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();
}

Il convole les séquences:

1 0 0 0 2
1 2 3

et en utilisant les deux méthodes de convolution sorties:

1 2 3 0 2 4 6

Je ne peux pas imaginer que quiconque utilise la méthode de diffusion, sauf si le filtre varie dans le temps, auquel cas les deux méthodes produiront des résultats différents et l'une peut être plus appropriée.

Olli Niemitalo
la source
Intéressant! Alors quelle est la conclusion finale que je suis intéressé de voir
Scientifique
Votre souci architectural est intéressant. Compte tenu des caches disponibles, des instructions SIMD (SSE, AVX) et des architectures multicœurs, la méthode dispersée semble-t-elle plus adaptée aux calculs parallèles? Mais je n'ai pas encore fait d'analyse détaillée ...
Fat32
@ Fat32 moi non plus! Vous voulez dire que l'accumulation dans la collecte de convolution pourrait devenir un goulot d'étranglement avec plusieurs cœurs travaillant sur les multiplications? Cela pourrait être atténué en donnant à chaque cœur son propre accumulateur et en les additionnant à la fin. Je pense que cette surcharge ne serait pas beaucoup comparée aux écritures de mémoire supplémentaires en convolution dispersée.
Olli Niemitalo
En fait, j'étais plus préoccupé par l' efficacité de la forme dispersée que par le goulot d'étranglement des formes de collecte.Mes codes de filtrage C actuels sont (très probablement) dans la forme de collecte, mais en ce qui concerne les codes ASM, j'ai tendance à les écrire dans des extensions SIMD SSE qui sont plus adapté à la forme dispersée. Je dois cependant mettre à jour mes tets :-))) La mémoire IO est définitivement un problème par rapport à l'accumulation de registres. Et je manque probablement la pénalité de mémoire répétée IO ...
Fat32
Quelqu'un connaît-il de meilleurs mots que la diffusion et la collecte? Je ne suis pas sûr que ceux-ci soient réservés aux noyaux de convolution clairsemés.
Olli Niemitalo
3

Il n'est "retourné" que pour le calcul ponctuel.

@Dilip explique ce que représente l'intégrale / la sommation de convolution, mais pour expliquer pourquoi l'une des deux fonctions d'entrée est (souvent h(t)) inversée à des fins de calcul, considérons un système à temps discret avec entrée x[n]et réponse impulsionnelle h[n]:

  • Vous pouvez prendre votre fonction d'entrée x[n]et, pour chaque échantillon non nul *, x[n]calculer la réponse impulsionnelle mise à l'échelle à partir de l'échantillon net ainsi de suite jusqu'à ce que le décalage temporel s'éteigne h[n]à zéro (en supposant une causalité h[n]). Cela n'impliquerait aucun «retournement» (ou plus exactement «inversion du temps») de l'un x[n]ou de l'autre h[n]. Cependant, à la fin, vous devrez ajouter / superposer tous ces «échos» échelonnés + décalés de la réponse impulsionnelle pour chaque non-zéro x[n].

  • x[0]k

    k=-X[k]h[n-k]
    h[n]x[n], ce qui est x[0]h[0]. Ensuite, l'incrémentation kde un se déplacera h[n]vers la droite d'un pas de temps, de telle sorte que la h[n]seconde entrée ( h[1]) inversée dans le temps sera maintenant placée au-dessus de x[0], attendant d'être multipliée. Cela donnera la contribution souhaitée x[0]h[1]au moment n=1, tout comme cela aurait été fait dans la méthode précédente.

x[n]

X[n]=0
h[n]y[n]
abc
la source
n
@Dilip. Tous les n sont identiques, à l'exception de «le décalage temporel h [n]», qui implique «h [nk]», où «k» est une constante utilisée pour décaler la réponse impulsionnelle au point souhaité du signal x [n ]. c'est-à-dire: h [n-2] pour calculer la réponse au signal à x [2].
abc
3

A l'indice c [n], la convolution de a [n] et b [n], est telle que:

"c [n] est une somme de tous les produits (a [k] b [m]) tels que m + k = n", donc m = n - k ou k = n - m, ce qui signifie que l'une des séquences doit être retourné.

Maintenant, pourquoi la convolution se comporte-t-elle ainsi en premier lieu? En raison de sa connexion avec la multiplication des polynômes.

La multiplication de deux polynômes donne un nouveau polynôme avec des coefficients. Les coefficients du polynôme produit définissent le fonctionnement de la convolution. Maintenant, dans le traitement du signal, les fonctions de transfert - les transformées de Laplace ou les transformées z sont ces polynômes, chaque coefficient correspondant à un retard différent. La mise en correspondance des coefficients du produit et des multiplicandes entraîne le fait que «la multiplication dans une représentation correspond à la convolution dans la représentation transformée».

entrez la description de l'image ici

Mahesh Shastry
la source
0

Pendant la convolution, aucun "retournement" de la réponse impulsionnelle ne doit se produire du tout ...

Cependant, si vous souhaitez éviter toute altération de phase, vous pouvez convoluer un signal avec une réponse impulsionnelle, puis inverser la réponse impulsionnelle et retravailler pour annuler les effets de phase.

Dans le traitement hors ligne, vous pouvez tout aussi facilement inverser le signal après la première convolution pour arriver à la même conclusion (comme le suggèrent les commentaires).

learnvst
la source
3
y(t)=-X(τ)h(t-τ)τh(t)X(t)h(t)=h(t)X(t)
@JasonR Ah, oups! Parfois difficile de voir où en est la question. Izhak, une fois que vous aurez compris la réponse que vous cherchiez, vous comprendrez où j'allais. Ignorez-moi pour l'instant!
learnvst
0

-F(τ)g(t-τ)τ
t1+t2=tF(t1)g(t2)t1t2
Fgt

t1,t2F(t1)g(t2)δ(t-t1-t2)t1t2
t1F(t1)t1t2g(t2)δ(t-t1-t2)t2
t1F(t1)t1g(t-t1)

la source