Warum ist Faltung erforderlich oder welche Philosophie steckt hinter Faltung?

Ich arbeite auf dem Gebiet der digitalen Bildwiederherstellung. Ich habe alles über Faltung gelesen, dass wir für ein LTI- System, wenn wir seine Impulsantwort kennen , seine Ausgabe finden können, indem wir nur die Faltung zwischen Eingabe und Impulsantwort verwenden.

Kann mir jemand sagen, was die mathematische Hauptphilosophie dahinter steckt? Ihre Erfahrung mit wird mir mehr als nur das Surfen im Internet erzählen.

Die Idee der Faltung

Meine Lieblingsausstellung des Themas ist in einer der Vorlesungen von Brad Osgood über die Fouriertransformation . Die Diskussion über die Faltung beginnt gegen 36:00 Uhr, aber die gesamte Vorlesung enthält einen zusätzlichen Kontext, der es wert ist, gesehen zu werden.

Die Grundidee ist, dass es hilfreich ist, übergeordnete Eigenschaften abzuleiten, die Berechnungen vereinfachen, wenn Sie so etwas wie die Fourier-Transformation definieren, anstatt ständig direkt mit der Definition zu arbeiten. Eine solche Eigenschaft ist beispielsweise, dass die Transformation der Summe zweier Funktionen gleich der Summe der Transformationen ist, d. H

$$F\{f + g\} = F\{f\} + F\{g\}.$$

Das heißt, wenn Sie eine Funktion mit einer unbekannten Transformation haben und diese mit bekannten Transformationen in eine Summe von Funktionen zerlegt werden kann, erhalten Sie die Antwort im Grunde kostenlos.

Da wir nun eine Identität für die Summe von zwei Transformationen haben, ist es eine natürliche Frage, was die Identität für das Produkt von zwei Transformationen ist, d. H

$$F\{f\}F\{g\} = \space ?.$$

Es stellt sich heraus, dass bei der Berechnung der Antwort die Faltung auftritt. Die gesamte Ableitung ist im Video angegeben, und da Ihre Frage hauptsächlich konzeptionell ist, werde ich sie hier nicht rekapitulieren.

Die Konsequenz einer solchen Annäherung an die Faltung besteht darin, dass die Laplace-Transformation (deren Spezialfall die Fourier-Transformation ist) lineare gewöhnliche Differentialgleichungen mit konstantem Koeffizienten (LCCODE) in algebraische Gleichungen umwandelt. Die Tatsache, dass eine solche Transformation verfügbar ist, um LCCODE analytisch nachvollziehbar zu machen, ist ein großer Teil des Grundes, warum sie in der Signalverarbeitung untersucht werden. Um zum Beispiel Oppenheim und Schafer zu zitieren :

Da sie sich relativ leicht mathematisch charakterisieren lassen und nützliche Signalverarbeitungsfunktionen ausführen lassen, wird die Klasse der linearen verschiebungsinvarianten Systeme eingehend untersucht.

Eine Antwort auf die Frage ist, dass bei Verwendung von Transformationsmethoden zum Analysieren und / oder Synthetisieren von LTI-Systemen früher oder später eine Faltung auftritt (entweder implizit oder explizit). Beachten Sie, dass dieser Ansatz zur Einführung der Faltung im Zusammenhang mit Differentialgleichungen sehr üblich ist. Zum Beispiel sehen Sie dies MIT-Vortrag von Arthur Mattuck . Die meisten Präsentationen präsentieren entweder das Faltungsintegral ohne Kommentar, leiten dann seine Eigenschaften ab (dh ziehen Sie es aus einem Hut), oder fassen die seltsame Form des Integrals ab, sprechen über Spiegeln und Ziehen, Zeitumkehrung usw. usw .

Der Grund, warum mir Prof. Osgoods Ansatz gefällt, ist, dass er all diese Probleme vermeidet und meiner Meinung nach einen tiefen Einblick gibt, wie Mathematiker wahrscheinlich überhaupt zu dieser Idee gekommen sind. Und ich zitiere:

