Schnelle Faltung

Die Schnelle Faltung ist ein Algorithmus

Sie unterscheidet sich von der Diskreten Faltung dadurch, dass sie nicht im Zeitbereich sondern mit Hilfe der Diskrete-Fourier-Transformation(DFT) im Frequenzbereich berechnet wird.

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 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}}(H(N))=(f*g)(n)$.

Anwendung

An Stelle der DFT kommen bei der Berechnung schnelle Varianten der DFT die sogenannte schnelle-Diskrete-Fourier-Transformation (FFT) zum Einsatz, wobei diese wiederum die Anwendung bestimmter Verfahren z.B. Overlap-Save-FFT oder Overlap-Add-FFT erfordern, da ansonsten das Ergebnis wegen der Aufteilung der Funktion f(n) in getrennte Bereiche verfälscht wird.

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össe N, mit der Randbedingung das N größer als K sein muss, mit der die FFT durchgefuehrt wird.

Für eine Menge von N-Werten (Samples) ergeben sich folgende Komplexitäten:

- diskrete Faltung $O(N)=N\cdot K$

- schnelle diskrete Faltung $O(N)=N\cdot ld(N)|N>K$

Nachteile

Ein Problem der schnellen diskreten Faltung ist ihre Latenz, die durch das warten auf einer der Blockgrösse N entsprechenden Menge an Werten (Samples) zur Berechnung der schnellen diskreten Faltung verursacht wird.

Einerseits sollte zur moeglichst effizienten Anwendung der FFT die gewaehlte Blockgrösse N möglichst klein sein, andererseits muss wegen der Multiplikation im Frequenzbereich mit der Funktion G(N) die gewaehlte Blockgrösse mindestens der Länge K der Funktion G(N) entsprechen. Weiterhin kann je nach konkreter FFT-Implementation noch die Bedingung existieren, dass die Blockgroesse N einer Potenz von 2 entsprechen muss (restfrei durch 2 teilbar ist). Daher kann die gewählte Blockgrösse N unter Umständen, mit technischen Massstäben betrachtet, sehr groß werden mit einer in der Konsequenz entsprechend großen Latenz und hohen technischen Anforderungen.