Rechner für lineare Faltung

Rechner für lineare Faltung

Wachsend AI Skill PRO

Geben Sie die Berechnung ein

Formel

y[n]=∑kx[k]·h[n−k]y[n] = \sum_{k} {x[k]} \cdot {h[n-k]}
Nutzungsstatistik

Werbung

Ergebnisse

Lineare Faltung
4, 13, 28, 27, 18
Erste Folge 1,2,3
Zweite Folge 4,5,6
Maximalwert 28
Minimalwert 4

Fehler auf dieser Seite melden

Was dieser Rechner leistet

Der Rechner für lineare Faltung nimmt zwei diskrete Folgen entgegen und verknüpft sie mithilfe der diskreten linearen Faltung. Die Faltung ist ein grundlegendes Werkzeug der digitalen Signalverarbeitung (DSP). Mit ihr berechnet man die Ausgabe eines linearen zeitinvarianten Systems (LTI-System), wenn man das Eingangssignal und die Impulsantwort kennt. Geben Sie Ihre beiden Zahlenfolgen ein, und das Tool liefert sofort die vollständige gefaltete Folge samt Maximal- und Minimalwert.

So verwenden Sie den Rechner

Es gibt nur zwei Eingabefelder:

  • Erste Folge – Ihr Eingangssignal x, eingegeben als durch Kommas getrennte Zahlen, z. B. 1, 2, 3.
  • Zweite Folge – Ihr zweites Signal h (häufig eine Impulsantwort), z. B. 0, 1, 0.5.

Dezimalzahlen und negative Zahlen werden unterstützt. Jeder Wert wird von Leerzeichen befreit und als Zahl eingelesen, die Abstände spielen also keine Rolle.

Die Formel

Die diskrete lineare Faltung ist definiert als:

$$y[n] = \sum_{k} x[k] \cdot h[n-k]$$

In der Praxis setzt der Rechner dies mit einer direkten doppelten Schleife um: Jedes Element der ersten Folge wird mit jedem Element der zweiten multipliziert, und jedes Produkt \(x[i]\cdot h[j]\) wird zur Ausgabeposition \(i + j\) addiert. Die resultierende Folge hat die Länge len(x) + len(h) − 1.

Werbung
Veranschaulichung der linearen Faltung zweier diskreter Folgen durch Spiegeln und Verschieben
Die lineare Faltung spiegelt eine Folge und schiebt sie über die andere, wobei die überlappenden Produkte summiert werden.

Rechenbeispiel

Es sei x = [1, 2, 3] und h = [1, 1]. Die Ausgabelänge beträgt \(3 + 2 - 1 = 4\).

  • \(y[0] = 1\cdot 1 = 1\)
  • \(y[1] = 1\cdot 1 + 2\cdot 1 = 3\)
  • \(y[2] = 2\cdot 1 + 3\cdot 1 = 5\)
  • \(y[3] = 3\cdot 1 = 3\)

Die Faltung ergibt also [1, 3, 5, 3] mit einem Maximalwert von 5 und einem Minimalwert von 1.

Faltung als Multiplikationsraster, das entlang der Diagonalen summiert wird
Jeder Ausgabewert ist die Summe der Elementprodukte entlang einer Diagonale des Multiplikationsrasters.

Wichtige Begriffe der Faltung

