Overlap-Save-Verfahren

Das Overlap-Save-Verfahren ist ein Verfahren zur Schnellen Faltung. Dabei wird im Gegensatz zu dem Overlap-Add-Verfahren die Eingangsfolge x[n] in einander überlappende Teilfolgen zerlegt. Aus den gebildeten periodischen Faltungsprodukten (zyklische Faltung) werden dann jene Anteile entnommen, die mit der aperiodischen, schnellen Faltung übereinstimmen. Das Overlap-Save-Verfahren dient in den Anwendungen beispielsweise zur effizienten Implementierung von FIR-Filtern höherer Ordnung.

Allgemeines

Zwischen einer Eingangsfolge x[n] und der nur durch Nullstellen gebildeten Übertragungsfunktion h[n] und der gebildeten Ausgangsfolge y[n] besteht folgender Zusammenhang:

$y[n] = x[n] * h[n] \ \stackrel{\mathrm{def}}{=} \ \sum_{m=-\infty}^{\infty} h[m] \cdot x[n-m] = \sum_{m=1}^{M} h[m] \cdot x[n-m]$

wobei außerhalb des Intervalls [1, M] die Werte von h[m] gleich 0 sind.

Die Signalfolge x[n] weist im allgemeinen eine wesentlich größere Länge als die Länge der Übertragungsfunktion h[x] auf. Durch den Umstand, dass die Übertragungsfunktion h[x] keine Polstellen aufweist, kann h[x] auch als die Übertragungsfunktion eines FIR-Filter aufgefasst werden.

Das Ausgangssignal y[x], das aus der Faltung zweier endlicher Signale entsteht, kann allgemein in drei Teile unterteilt werden. Einschwingverhalten, stationäres Verhalten und Ausschwingverhalten. Bei der Overlap-Save Methode wird das Eingangssignal in Segmente zerlegt und jedes Segment, mittels der zyklischen Faltung mit einem Filter, einzeln gefaltet. Danach werden die Teilfaltungen wieder zusammengesetzt, wobei der Ausschwingbereich jeder dieser Teilfaltungen jetzt die darauffolgende überlappt und dadurch stören würde. Daher wird dieser Ausschwingbereich, der zu einem falschen Ergebnis führt, im Rahmen des Verfahrens verworfen. Es stoßen also die einzelnen stationären Teile der einzelnen Faltungen jetzt direkt aneinander und liefern dadurch das richtige Ergebnis der Faltung.

Verfahren

Das Prinzip besteht darin, kurze Abschnitte von y[n] mit beliebiger Länge L zu berechnen und diese Abschnitte dann aneinander zu reihen. Für ein Teilsegment, welches bei n = kL + M beginnt, k ganzzahlig, gilt:

$x_k[n] \ \stackrel{\mathrm{def}}{=} \begin{cases} x[n+kL] & M \le n \le M+L-1\\ 0 & \textrm{ansonsten}. \end{cases}$

$y_k[n] \ \stackrel{\mathrm{def}}{=} \ x_k[n]*h[n]\,$

Mit diesen Teilfolgen ergibt sich im Intervall kL + M  ≤  n  ≤  kL + L + M − 1, oder dazu gleichwertig im Intervall M  ≤  n − kL  ≤  L + M − 1, für y[n]:

$\begin{align} y[n] = \sum_{m=1}^{M} h[m] \cdot x_k[n-kL-m] &= x_k[n-kL] * h[n] &\stackrel{\mathrm{def}}{=} \ y_k[n-kL]. \end{align}$

Zur Berechnung von y_k[n] ist das Intervall M  ≤  n  ≤  L + M − 1 ausreichend.

Für die periodische Fortsetzung x_k,N[n] von x_k[n] mit der Periode N  ≥  L + M − 1:

$x_{k,N}[n] \ \stackrel{\mathrm{def}}{=} \ \sum_{k=-\infty}^{\infty} x_k[n - kN],$

ist die Faltung von $(x_{k,N})*h\,$  und  $x_k*h\,$  im Intervall M  ≤  n  ≤  L + M − 1 gleichwertig. Deswegen ist es ausreichend, N Elemente von x_k[n] mit h[n] im Intervall [1, N] zirkular zu falten. Der Teilabschnitt [M, L + M − 1] wird an die Ausgabefolge angefügt, alle anderen Werten werden verworfen.

Der Vorteil dieses Verfahrens besteht darin, dass eine zirkulare Faltungsoperation mit Hilfe der schnellen Fourier-Transformation (FFT) und der inversen schnellen Fourier-Transformation (IFFT) mit einem drastisch reduzierten Aufwand realisiert werden kann:

$y_k[n] = \textrm{IFFT}\left(\textrm{FFT}\left(x_k[n]\right)\cdot\textrm{FFT}\left(h[n]\right)\right)$

Für Details hierzu siehe den Artikel zur Schnellen Faltung.

Pseudocode

H = FFT(h,N)
i = 1
while i <= Nx
    il = min(i+N-1,Nx)
    yt = IFFT( FFT(x(i:il),N) * H, N)
    y(i : i+N-M) = yt(M : N)
    i = i+L
end

Literatur

• Karl-Dirk Kammeyer, Kristian Kroschel: Digitale Signalverarbeitung. 6. Auflage. Teubner, 2006, ISBN 3-8351-0072-6.
• Alan V. Oppenheim, Ronald W. Schafer: Zeitdiskrete Signalverarbeitung. 3. Auflage. R.Oldenbourg, 1999, ISBN 3-486-24145-1.

Weblinks

• Fast Convolution - Efficient computation of convolution using FFTs (in Englisch)