Ich sagte: "Gibt es eine Möglichkeit, F und G im Zeitbereich zu kombinieren, so dass sich im Frequenzbereich die Spektren multiplizieren, die Fourier-Transformationen multiplizieren?" Und die Antwort lautet: Ja, durch dieses komplizierte Integral. Es ist nicht so offensichtlich. Sie würden morgens nicht aufstehen und dies aufschreiben und erwarten, dass dies das Problem lösen würde. Wie bekommen wir es? Sie sagten: Angenommen, das Problem ist gelöst. Sehen Sie, was passieren muss, und dann müssen wir erkennen, wann es Zeit ist, den Sieg zu erklären. Und es ist Zeit, den Sieg zu erklären.

Als widerwärtiger Mathematiker verwischen Sie Ihre Spuren und sagen: "Nun, ich werde einfach die Faltung zweier Funktionen durch diese Formel definieren."

LTI-Systeme

In den meisten DSP-Texten wird die Faltung normalerweise auf andere Weise eingeführt (so dass Verweise auf Transformationsmethoden vermieden werden). Durch Ausdrücken eines beliebigen Eingangssignals als eine Summe von skalierten und verschobenen Einheitsimpulsen,$x(n)$

$$x(n) = \sum_{k=-\infty}^\infty{x(k)\delta(n - k)}, \tag{1}$$

wo

$$\delta(n) = \begin{cases} 0, & n \ne 0 \\ 1, & n = 0, \end{cases} \tag{2}$$

Die definierenden Eigenschaften linearer zeitinvarianter Systeme führen direkt zu einer Faltungssumme mit der Impulsantwort . Wenn das durch einen LTI-Operator L definierte System ausgedrückt wird als y ( n ) = L [ x ( n ) ] , dann durch Anwenden der jeweiligen Eigenschaften, nämlich der Linearität$h(n) = L[\space \delta(n) \space]$$L$$y(n) = L[\space x(n)\space]$

$$\overbrace{L[\space ax_1(n) + bx_2(n)\space ]}^\text{Transform of the sum of scaled inputs} = \overbrace{aL[\space x_1(n)\space ] + bL[\space x_2(n)\space ]}^\text{Sum of scaled transforms} , \tag{3}$$

und Zeit / Schicht-Invarianz

$$L[\space x(n) \space] = y(n) \space \xrightarrow{\text{implies}} L[\space x(n-k) \space] = y(n-k), \tag{4}$$

Das System kann umgeschrieben werden als

$$y(n) = \overbrace{L\left[ \sum_{k=-\infty}^\infty{x(k)\delta(n - k)}\right]}^\text{Tranform of the sum of scaled inputs} = \overbrace{\sum_{k=-\infty}^\infty{x(k)L[\delta(n - k)]}}^\text{Sum of scaled transforms} = \overbrace{\sum_{k=-\infty}^\infty{x(k)h(n-k) }. }^\text{Convolution with the impulse response}$$

Das ist ein sehr üblicher Weg, um Faltung zu präsentieren, und es ist ein vollkommen eleganter und nützlicher Weg, dies zu tun. Ähnliche Ableitungen finden sich in Oppenheim und Schafer , Proakis und Manolakis , Rabiner und Gold , und ich bin sicher, viele andere. Einen tieferen Einblick (der über die Standardeinführungen hinausgeht) gibt Dilip in seiner ausgezeichneten Antwort hier .

Beachten Sie jedoch, dass diese Herleitung ein zauberhafter Trick ist. Ein weiterer Blick auf die Zerlegung des Signals in , dass es sich bereits um eine Faltung handelt. Wenn$\left(1\right)$

$$\overbrace{(f * g)(n)}^\text{f convolved with g} = \sum_{k=-\infty}^\infty{f(k)g(n-k)},$$

dann ist nur x ∗ δ . Da die Delta-Funktion das Identitätselement für die Faltung ist, kann man sagen, dass jedes Signal in dieser Form ausgedrückt werden kann, ähnlich wie wenn man sagt, dass jede Zahl n als n + 0 oder n × 1 ausgedrückt werden kann$\left(1\right)$$x * \delta$$n$$n + 0$$n \times 1$ . Die Wahl, Signale auf diese Weise zu beschreiben, ist brillant, da sie direkt zur Idee einer Impulsantwort führt - es ist nur so, dass die Idee der Faltung bereits in die Zerlegung des Signals "eingebrannt" ist.

