Umdrehen der Impulsantwort in der Faltung

26

Warum müssen wir während der Faltung eines Signals die Impulsantwort während des Prozesses umdrehen?

winuall
quelle
5
Die zweite Hälfte dieser Antwort kann Ihnen beim Verständnis helfen.
Dilip Sarwate
3
Neben der großartigen Antwort von @ DilipSarwate ist es eine gute Übung, ein Blatt Papier zu nehmen und die Ausgabe eines LTI-Systems grafisch zu berechnen, indem zeitversetzte und skalierte Versionen der Impulsantwort addiert werden.
Deve
1
Beachten Sie, dass Sie beide Argumente spiegeln können - das Ergebnis ist dasselbe.
Wakjah

Antworten:

29

Angepasst von einer Antwort auf eine andere Frage (wie in einem Kommentar erwähnt) in der Hoffnung, dass diese Frage nicht wiederholt vom Community Wiki als eine der Top-Fragen geworfen wird ....

Es gibt kein "Umkehren" der Impulsantwort durch ein lineares (zeitinvariantes) System. Die Ausgabe eines linearen zeitinvarianten Systems ist die Summe der skalierten und zeitverzögerten Versionen der Impulsantwort, nicht der "gekippten" Impulsantwort.

Wir zerlegen das Eingangssignal x in eine Summe skalierter Einheitsimpulssignale. Die Systemantwort auf das Einheitsimpulssignal , 0, 0, 1, 0, 0, ist die Impulsantwort oder Impulsantwort

h[0], h[1],, h[n],
und so weiter Skalierungseigenschaft der einzelne Eingabewert x[0], oder, wenn Sie es vorziehen, erzeugt eine Antwort x [ 0 ] h [ 0 ] , x [ 0 ] h [ 1 ] , , x
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],

Ähnlich ist die einzige Eingangswert oder erstellt x [ 1 ] ( , 0 , 0 , 0 , 1 , 0 , ) = 0 , 0 , 0 , x [ 1 ] , 0 , erzeugt eine Antwort 0 , x [ 1 ] h [ 0 ] , x [ 1x[1]

x[1](, 0, 0, 0, 1, 0,)= 0, 0, 0, x[1], 0,
Beachten Sie die Verzögerung in der Antwort auf x [ 1 ] . Wir können in diesem Sinne fortfahren, aber es ist am besten, zu einer tabellarischeren Form zu wechseln und die verschiedenen Ausgaben rechtzeitig richtig ausgerichtet anzuzeigen. Wir haben Zeit 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] Die Zeilen im obigen Array sind genau die skalierten und verzögerten Versionen von die Impulsantwort, die sich zu der Antwortyauf das Eingangssignalxaddiert. Aber wenn Sie eine spezifischere Frage stellen, wie z
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

Was ist die Ausgabe zum Zeitpunkt ?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
quelle
4

Hier ist ein C / C ++ - Beispiel, das zeigt, dass die Faltung ohne umgekehrte Verwendung der Impulsantwort durchgeführt werden kann. Wenn Sie die convolve_scatter()Funktion überprüfen , wird nirgendwo eine Variable negiert. Dies ist eine Streuungsfaltung, bei der jede Eingangsabtastung zu mehreren Ausgangsabtastungen im Speicher gestreut (summiert) wird, wobei Gewichtungen verwendet werden, die durch die Impulsantwort gegeben sind. Dies ist verschwenderisch, da die Ausgabebeispiele mehrmals gelesen und beschrieben werden müssen.

Normalerweise Faltung wird als getan Sammeln Faltung, wie in convolve_gather(). Bei diesem Verfahren wird jede Ausgangsabtastung separat gebildet, indem Eingangsabtastungen mit der umgekehrten Impulsantwort als Gewichtungen zu diesen gesammelt (summiert) werden. Das Ausgabesample befindet sich in einem Prozessorregister, das währenddessen als Akkumulator verwendet wird. Dies ist normalerweise die Methode der Wahl, da für jedes gefilterte Sample nur ein Speicherschreibvorgang ausgeführt wird. Es gibt jetzt mehr Speicherlesevorgänge der Eingabe, aber nur so viele, wie Speicherlesevorgänge der Ausgabe bei der Streumethode vorhanden waren.

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

Es faltet die Sequenzen zusammen:

1 0 0 0 2
1 2 3

und mit beiden Faltungsmethoden Ausgaben:

1 2 3 0 2 4 6

Ich kann mir niemanden vorstellen, der die Streumethode verwendet, es sei denn, der Filter variiert zeitlich. In diesem Fall führen die beiden Methoden zu unterschiedlichen Ergebnissen, und eine ist möglicherweise geeigneter.

