Schnelle Faltung
aus Wikipedia, der freien Enzyklopädie
Die Schnelle Faltung ist ein Algorithmus zur Berechnung der diskreten, aperidoischen Faltungsoperation. Dabei wird die rechenintensive Faltungsoperation im Zeitbereich durch eine wesentlich einfachere Multiplikation im Frequenzbereich ersetzt.
Die schnelle Faltung unterscheidet sich von der Diskreten Faltung dadurch, dass sie nicht im Zeitbereich sondern mit Hilfe der Diskreten Fourier-Transformation (DFT) im Frequenzbereich berechnet wird.
Inhaltsverzeichnis |
[Bearbeiten] Von der diskreten Faltung zur schnellen diskreten Faltung
Im Zeitbereich ist die diskrete Faltung definiert als:
Wird die diskrete Faltung in den Frequenzbereich transformiert ergibt sich folgender Term:
H(N) wird berechnet und anschließend in den Zeitbereich zurücktransformiert, es ergibt sich die gesuchte Funktion:
.
[Bearbeiten] Anwendung
An Stelle der DFT kommt bei der Berechnung die schnelle Fourier-Transformation (FFT) zum Einsatz. Die Anwendungsbereiche der schnellen Faltung umfassen primär Filteranwendungen im Bereich sogenannter Filter mit endlicher Impulsantwort (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 periodische Faltung handelt, anderseits 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 Überlappungsbereiche zwischen den Datenblöcken zu "korrigieren". Daraus leitet sich der Name Overlap in den Verfahren zur schnellen Faltung ab.
[Bearbeiten] 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, 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
- schnelle diskrete Faltung
, 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.
[Bearbeiten] Nachteile
Ein Problem der schnellen diskreten Faltung ist ihre Latenz, die durch das Warten auf eine der Blockgrösse N entsprechenden Menge an Werten (Samples) zur Berechnung der schnellen diskreten Faltung verursacht wird.
Einerseits sollte zur möglichst effizienten Anwendung der FFT die gewählte Blockgröße N möglichst klein sein, andererseits muss diese wegen der Multiplikation im Frequenzbereich mit der Funktion G(N) mindestens der Länge K der Funktion G(N) entsprechen. Weiterhin kann je nach konkreter FFT-Implementierung noch die Bedingung existieren, dass die Blockgröße N einer ganzzahligen Potenz von 2 entsprechen muss. Daher kann die gewählte Blockgröße N unter Umständen, mit technischen Maßstäben betrachtet, sehr groß werden mit einer in der Konsequenz entsprechend großen Latenz und hohen technischen Anforderungen.
Ein weiterer wesentlicher Nachteil ist das erhöhte bzw. schwerer zu kalkulierende Quantisierungsrauschen über die gesamte Faltungsoperation. Dieses Problem ist vor allem bei Signalprozessoren mit Festkommaarithmetik zu beachten.