Begriff Bedeutung
Diskrete Folge \(x[n]\) Eine geordnete Liste von Zahlen, die durch eine ganze Zahl \(n\) indiziert ist, typischerweise Abtastwerte eines Signals. Die Einträge, die Sie als kommagetrennte Werte eingeben, sind \(x[0],x[1],x[2],\dots\)
Impulsantwort \(h[n]\) Die Ausgabe, die ein System erzeugt, wenn sein Eingang ein einzelner Einheitsimpuls ist. Bei einem LTI-System beschreibt sie das System vollständig: Die Antwort auf jede Eingabe ist diese Eingabe gefaltet mit \(h[n]\).
LTI-System Linear und zeitinvariant: Das Skalieren und Addieren von Eingaben skaliert und addiert die Ausgaben (Linearität), und eine Verzögerung der Eingabe verzögert lediglich die Ausgabe (Zeitinvarianz). Die Faltung beschreibt genau diese Systemklasse.
Einheitsimpuls \(\delta[n]\) Die Folge, die bei \(n=0\) gleich 1 und sonst überall 0 ist. Sie ist das neutrale Element der Faltung: \(x[n]*\delta[n]=x[n]\).
Kernel / Filterkoeffizienten (Taps) Gebräuchliche Bezeichnungen für die endliche Folge \(h\), wenn sie als Filter verwendet wird. Jeder einzelne Koeffizient \(h[k]\) ist ein „Tap“; ein Kernel der Länge 5 ist ein Filter mit 5 Taps.
Faltungssumme \(y[n]=\sum_{k} x[k]\,h[n-k]\) – für jeden Ausgabeindex \(n\) wird jeder Eingabewert mit dem Kernelwert multipliziert, dessen Index \(k+(n-k)=n\) erfüllt, und anschließend werden die Produkte addiert.
Träger / Länge Die Menge der Indizes, an denen eine Folge ungleich null ist. Für endliche Folgen der Längen \(N\) und \(M\) hat die Faltung einen Träger der Länge \(N+M-1\).
Index \(n\) und Verschiebung \(n-k\) \(n\) ist die Ausgabeposition; \(k\) durchläuft die Eingabewerte. Die Schreibweise \(h[n-k]\) bedeutet, dass der Kernel zeitlich umgekehrt (gespiegelt) und an die Position \(n\) geschoben wird – das Bild vom „Spiegeln und Verschieben“ der Faltung.
Lineare vs. zirkuläre Faltung Die lineare Faltung (dieser Rechner) wächst auf die Länge \(N+M-1\). Die zirkuläre Faltung behandelt die Folgen als periodisch mit der Länge \(L=\max(N,M)\) und wickelt den Überhang an den Anfang zurück, sodass ein Ergebnis der Länge \(L\) entsteht; sie entspricht dem elementweisen Produkt zweier DFTs.
Kreuzkorrelation \(r[n]=\sum_k x[k]\,h[k+n]\) – dieselbe Operation aus Verschieben und Summieren, aber ohne Spiegelung. Die Korrelation von \(x\) mit \(h\) entspricht der Faltung von \(x\) mit dem zeitlich umgekehrten \(h\); beide stimmen überein, wenn \(h\) symmetrisch ist.
Kommutativität \(x*h=h*x\): Das Vertauschen der beiden Eingaben liefert dieselbe Ausgabefolge.
Assoziativität \((x*h_1)*h_2=x*(h_1*h_2)\): Hintereinandergeschaltete Filter lassen sich zu einem einzigen äquivalenten Kernel zusammenfassen.
Distributivität \(x*(h_1+h_2)=x*h_1+x*h_2\): Parallele Zweige addieren sich, was die Grundlage für die Zerlegung von Filtern ist.
Zero-Padding (Nullauffüllung) Das Anhängen von Nullen an eine Folge. Nullen ändern die von null verschiedenen Werte einer linearen Faltung nicht, doch wenn beide Folgen auf eine Länge \(\ge N+M-1\) aufgefüllt werden, entspricht eine zirkuläre (DFT-basierte) Faltung der linearen.
Werbung

Interpretation Ihrer gefalteten Folge

Was die Ausgabeindizes bedeuten. Der Rechner gibt \(y[0],y[1],y[2],\dots\) aus und nimmt dabei an, dass beide Eingaben bei Index 0 beginnen. Beginnen Ihre Folgen tatsächlich woanders, liegt der erste Ausgabewert bei der Summe der beiden Startindizes: Beginnt \(x\) bei \(n_x\) und \(h\) bei \(n_h\), so beginnt \(y\) bei \(n_x+n_h\). Faltet man beispielsweise einen bei \(-1\) zentrierten Kernel mit einem bei 0 beginnenden Signal, gehört der erste Ausgabewert zu \(n=-1\); Sie müssen die ausgegebene Liste daher um eins nach links verschieben, bevor Sie sie über der Zeit auftragen.

Länge und Verbreiterung. Die Ausgabelänge beträgt stets

$$\operatorname{len}(y)=\operatorname{len}(x)+\operatorname{len}(h)-1$$

das Signal verbreitert sich also um \(\operatorname{len}(h)-1\) zusätzliche Abtastwerte. Diese zusätzlichen Werte erscheinen als Einschwingvorgang (die ersten \(\operatorname{len}(h)-1\) Ausgaben, bei denen der Kernel die Daten nur teilweise überlappt) und als Ausklingen am Ende. Bei der Echtzeitfilterung werden diese Randwerte oft verworfen oder gesondert behandelt, da sie aus einer unvollständigen Überlappung und nicht aus dem vollständigen Kernel berechnet werden.

