Überlappung hinzufügen versus Überlappung speichern

24

Welche Unterschiede oder andere Kriterien können verwendet werden, um zu entscheiden, ob Überlappung hinzugefügt oder Überlappung gespeichert werden soll? Sowohl das Hinzufügen von Überlappungen als auch das Speichern von Überlappungen werden als Algorithmen zum Ausführen einer FFT-basierten schnellen Faltung von Datenströmen mit FIR-Filterkernen beschrieben. Welche Unterschiede gibt es hinsichtlich Latenz, Rechenleistung oder Caching-Lokalität (usw.)? Oder sind sie gleich?

hotpaw2
quelle

Antworten:

27

Das Betriebssystem ist im Wesentlichen etwas effizienter, da keine überlappenden Transienten hinzugefügt werden müssen. Möglicherweise möchten Sie jedoch OA verwenden, wenn Sie die FFTs mit Null-Padding anstelle von wiederholten Samples wiederverwenden müssen.

Hier ist ein kurzer Überblick über einen Artikel, den ich vor einiger Zeit geschrieben habe

Schnelle Faltung bezieht sich auf die blockweise Verwendung einer kreisförmigen Faltung, um eine lineare Faltung zu erreichen. Eine schnelle Faltung kann durch OA- oder OS-Methoden erreicht werden. OS wird auch als „Overlap-Scrap“ bezeichnet. Bei der OA-Filterung enthält jeder Signaldatenblock nur so viele Abtastwerte, wie eine Kreisfaltung einer linearen Faltung entspricht. Der Signaldatenblock wird vor der FFT mit Nullen aufgefüllt, um zu verhindern, dass die Filterimpulsantwort das Ende der Sequenz „umfließt“. Durch die OA-Filterung wird der Eingangs-Ein-Übergang von einem Block zum Eingangs-Aus-Übergang vom vorherigen Block hinzugefügt. Bei der in 1 gezeigten OS-Filterung werden die Eingangsdaten nicht mit Nullen aufgefüllt, sodass die Kreisfaltung nicht der linearen Faltung entspricht. Die Teile, die "herumlaufen", sind unbrauchbar und werden weggeworfen. Um dies auszugleichen, Der letzte Teil des vorherigen Eingabeblocks wird als Anfang des nächsten Blocks verwendet. Das Betriebssystem erfordert keine zusätzlichen Transienten und ist daher schneller als OA.

Mark Borgerding
quelle
Großartiger Artikel! =)
Phonon
Es kann einige Optimierungen in der Art und Weise geben, wie die DFT über dem mit Nullen aufgefüllten Teil des OA-Puffers berechnet wird, die der OA-Methode eine Kante geben. Dies hängt von Ihrem Prozessor und Ihrem FFT-Paket ab. Sie können auch Ihren eigenen FFT-Algorithmus speziell für den OA schreiben, der das Null-Pad berücksichtigt.
Orodbhen
@orodbhen, kennst du ein solches FFT-Paket?
Mark Borgerding
@MarkBorgerding In OpenCV können Sie die Anzahl der Nullzeilen angeben, dies gilt jedoch nur für 2D. Inwieweit implizite Optimierungen in diesem oder anderen FFT-Paketen vorhanden sind, weiß ich nicht. Ich kann mir viele Fälle vorstellen, in denen eine benutzerdefinierte FFT zur Ausnutzung der Spärlichkeit hilfreich wäre, aber ich bin diesen Weg nicht selbst gegangen. Noch nicht.
Orodbhen
1
Gut, dass Sie zitiert haben, weil der Link nicht
Mehrdad