Olli Niemitalo
quelle
Interessant! Also, was ist die endgültige Schlussfolgerung, die ich sehen
möchte
Ihr architektonisches Anliegen ist interessant. Unter Berücksichtigung der verfügbaren Caches, SIMD - Befehle (SSE, AVX) und Multi - Core Architekturen, die Streu scheint Verfahren besser geeignet für parallele Berechnungen? Aber ich habe keine detaillierte Analyse durchgeführt ...
Fat32
@Fat32 mir auch nicht! Sie meinen, die Akkumulation beim Sammeln von Faltungen könnte zu einem Engpass werden, wenn mehrere Kerne an Multiplikationen arbeiten? Dies könnte gemildert werden, indem jeder Kern seinen eigenen Akkumulator erhält und am Ende aufsummiert wird. Ich denke, dieser Overhead wäre nicht viel im Vergleich zu den zusätzlichen Speicherschreibvorgängen in verstreuter Faltung.
Olli Niemitalo
Eigentlich ging es mir mehr um die Effizienz des gestreuten Formulars als um den Engpass beim Sammeln von Formularen. Meine aktuellen C-Filtercodes befinden sich (höchstwahrscheinlich) im Sammelformular, aber wenn es um ASM-Codes geht, tendiere ich dazu, sie in SIMD-SSE-Erweiterungen zu schreiben, die mehr sind geeignet für verstreute Form. Ich habe zu aktualisieren meine tets jedoch :-))) Speicher IO ist definitiv ein Problem im Vergleich Akkumulation zu registrieren. Und wahrscheinlich vermisse ich die Strafe für wiederholte Speicher-IO ...
Fat32
Kennt jemand bessere Worte als Streuen und Sammeln? Ich bin nicht sicher, ob diese für spärliche Faltungskerne reserviert sind.
Olli Niemitalo
3

Es wird nur für die punktweise Berechnung "umgedreht".

@Dilip erklärt, was das Faltungsintegral / die Faltungssummation darstellt. Um jedoch zu erklären, warum eine der beiden Eingabefunktionen (häufig h(t)) zu Berechnungszwecken gekippt wird, betrachten Sie ein zeitdiskretes System mit Eingabe x[n]und Impulsantwort h[n]:

  • Sie könnten Ihre Eingabefunktion übernehmen x[n]und für jede Nicht-Null * -Abtastung x[n]die skalierte Impulsantwort von Abtastung nund weiter berechnen, bis die zeitversetzte h[n]Verzögerung auf Null zurückgeht (unter der Annahme einer Kausalität h[n]). Dies würde kein 'Umdrehen' (oder genauer 'Zeitumkehr') von entweder x[n]oder beinhalten h[n]. Am Ende müssten Sie jedoch alle diese skalierten + verschobenen "Echos" der Impulsantwort für jede Nicht-Null addieren / überlagern x[n].

  • x[0]k

    k=x[k]h[nk]
    h[n]x[n], was ist x[0]h[0]. Inkrementieren kum eins verschiebt sich dann h[n]um einen Zeitschritt nach rechts, sodass der h[n]zweite Eintrag ( h[1]) der Zeitumkehrung nun darauf liegt x[0]und darauf wartet, multipliziert zu werden. Dies ergibt zum gewünschten x[0]h[1]Zeitpunkt den gewünschten Beitrag n=1, genau wie dies bei der vorherigen Methode der Fall gewesen wäre.

x[n]

x[n]=0
h[n]y[n]
ABC
quelle
n
@ Dilip. Alle n sind gleich, mit Ausnahme von 'the time-shifted h [n]', was 'h [nk]' impliziert, wobei 'k' eine Konstante ist, die verwendet wird, um die Impulsantwort auf den gewünschten Punkt des Signals x [n zu verschieben ]. dh: h [n-2] zum Berechnen der Antwort auf das Signal bei x [2].
abc
3

Am Index c [n] ist die Faltung von a [n] und b [n] so, dass:

"c [n] ist eine Summe aller Produkte (a [k] b [m]), so dass m + k = n," also m = n - k oder k = n - m, was bedeutet, dass eine der Sequenzen muss gekippt werden.

Warum verhält sich Faltung überhaupt so? Wegen seiner Verbindung mit multiplizierenden Polynomen.

Die Multiplikation zweier Polynome ergibt ein neues Polynom mit Koeffizienten. Die Koeffizienten des Produktpolynoms definieren den Vorgang der Faltung. In der Signalverarbeitung sind Transferfunktionen - Laplace-Transformationen oder Z-Transformationen - diese Polynome, wobei jeder Koeffizient einer anderen Zeitverzögerung entspricht. Die Übereinstimmung der Koeffizienten des Produkts und der Multiplikanden führt zu der Tatsache, dass "Multiplikation in einer Darstellung der Faltung in der transformierten Darstellung entspricht".

Bildbeschreibung hier eingeben

Mahesh Shastry
quelle
0

Während der Faltung muss überhaupt kein "Flip" der Impulsantwort auftreten ...

Wenn Sie jedoch eine Phasenänderung verhindern möchten, können Sie ein Signal mit einer Impulsantwort falten und dann die Impulsantwort umkehren und erneut falten, um die Phaseneffekte aufzuheben.

Bei der Offline-Verarbeitung können Sie das Signal nach der ersten Faltung genauso einfach umkehren, um zu derselben Schlussfolgerung zu gelangen (wie aus den Kommentaren hervorgeht).

learnvst
quelle
3
y(t)=x(τ)h(tτ)dτh(t)x(t)h(t)=h(t)x(t)
@ JasonR Ah, whoops! Manchmal ist es schwer zu erkennen, worauf es bei der Frage ankommt. Izhak, sobald Sie die Antwort verstanden haben, nach der Sie gesucht haben, werden Sie verstehen, wohin ich wollte. Ignoriere mich jetzt!
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)

quelle