Aus dieser Perspektive hängt die Faltung eng mit der Idee einer Delta-Funktion zusammen (dh es handelt sich um eine binäre Operation, deren Identitätselement die Delta-Funktion ist). Auch ohne Berücksichtigung der Beziehung zur Faltung hängt die Beschreibung des Signals entscheidend von der Idee der Delta-Funktion ab. Es stellt sich also die Frage, woher wir überhaupt die Idee für die Delta-Funktion haben. Soweit ich das beurteilen kann, reicht es mindestens bis zu Fouriers Arbeit über die analytische Theorie der Hitze zurück, wo es implizit erscheint. Eine Quelle für weitere Informationen ist dieses Papier über Ursprung und Geschichte der Faltung von Alejandro Domínguez.

Nun, das sind die beiden Hauptansätze für die Idee im Kontext der linearen Systemtheorie. Einer bevorzugt analytische Einsichten und der andere bevorzugt numerische Lösungen. Ich denke, beide sind nützlich, um ein vollständiges Bild von der Bedeutung der Faltung zu erhalten. In dem diskreten Fall jedoch, in dem lineare Systeme vollständig vernachlässigt werden, ist Faltung in gewisser Weise eine viel ältere Idee.

Polynom-Multiplikation

Eine gute Darstellung der Idee, dass diskrete Faltung nur eine Polynommultiplikation ist, gibt Gilbert Strang in dieser Vorlesung, die um 5:46 beginnt. Aus dieser Perspektive reicht die Idee zurück bis zur Einführung von Positionszahlensystemen (die Zahlen implizit als Polynome darstellen). Da die Z-Transformation Signale in z als Polynome darstellt, entsteht auch in diesem Zusammenhang eine Faltung - auch wenn die Z-Transformation formal als Verzögerungsoperator ohne Rückgriff auf komplexe Analysen und / oder als Sonderfall des Laplace definiert ist Transformieren .

Ich habe einmal die Antwort in der Wikipedia-Faltungsdiskussionsseite gegeben, die im Grunde die gleiche Frage stellte: Warum die Zeitumkehrung? . Die Philosophie ist, dass Sie einen einzelnen Impuls zum Zeitpunkt 0 auf Ihren Filter anwenden und dessen Reaktion zum Zeitpunkt 0,1,2,3,4,… aufzeichnen. Grundsätzlich sieht die Antwort wie eine Funktion aus, h (t). Sie können es planen. Wenn der Impuls n-mal größer / höher war, sind die Antwortimpulse proportional größer (dies liegt daran, dass immer ein lineares Filter angenommen wird). Nun, bei allem DSP (und nicht nur bei DSP) geht es darum, was passiert, wenn Sie den Filter auf Ihr Signal anwenden? Sie kennen die Impulsantwort. Ihr Signal (besonders digital) ist nichts anderes als eine Reihe von Impulsen der Höhe x (t). Es hat Höhe / Wert zum Zeitpunkt $x$$t$. Lineare Systeme sind so cool, dass Sie die Ausgänge für jeden solchen Eingangsimpuls summieren können, um die Antwortfunktion y (t) für die Eingangsfunktion x (t) zu erhalten. Sie wissen, dass der Ausgangsimpuls y (t = 10) vom unmittelbaren Eingang x (10) abhängt, der zu h (0) * x (10) beiträgt. Es gibt aber auch einen Beitrag x (9) · h (1) zum Ausgang des vorhergehenden Impulses x (9) und Beiträge von noch früheren Eingangswerten. Sie sehen, wenn Sie Beiträge aus früheren Eingaben hinzufügen, verringert sich ein Zeitargument, während sich ein anderes erhöht. Sie MAC alle Beiträge in y (10) = h (0) * x (10) + h (1) * x (9) + h (2) * x (8) + ..., was eine Faltung ist.

Sie können sich die Funktionen y (t), h (t) und x (t) als Vektoren vorstellen. Matrizen sind Operatoren in der linearen Algebra. Sie nehmen einen Eingabevektor (eine Reihe von Zahlen) und erzeugen einen Ausgabevektor (eine andere Reihe von Zahlen). In diesem Fall ist das y ein Produkt der Faltungsmatrix mit dem Vektor x,

$\vec y = \begin{bmatrix}y_0\\y_1\\y_2 \\ \vdots \end{bmatrix} = \begin{bmatrix}h_0 & 0 & 0 & \cdots \\ h_1 & h_0 & 0 & \cdots \\ h_2 & h_1 & h_0 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix}x_0\\x_1\\x_2 \\ \vdots \end{bmatrix} = H \vec x$

