Schnelle Faltung

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

Von der diskreten Faltung zur schnellen diskreten Faltung

Im Zeitbereich ist die diskrete Faltung definiert als:

$h(n)=(f*g)(n)=\sum _{k}f(k)\cdot g(n-k)$

Wird die diskrete Faltung in den Frequenzbereich diskret fourier-transformiert, ergibt sich folgender Term:

$H(N)={\mathcal {F}}(h(n))={\mathcal {F}}(f(n))\cdot {\mathcal {F}}(g(n))$

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

$h(n)={\mathcal {F}}^{-1}(H(N))=(f*g)(n)$.

Anwendung

Die Anwendungsbereiche der schnellen Faltung umfassen primär Filteranwendungen im Bereich nicht rekursiver Filter (FIR-Filter). Die dabei eingesetzten Verfahren nennen sich Overlap-Save-Verfahren und 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 $h[n]$ identisch ist zur diskreten linearen Faltung.

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

Um die zyklische Faltung über die 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 $g[n]$ sei kürzer als die Eingangsfolge $f[n]$ ($G<K$).

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

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

Vorteile

Der Einsatz der schnellen Faltung mit Hilfe der FFT führt zu einer Reduktion des Rechenaufwandes, sodass dieser für jeden Wert (jedes Sample) nicht mehr proportional von der Länge (Anzahl der Werte) K der Funktion $g(k)$ 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 FFT durchgeführt wird.

Für eine Menge von N Werten (Samples) ergeben sich folgende Komplexitäten (gemessen als Anzahl arithmetischer Grundoperationen wie Additionen und Multiplikationen):

• diskrete Faltung

$O(N\cdot K)$

• schnelle diskrete Faltung

$O(N\cdot \mathrm {log} (N))$, falls $N>K$.

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, 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 Overlap-Add- oder Overlap-Save-Verfahrens, 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 Signalprozessoren mit Festkommaarithmetik zu beachten.

Literatur

• Karl-Dirk Kammeyer: Digitale Signalverarbeitung. 6. Auflage. Teubner, 2006, ISBN 3-8351-0072-6, S. 248–260. 
• Steven W. Smith, Ph.D.: The Scientist and Engineer’s Guide to Digital Signal Processing. 1. Auflage. Elsevier Ltd, Oxford 2002, ISBN 978-0-7506-7444-7, 18. Kapitel (englisch, dspguide.com).