Faltungsrechner

Faltungsrechner

Wachsend AI Skill PRO

Geben Sie die Berechnung ein

Formel

(Seq1∗Seq2)[i]=∑j=max⁡(0,i−m+1)min⁡(i,n−1)Seq1[j]·Seq2[i−j]({{\text{Seq}_1}} * {{\text{Seq}_2}})[i] = \sum_{j=\max(0,\,i-m+1)}^{\min(i,\,n-1)} {{\text{Seq}_1}}[j]\cdot {{\text{Seq}_2}}[i-j]
Nutzungsstatistik

Werbung

Ergebnisse

Faltungsergebnis:
4, 13, 28, 27, 18
Erste Folge 1,2,3
Zweite Folge 4,5,6

Fehler auf dieser Seite melden

Was der Faltungsrechner leistet

Dieser Faltungsrechner berechnet die diskrete Faltung zweier endlicher Zahlenfolgen. Die Faltung ist eine grundlegende Operation in der Signalverarbeitung, bei der Bildfilterung, in der Wahrscheinlichkeitsrechnung und bei der Polynommultiplikation. Statt die Summen von Hand auszurechnen, geben Sie zwei Folgen ein und das Tool liefert sofort die resultierende Ausgabefolge.

So verwenden Sie den Rechner

Es gibt nur zwei Eingabefelder:

  • Erste Folge – Ihr Eingangssignal oder die erste Zahlenmenge, eingegeben als durch Kommas getrennte Werte (zum Beispiel 1, 2, 3).
  • Zweite Folge – Ihr zweites Signal, der Kern oder Filter, ebenfalls durch Kommas getrennt (zum Beispiel 0, 1, 0.5).

Dezimalzahlen und negative Zahlen sind zulässig. Der Rechner trennt jede Eingabe an den Kommas auf, entfernt Leerzeichen und wandelt jeden Eintrag in eine Zahl um, bevor das Ergebnis berechnet wird.

Die Formel erklärt

Die diskrete Faltung ist definiert als:

$$(\text{Folge}_1 * \text{Folge}_2)[i] = \sum_{j=\max(0,\,i-m+1)}^{\min(i,\,n-1)} \text{Folge}_1[j]\cdot \text{Folge}_2[i-j]$$

Bei zwei endlichen Folgen der Länge n und m hat das Ergebnis genau n + m − 1 Werte. Jeder Ausgabewert \(y[i]\) ist die Summe aller Produkte \(x[j] \cdot h[i - j]\), bei denen die Indizes innerhalb beider Folgen bleiben. Einfach gesagt schiebt das Tool eine Folge über die andere, multipliziert die sich überlappenden Terme und addiert sie bei jeder Verschiebung.

Werbung
Diagramm der diskreten Faltung als Spiegeln und Verschieben zweier Folgen, die eine Ausgabefolge ergeben
Die Faltung spiegelt eine Folge und schiebt sie über die andere; bei jeder Verschiebung werden die sich überlappenden Produkte summiert.

Rechenbeispiel

Die erste Folge sei 1, 2, 3 und die zweite Folge 0, 1, 0.5. Hier ist n = 3 und m = 3, das Ergebnis hat also 3 + 3 − 1 = 5 Werte:

  • \(y[0] = 1\cdot 0 = 0\)
  • \(y[1] = 1\cdot 1 + 2\cdot 0 = 1\)
  • \(y[2] = 1\cdot 0{,}5 + 2\cdot 1 + 3\cdot 0 = 2{,}5\)
  • \(y[3] = 2\cdot 0{,}5 + 3\cdot 1 = 4\)
  • \(y[4] = 3\cdot 0{,}5 = 1{,}5\)

Die Ausgabe lautet also 0, 1, 2.5, 4, 1.5.

Drei Stabdiagramme: Eingangsfolge, zweite Folge und die längere resultierende Faltungsausgabe
Die Ausgabe ist länger als jede der beiden Eingaben und hat die Länge n + m − 1.

So berechnen Sie eine Faltung von Hand

Die diskrete lineare Faltung verknüpft zwei endliche Folgen, \(x\) der Länge \(n\) und \(h\) der Länge \(m\), zu einer einzigen Ausgabe \(y = x * h\). Die definierende Summe lautet

$$y[i] = \sum_{j} x[j]\,h[i-j], \qquad i = 0,1,\dots,n+m-2$$