Da die Faltung eine Toeplitz-Matrix ist , hat sie eine Fourier-Eigenbasis und daher ist der Faltungsoperator (lineare Operatoren werden durch Matrizen dargestellt, aber die Matrix hängt auch von der Basis ab) eine schöne Diagonalmatrix im Fourier-Bereich.

$\vec Y = \begin{bmatrix}Y_0\\Y_1\\Y_2 \\ \vdots \end{bmatrix} = \begin{bmatrix} \lambda_0 & 0 & 0 & \cdots \\ 0 & \lambda_1 & 0 & \cdots \\0 & 0 & \lambda_2 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix}X_0\\X_1\\X_2 \\ \vdots \end{bmatrix} = diag(H)\vec X$

Note, much more zeroes and, thus, much simpler computation. This result is know as "convolution theorem" and, as first response answered, it is much simpler in the fourier domain. But, this is phylosophy behind the "convolution theorem", fourier basis and linear operators rather than ubiquitous need for convolution.

Normally, you do convolution because you have your input signal, impulse response and require output in time domain. You may transform into fourier space to optimize computation. But, it is not practical for simple filters, as I've seen in the DSPGuide. If your filter looks like $y[currentTime] = k_1 x[time-1] + k_2 x(time-2) + b * y[time-1]$, it makes no sense to fourier transform. You just do n multiplications, for computing every y. It is also natural for real-time. In real-time you compute only one y at a time. You may think of Fourier transform if you have your signal x recorded and you need to compute the whole vector y at once. This would need NxN MAC operations and Fourier can help to reduce them to N log(N).

Although the previous answers have been really good, I would like to add my viewpoint about convolution where I just make it easier to visualize due to the figures.

One wonders if there is any method through which an output signal of a system can be determined for a given input signal. Convolution is the answer to that question, provided that the system is linear and time-invariant (LTI).

Assume that we have an arbitrary signal $s[n]$. Then, $s[n]$ can be decomposed into a scaled sum of shifted unit impulses through the following reasoning. Multiply $s[n]$ with a unit impulse shifted by $m$ samples as $\delta[n-m]$. Since $\delta[n-m]$ is equal to 0 everywhere except at $n=m$, this would multiply all values of $s[n]$ by 0 when $n$ is not equal to $m$ and by 1 when $n$ is equal to $m$. So the resulting sequence will have an impulse at $n=m$ with its value equal to $s[m]$. This process is clearly illustrated in Figure below.

$\hspace{2cm}$

This can be mathematically written as

$$\begin{equation*} s[n] \delta [n-m] = s[m] \delta [n-m] \end{equation*}$$ Repeating the same procedure with a different delay $m'$ gives $$\begin{equation*} s[n] \delta [n-m'] = s[m'] \delta [n-m'] \end{equation*}$$

