Overlap-Save-Verfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Zwischen einer Eingangsfolge x[n] und der nur durch Nullstellen gebildeten Impulsantwort 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 Impulsantwort h[n] auf. Durch den Umstand, dass die Impulsantwort h[n] keine Polstellen aufweist, kann h[n] auch als die Übertragungsfunktion eines FIR-Filter aufgefasst werden.

Das Ausgangssignal y[n], 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[Bearbeiten]

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 yk[n] ist das Intervall M  ≤  n  ≤  L + M − 1 ausreichend.

Für die periodische Fortsetzung xk,N[n] von xk[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 xk[n] mit h[n] im Intervall [1, N] zirkular zu falten. Der Teilabschnitt [ML + 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[Bearbeiten]

H = FFT(h,N)
i = 1
Nx = length(x)
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[Bearbeiten]

  •  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[Bearbeiten]

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