wobei jeder Term, dessen Index außerhalb einer Folge liegt, als null behandelt wird. Das folgende Verfahren ist die übliche Methode „Spiegeln und Verschieben“ und entspricht dem, was dieser Rechner ausführt (volle lineare Faltung, ohne Abschneiden).

  1. Längen notieren. Sei \(n\) die Anzahl der Glieder der ersten Folge und \(m\) die der zweiten. Die Ausgabe hat immer genau \(n+m-1\) Glieder. Prüfen Sie zuerst diese Zahl – sie ist der einfachste Schutz gegen ein vergessenes Glied.
  2. Beide Folgen ab 0 indizieren. Schreiben Sie \(x[0],x[1],\dots,x[n-1]\) und \(h[0],h[1],\dots,h[m-1]\). Mit der Nummerierung ab null funktioniert die Verschiebungsrechnung \(i-j\) ohne Versatz.
  3. Die zweite Folge umkehren (spiegeln). Schreiben Sie \(h\) rückwärts: \(h[m-1],\dots,h[1],h[0]\). Durch das Spiegeln wird aus der Summe \(\sum_j x[j]h[i-j]\) eine einfache Spalte ausgerichteter Produkte.
  4. Die gespiegelte Folge über die erste schieben. Beginnen Sie bei der Verschiebung \(i=0\), bei der nur das letzte Element des gespiegelten Kerns – also \(h[0]\) – unter \(x[0]\) liegt. Schieben Sie den gespiegelten Kern für jedes weitere \(i\) um eine Position nach rechts.
  5. Ausgerichtete Paare multiplizieren und summieren. Multiplizieren Sie bei jeder Verschiebung jedes senkrecht übereinanderliegende Paar und addieren Sie die Produkte. Diese eine Zahl ist \(y[i]\).
  6. Indizes außerhalb des Bereichs als null behandeln. Ragt der gespiegelte Kern an einem Ende über, sind die fehlenden Werte Nullen (Zero-Padding), sodass diese Produkte nichts beitragen. Gleichwertig beschränken Sie die Summe auf \(\max(0,\,i-m+1) \le j \le \min(i,\,n-1)\).
  7. \(y[i]\) für \(i = 0,1,\dots,n+m-2\) festhalten. Hören Sie auf, wenn der gespiegelte Kern vollständig über das rechte Ende hinausgelaufen ist; die letzte von null verschiedene Verschiebung ist \(i=n+m-2\).

Anordnung der gleitenden Ausrichtung

Mit \(n=3\) und \(m=2\) – den Folgen \(x=[x_0,x_1,x_2]\) und \(h=[h_0,h_1]\) – gleitet der gespiegelte Kern \([h_1,h_0]\) wie folgt. Die Ausgabe hat \(3+2-1=4\) Glieder.

Verschiebung \(i\) Unter \(x_0\) ausgerichtet Unter \(x_1\) ausgerichtet Unter \(x_2\) ausgerichtet Produkte in \(y[i]\)
0 \(h_0\) — — \(y[0]=x_0h_0\)
1 \(h_1\) \(h_0\) — \(y[1]=x_0h_1+x_1h_0\)
2 — \(h_1\) \(h_0\) \(y[2]=x_1h_1+x_2h_0\)
3 — — \(h_1\) \(y[3]=x_2h_1\)

Beachten Sie das Muster: In jedem Produkt ergeben die beiden Indizes zusammen \(i\). Das ist die ganze Regel – \(y[i]\) ist die Summe aller \(x[j]h[k]\) mit \(j+k=i\).

Die Sichtweise der Polynommultiplikation

Weil sich die Indizes addieren, ist die Faltung identisch mit dem Multiplizieren von Polynomen und dem Zusammenfassen der Koeffizienten. Ordnen Sie jeder Folge ein Polynom in einer Hilfsvariablen \(z\) zu:

$$X(z)=x_0+x_1z+x_2z^2, \qquad H(z)=h_0+h_1z$$

Dann gilt

$$X(z)H(z)=x_0h_0+(x_0h_1+x_1h_0)z+(x_1h_1+x_2h_0)z^2+x_2h_1z^3$$

dessen Koeffizienten genau \(y[0],y[1],y[2],y[3]\) sind. Ein Polynom vom Grad \(n-1\) mal ein Polynom vom Grad \(m-1\) hat den Grad \(n+m-2\), also \(n+m-1\) Koeffizienten – dieselbe Längenregel. So lässt sich eine Handrechnung bequem überprüfen: Multiplizieren Sie die Polynome mit gewöhnlicher Algebra aus und vergleichen Sie die Koeffizientenlisten.

Werbung

Wichtige Begriffe und Notation