Die Summenprobe. Eine schnelle Möglichkeit, ein Ergebnis zu prüfen: Die Summe der Ausgabe entspricht dem Produkt der Eingabesummen:

$$\sum_n y[n]=\left(\sum_n x[n]\right)\left(\sum_n h[n]\right)$$

Für \(x=[1,2,3]\) und \(h=[1,1]\) lautet die Ausgabe [1, 3, 5, 3], deren Summe \(1+3+5+3=12\) beträgt und mit \(6\times 2=12\) übereinstimmt. Stimmen Ihre Summen nicht überein, wurde ein Index ausgelassen oder ein Vorzeichen falsch behandelt.

Was die Summe des Kernels aussagt. Gilt \(\sum_n h[n]=1\), bleiben Gesamtpegel und Mittelwert des Signals erhalten – das ist das Kennzeichen eines Glättungs- bzw. Tiefpass-Kernels wie \([0.5,0.5]\) oder \([1/3,1/3,1/3]\). Gilt \(\sum_n h[n]=0\), werden konstante Anteile der Eingabe ausgelöscht und nur Änderungen bleiben erhalten: \(h=[1,-1]\) ist ein Kernel für die erste Differenz (Hochpass), der auf jedem konstanten Abschnitt null ausgibt und an Flanken Spitzen erzeugt. Ein Kernel mit einer Summe größer als 1 bewirkt eine Nettoverstärkung; eine Summe kleiner als 1 (aber ungleich null) bewirkt eine Nettodämpfung.

Spitzenamplitude. Maximum und Minimum geben die größten positiven und negativen Ausschläge des gefilterten Signals an – nützlich, um Überlauf oder Übersteuerung bei Festkomma-Implementierungen zu erkennen. Jeder Ausgabewert erfüllt

$$|y[n]|\le\left(\sum_k |x[k]|\right)\max_k |h[k]|$$

was eine sichere Worst-Case-Schranke ist. Eine engere und ebenso gebräuchliche Schranke ist \(\max_n|y[n]|\le \max_n |x[n]|\cdot\sum_k|h[k]|\); die Größe \(\sum_k|h[k]|\) ist die Verstärkung des Filters bei ungünstigstem beschränktem Eingangssignal.

Verhalten bei Impulsen. Die Faltung mit \(\delta[n]=[1]\) gibt die Eingabe unverändert zurück, und die Faltung mit einem verschobenen Impuls – \([0,0,1]\), also \(\delta[n-2]\) – liefert eine exakte, um 2 Abtastwerte verzögerte Kopie. Impulse eignen sich daher gut als Plausibilitätstest: Soll ein Kernel neutral sein, muss die Eingabe einer einzelnen 1 den Kernel selbst reproduzieren, denn \(\delta[n]*h[n]=h[n]\).

Diese Eigenschaften sind allgemeine mathematische Tatsachen über die diskrete lineare Faltung und an keine nationale Norm und kein Softwarepaket gebunden. Wenn Sie Ergebnisse mit einer DFT-basierten Routine vergleichen, beachten Sie, dass diese eine zirkuläre Faltung berechnet, sofern nicht beide Folgen auf mindestens \(\operatorname{len}(x)+\operatorname{len}(h)-1\) mit Nullen aufgefüllt werden.

Häufig gestellte Fragen

Wie lang ist das Ergebnis? Immer die Summe der beiden Eingabelängen minus eins. Die Faltung einer Folge mit 4 Elementen und einer mit 3 Elementen ergibt 6 Werte.

Spielt die Reihenfolge der Folgen eine Rolle? Nein. Die Faltung ist kommutativ; das Vertauschen von erster und zweiter Folge liefert dieselbe Ausgabefolge.

Ist das dasselbe wie die Kreuzkorrelation? Nein. Die Faltung spiegelt vor dem Verschieben eine Folge (der Term \(h[n - k]\)), die Korrelation tut dies nicht. Die Ergebnisse unterscheiden sich, es sei denn, eine der Folgen ist symmetrisch.

Zuletzt aktualisiert:

Am beliebtesten in Mathe und Statistik

Alle Mathe und Statistik Rechner anzeigen