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.
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.
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. |
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.