Begriff Bedeutung
Faltung \(x * h\) Die Operation \(y[i]=\sum_j x[j]\,h[i-j]\), die zwei Folgen verknüpft, indem alle Produkte summiert werden, deren Indizes zusammen \(i\) ergeben. Geschrieben mit einem Stern: \(y = x * h\).
Folge / Signal \(x[n]\) Eine geordnete Liste von Zahlen, die über eine ganze Zahl \(n\) indiziert ist – Messwerte, eine Datenreihe oder eine Menge von Koeffizienten. Hier beginnt die Indizierung bei \(n=0\).
Kern / Filter / Impulsantwort \(h[n]\) Drei Bezeichnungen für dieselbe zweite Folge. „Kern“ oder „Filter“ betont die Gewichte, die auf benachbarte Abtastwerte angewendet werden; „Impulsantwort“ ist die Systemsicht – \(h\) ist genau die Ausgabe, die ein lineares zeitinvariantes System bei einem einzelnen Einheitsimpuls liefert.
Index \(n\) (oder \(i\)) und Verschiebungsvariable \(j\) \(i\) bezeichnet die gerade berechnete Ausgabeposition; \(j\) ist die interne Summationsvariable, die über die sich überlappenden Positionen läuft. Innerhalb der Summe wird \(x\) an der Stelle \(j\) und \(h\) an der Stelle \(i-j\) gelesen.
Träger und Ausgabelänge Der Träger ist der Indexbereich, in dem eine Folge von null verschieden ist. Hat \(x\) \(n\) Glieder und \(h\) \(m\) Glieder, belegt die Ausgabe die Indizes \(0\) bis \(n+m-2\) – genau \(n+m-1\) Werte.
Zero-Padding Jeder Index außerhalb des definierten Bereichs einer Folge wird als null behandelt. Dadurch lässt sich die Summe ohne Sonderfälle über alle \(j\) schreiben; es erklärt auch die betragsmäßig kleineren Werte an den beiden Enden der Ausgabe.
Lineare vs. zyklische Faltung Die lineare Faltung füllt die Enden mit Nullen auf und liefert \(n+m-1\) Werte. Die zyklische Faltung schließt die Enden ringförmig und liefert nur \(\max(n,m)\) Werte; sie ergibt sich natürlich aus der Multiplikation bei DFT/FFT. Dieser Rechner berechnet die lineare Faltung im Modus „full“ – nichts wird auf die kürzere Ausgabe „same“ oder „valid“ gekürzt, die manche Softwarebibliotheken standardmäßig liefern.
Kommutativ \(x * h = h * x\). Vertauschen Sie die beiden Eingabefolgen, erhalten Sie dieselbe Ausgabe; es spielt also keine Rolle, welche Sie als Signal und welche als Kern bezeichnen.
Assoziativ \((x * h_1) * h_2 = x * (h_1 * h_2)\). Zwei hintereinandergeschaltete Filter lassen sich durch einen einzigen Filter ersetzen, der ihrer Faltung entspricht.
Distributiv \(x * (h_1 + h_2) = x * h_1 + x * h_2\). Parallel geschaltete Filter addieren sich.
LTI-System Ein lineares, zeitinvariantes System: Skalieren und Addieren der Eingänge skaliert und addiert die Ausgänge, und eine Verzögerung des Eingangs verzögert lediglich die Ausgabe. Jedes solche System wird vollständig durch seine Impulsantwort beschrieben, und seine Ausgabe ist die Faltung des Eingangs mit \(h\).
Gleitender Mittelwert / Glättungsfilter Ein Kern aus \(k\) gleichen Gewichten \(1/k\), z. B. \(h = [0{,}5, 0{,}5]\) oder \(h = [1/3, 1/3, 1/3]\). Die Faltung damit mittelt jeden Abtastwert mit seinen Nachbarn und dämpft schnelle Schwankungen; die ersten und letzten Ausgabewerte sind Randeffekte, die durch das Zero-Padding verfälscht sind.
Diskrete vs. kontinuierliche Faltung Die diskrete Form summiert, die kontinuierliche integriert: \((x * h)(t) = \int_{-\infty}^{\infty} x(\tau)\,h(t-\tau)\,d\tau\). Dieses Tool behandelt den diskreten (abgetasteten) Fall.
Multiplikation von Polynomkoeffizienten Ist \(X(z)=\sum_j x[j]z^j\) und \(H(z)=\sum_k h[k]z^k\), dann sind die Koeffizienten von \(X(z)H(z)\) genau \(x * h\). Die schriftliche Multiplikation ganzer Zahlen folgt derselben Idee, mit Übertrag.
Summe unabhängiger Zufallsvariablen Sind \(X\) und \(Y\) unabhängig und ganzzahlig, ist die Wahrscheinlichkeitsfunktion von \(Z = X+Y\) die Faltung ihrer Wahrscheinlichkeitsfunktionen: \(P(Z=k)=\sum_j P(X=j)\,P(Y=k-j)\). Die Faltung von \([1/6,\dots,1/6]\) mit sich selbst ergibt zum Beispiel die Verteilung der Augensumme zweier fairer sechsseitiger Würfel.

Häufig gestellte Fragen

Wie lang ist die Ausgabefolge? Immer so lang wie die erste Folge plus die Länge der zweiten Folge minus eins (n + m − 1).

Spielt die Reihenfolge der beiden Folgen eine Rolle? Nein. Die Faltung ist kommutativ; Vertauschen der beiden Eingaben liefert dieselbe Ergebnisfolge.

Kann ich den Rechner für die Polynommultiplikation verwenden? Ja. Wenn Sie jede Folge als Koeffizienten eines Polynoms auffassen, ergibt die Faltung die Koeffizienten des Produkts – eine praktische Abkürzung für die Algebra ebenso wie für Signale.

Zuletzt aktualisiert:

Am beliebtesten in Mathe und Statistik

Alle Mathe und Statistik Rechner anzeigen