imported>Hybridrix: /* Literatur */Link zu Kammeyer

2025-08-22T16:32:31Z

Literatur: Link zu Kammeyer

Neue Seite

Die '''Schnelle Faltung''' ist ein [[Algorithmus]] zur Berechnung der diskreten, aperiodischen [[Faltung (Mathematik)|Faltungsoperation]] mit Hilfe der [[Schnelle Fourier-Transformation|schnellen Fourier-Transformation]] (FFT). Dabei wird die rechenintensive aperiodische Faltungsoperation im [[Zeitbereich]] durch eine wesentlich einfachere, funktionell gleichwertige, Multiplikation im [[Frequenzspektrum|Frequenzbereich]] ersetzt. Anwendung findet die schnelle Faltung im Bereich der [[Digitale Signalverarbeitung|digitalen Signalverarbeitung]] unter anderem bei [[Filter mit endlicher Impulsantwort|nicht-rekursiven digitalen Filtern]] (''FIR-Filter'') zur Reduktion des Berechnungsaufwandes.

== Von der diskreten Faltung zur schnellen diskreten Faltung ==
Im [[Zeitbereich]] ist die [[Faltung (Mathematik)#Diskrete Faltung|diskrete Faltung]] definiert als:
: <math> h(n) = (f * g)(n) = \sum_{k} f(k) \cdot g(n-k)</math>

Wird die diskrete Faltung in den [[Frequenzspektrum|Frequenzbereich]] [[Diskrete Fourier-Transformation|diskret fourier-transformiert]], ergibt sich folgender Term:

: <math> H(N) = \mathcal{F}(h(n)) = \mathcal{F}(f(n)) \cdot \mathcal{F}(g(n))</math>

<math>H(N)</math> wird berechnet und anschließend in den Zeitbereich zurücktransformiert, es ergibt sich die gesuchte Funktion:

: <math> h(n) = \mathcal{F}^{-1}(H(N)) = (f * g)(n)</math>.

== Anwendung ==
Die Anwendungsbereiche der schnellen Faltung umfassen primär Filteranwendungen im Bereich [[Filter mit endlicher Impulsantwort|nicht rekursiver Filter]] (FIR-Filter). Die dabei eingesetzten Verfahren nennen sich [[Overlap-Save-Verfahren]] und [[Segmentierte Faltung|Overlap-Add-Verfahren]]. Da es sich bei der schnellen Faltung mittels FFT und deren Zusammenfassen der Daten in Blöcke um eine [[zyklische Faltung]] handelt, andererseits aber FIR-Filter mit der aperiodischen Faltung im Zeitbereich arbeiten, sind zur Gleichstellung der periodischen mit der aperiodischen Faltung Verfahren nötig, um die Daten in den Überlappungsbereichen zwischen den Datenblöcken zu „korrigieren“. Daraus leitet sich der Name ''Overlap'' in den Verfahren zur schnellen Faltung ab.

== Überlappungsfehler ==
Im Folgenden wird auf den Effekt der Überlappung bei der schnellen (zyklische-) Faltung eingegangen, und
in welchen Fällen das Resultat <math>h[n]</math> identisch ist zur [[Faltung (Mathematik)#Diskrete Faltung|diskreten linearen Faltung]].

Wird die Eingangsfolge <math>f[n]</math> der Länge ''K'' mit der [[Impulsantwort]] <math>g[n]</math> der Länge ''G'' gefaltet, ergeben sich bei der linearen Faltung <math>N=K+G-1</math> Ausgangswerte <math>h[n]</math>.

Um die zyklische Faltung über die [[Diskrete Fourier-Transformation|DFT]] überhaupt durchführen zu können, müssen Eingangssequenz und [[Impulsantwort]] gleich lang sein. Ist dies nicht gegeben, muss der kürzere Vektor durch Anfügen von Nullen ausgeglichen werden (''zero-padding'').

Zur Vereinfachung der folgenden Betrachtung nehmen wir an die Impulsantwort <math>g[n]</math> sei kürzer als die Eingangsfolge <math>f[n]</math> (<math>G < K</math>).

Da die Rücktransformation mittels [[IFFT]] aus dem [[Frequenzspektrum|Spektrum]] in diesem Fall als Faltungsprodukt anstelle von <math>N=K+G-1</math> ebenfalls nur K [[Abtastung (Signalverarbeitung)|Samples]] liefert (siehe Eigenschaften der DFT), ergibt sich in der Ausgangsfolge ein Überlappungsfehler an den ersten <math>G-1</math> Stellen. Zudem ist sie um <math>G-1</math> zu kurz, da sich die fehlenden Werte zu den ersten hinzuaddieren. Der Fehler lässt sich durch Anfügen von ''mindestens'' <math>G-1</math> Nullen an <math>f[n]</math> und <math>K-1</math> Nullen an <math>g[n]</math> korrigieren (zusätzliche Nullen am Ende stören den DFT-[[Algorithmus]] nicht, wenn die Länge eine Zweierpotenz ist, arbeiten manche [[Schnelle Fourier-Transformation|FFT]]-Implementierungen wesentlich effizienter).

Mithilfe des ''Zero-Padding'' haben beide Vektoren nun <math>N=K+G-1</math> Elemente, das Ergebnis <math>h[n]</math> der schnellen Faltung liefert ebenfalls <math>N=K+G-1</math> Werte.
Wie bei der linearen Faltung tritt kein Überlappungsfehler mehr auf.

== Vorteile ==
Der Einsatz der schnellen Faltung mit Hilfe der [[Schnelle Fourier-Transformation|FFT]] führt zu einer Reduktion des [[Rechenaufwand]]es, sodass dieser für jeden Wert (jedes Sample) nicht mehr proportional von der Länge (Anzahl der Werte) ''K'' der Funktion <math>g(k)</math> abhängt, sondern nur noch logarithmisch von der gewählten Blockgröße ''N'', mit der Randbedingung, dass ''N'' größer als ''K'' sein muss, mit der die [[Schnelle Fourier-Transformation|FFT]] durchgeführt wird.

Für eine Menge von ''N'' Werten (Samples) ergeben sich folgende [[Komplexität (Informatik)|Komplexitäten]] (gemessen als Anzahl arithmetischer Grundoperationen wie Additionen und Multiplikationen):
* diskrete Faltung
:<math> O(N \cdot K) </math>
* schnelle diskrete Faltung
:<math> O(N \cdot \mathrm{log}(N))</math>, falls <math>N>K</math>.

Praktisch realisierte FIR-Filter sind ab einer Ordnung von ca. 20 bis 40 mittels der schnellen Faltung meist effizienter als in der direkten Form zu implementieren.

== Nachteile ==
Ein Problem der schnellen diskreten Faltung ist ihre [[Verzögerung (Telekommunikation)|Verzögerung]], die durch das Warten auf eine der Blockgröße ''N'' entsprechenden Menge an Werten (Samples) zur Berechnung der schnellen diskreten Faltung verursacht wird:

Die Blockgröße muss mindestens der Länge des Signals im Zeitbereich, mit dem die Funktion gefaltet werden soll, entsprechen, da sonst das Ergebnis kürzer als die Impulsantwort der Faltung wäre. Zudem muss bei Verwendung des [[Segmentierte Faltung|Overlap-Add-]] oder [[Overlap-Save-Verfahren]]s, wenn die Entstehung von Artefakten durch das Verfahren gänzlich vermieden werden soll, diese minimale Blocklänge zusätzlich um den Abstand der einzelnen Pakete, in denen die Faltung vorgenommen werden soll, verlängert werden – weswegen große Blocklängen tendenziell eher Ergebnisse mit einer höheren Effizienz liefern. Weiterhin kann je nach konkreter FFT-Implementierung noch die Bedingung existieren, dass die Blockgröße ''N'' einer ganzzahligen Potenz von 2, 4 oder 8 entsprechen muss – was zusammen am Ende unter Umständen zu einer sehr hohen Blockgröße ''N'' führen kann.

Ein weiterer Nachteil ist das schwerer zu kalkulierende [[Quantisierungsrauschen]] über die gesamte Faltungsoperation. Dieses ist bei der schnellen Faltung tendenziell höher als bei der diskreten Faltung. Das Problem des Quantisierungsrauschens ist vor allem bei [[Digitaler Signalprozessor|Signalprozessoren]] mit [[Festkommazahl|Festkommaarithmetik]] zu beachten.

== Literatur ==
* {{Literatur
|Autor=[[Karl-Dirk Kammeyer]]
|Titel=Digitale Signalverarbeitung
|Auflage=6.
|Verlag=Teubner
|Datum=2006
|ISBN=3-8351-0072-6
|Seiten=248–260}}
* {{Literatur
|Autor=Steven W. Smith, Ph.D.
|Titel=The Scientist and Engineer’s Guide to Digital Signal Processing
|Auflage=1.
|Verlag=Elsevier Ltd
|Ort=Oxford
|Datum=2002
|ISBN=978-0-7506-7444-7
|Kapitel=18. Kapitel
|Sprache=en
|Online=[http://www.dspguide.com/ dspguide.com]}}

[[Kategorie:Algorithmus]]
[[Kategorie:Filter (Elektrotechnik)|!]]
[[Kategorie:Digitale Signalverarbeitung]]

[[en:Convolution#Fast convolution algorithms]]

Schnelle Faltung - Versionsgeschichte

imported>Hybridrix: /* Literatur */Link zu Kammeyer