The value $s[m']$ is extracted at this instant. Therefore, if this multiplication is repeated over all possible delays $-\infty < m < \infty$, and all produced signals are summed together, the result will be the sequence $s[n]$ itself.

$$\begin{align} s[n]&= \cdots + s[-2]\delta[n+2] + s[-1]\delta[n+1] + \nonumber \\ &\quad\quad\quad\quad\quad s[0]\delta[n] + s[1]\delta[n-1] + s[2]\delta[n-2] + \cdots \nonumber \\ &= \sum \limits _{m = -\infty} ^{\infty} s[m] \delta[n-m] \label{eqIntroductionSeqImpulses} \end{align}$$

In summary, the above equation states that $s[n]$ can be written as a summation of scaled unit impulses, where each unit impulse $\delta[n-m]$ has an amplitude $s[m]$. An example of such a summation is shown in Figure below.

$\hspace{3cm}$

Überlegen Sie, was passiert, wenn es als Eingabe für ein LTI-System mit einer Impulsantwort ausgegeben wird $h[n]$.

Dies führt zu einer Eingabe-Ausgabe-Sequenz als

Während des obigen Vorgangs haben wir die berühmte Faltungsgleichung ausgearbeitet, die die Ausgabe beschreibt $r[n]$ für eine Eingabe $s[n]$ zu einem LTI-System mit Impulsantwort $h[n]$.

Faltung ist ein sehr logischer und einfacher Vorgang, der jedoch für viele DSP-Lernende aufgrund der Art und Weise, wie er erklärt wird, verwirrend ist. Wir werden eine konventionelle Methode und einen anderen intuitiveren Ansatz beschreiben.

Konventionelle Methode

---

Die meisten Lehrbücher schlagen nach der Definition der Faltungsgleichung die Implementierung anhand der folgenden Schritte vor. Für jede einzelne Zeitverschiebung$n$,

[Flip] Anordnen der Gleichung als$r[n] = \sum _{m = -\infty} ^{\infty} s[m] h[-m+n]$Betrachten Sie die Impulsantwort als eine Funktion der Variablen $m$Flip $h[m]$ Über $m = 0$ erhalten $h[-m]$.

[Shift] To obtain $h[-m+n]$ for time shift $n$, shift $h[-m]$ by $n$ units to the right for positive $n$ and left for negative $n$.

[Multiply] Point-wise multiply the sequence $s[m]$ by sequence $h[-m+n]$ to obtain a product sequence $s[m]\cdot h[-m+n]$.

[Sum] Sum all the values of the above product sequence to obtain the convolution output at time $n$.

[Repeat] Repeat the above steps for every possible value of $n$.

An example of convolution between two signals $s[n] = [2\hspace{1mm}-\hspace{-1mm}1\hspace{2mm} 1]$ und $h[n] = [-1\hspace{2mm} 1\hspace{2mm} 2]$ In der folgenden Abbildung ist das Ergebnis dargestellt $r[n]$ wird für jeden angezeigt $n$.

Beachten Sie eine Änderung in der Signaldarstellung oben. Die tatsächlichen Signale$s[n]$ und $h[n]$ sind eine Funktion des Zeitindex $n$ Die Faltungsgleichung bezeichnet jedoch beide Signale mit Zeitindex $m$. Auf der anderen Seite,$n$ wird verwendet, um die Zeitverschiebung von darzustellen $h[-m]$ vor dem Multiplizieren mit $s[m]$Punktweise. Die Ausgabe$r[n]$ ist eine Funktion des Zeitindex $n$, auf die sich diese Verschiebung bezog $h[-m]$.

Als nächstes wenden wir uns der intuitiveren Methode zu, bei der das Umdrehen eines Signals nicht erforderlich ist.

Intuitive Methode

---

Es gibt eine andere Methode, um die Faltung zu verstehen. Tatsächlich basiert es auf der Herleitung der Faltungsgleichung, dh der Ermittlung der Ausgabe$r[n]$ wie

$$\begin{align} r[n] ~ &= ~ \cdots + \nonumber \\ &\qquad\quad s[-2]\cdot h[n+2] ~+ \nonumber \\ &\qquad\qquad \quad\quad\quad s[-1]\cdot h[n+1] ~+ \nonumber \\ &\qquad\qquad \qquad\qquad\quad \quad\quad \quad s[0]\cdot h[n] ~+ \nonumber \\ &\qquad\qquad \quad \qquad\qquad\qquad \quad \quad\quad~ s[1]\cdot h[n-1] ~+ \nonumber \\ &\qquad\qquad \qquad\qquad\qquad\qquad\qquad \quad\quad\quad \quad~ s[2]\cdot h[n-2] ~+ \nonumber \\ &\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\quad\quad\quad \cdots \label{eqIntroductionConvolution3} \end{align}$$ Lösen wir das gleiche Beispiel wie in der obigen Abbildung $s[n] = [2\hspace{1mm}-~\hspace{-2mm}1\hspace{2mm} 1]$ und $h[n] = [-1\hspace{2mm} 1\hspace{2mm} 2]$. Dies ist in der folgenden Tabelle dargestellt.

$\hspace{3cm}$

Ein solches Verfahren ist in der folgenden Abbildung dargestellt. Aus Sicht der Implementierung gibt es keinen Unterschied zwischen beiden Methoden.

$\hspace{3cm}$

Zusammenfassend sagt uns die Faltung, wie sich ein LTI-System auf eine bestimmte Eingabe verhält, und dank der obigen intuitiven Methode können wir sagen, dass die Faltung auch eine Multiplikation im Zeitbereich ist (und ein Umdrehen des Signals nicht erforderlich ist), außer der Tatsache, dass Diese Zeitbereichs-Multiplikation beinhaltet Speicher. Um zu verstehen , weiter auf einer viel tieferen Ebene , wo Flipping herkommt und was im Frequenzbereich passiert, können Sie einen Probenabschnitt aus meinem Buch herunterladen hier .