Overlap-Save-Verfahren

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.

Inhaltsverzeichnis

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 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

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)

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Overlap-Add-Verfahren — Das Overlap Add Verfahren ist ein Verfahren zur Schnellen Faltung und wird in der digitalen Signalverarbeitung eingesetzt. Dabei wird eine Eingangsfolge in einander überlappende Teilfolgen zerlegt und die Überlappungsbereiche, im Gegensatz zum… …   Deutsch Wikipedia

  • Schnelle Faltung — Die Schnelle Faltung ist ein Algorithmus zur Berechnung der diskreten, aperiodischen Faltungsoperation mit Hilfe der schnellen Fourier Transformation (FFT). Dabei wird die rechenintensive aperiodische Faltungsoperation im Zeitbereich durch eine… …   Deutsch Wikipedia

  • FIR-Filter — Ein Filter mit endlicher Impulsantwort (englisch finite impulse response filter, FIR Filter, oder manchmal auch Transversalfilter genannt) ist ein diskreter, meist digital implementierter Filter und wird im Bereich der digitalen… …   Deutsch Wikipedia

  • Filter mit begrenztem Impulsansprechverhalten — Ein Filter mit endlicher Impulsantwort (englisch finite impulse response filter, FIR Filter, oder manchmal auch Transversalfilter genannt) ist ein diskreter, meist digital implementierter Filter und wird im Bereich der digitalen… …   Deutsch Wikipedia

  • Finite impulse response — Ein Filter mit endlicher Impulsantwort (englisch finite impulse response filter, FIR Filter, oder manchmal auch Transversalfilter genannt) ist ein diskreter, meist digital implementierter Filter und wird im Bereich der digitalen… …   Deutsch Wikipedia

  • Finite impulse response filter — Ein Filter mit endlicher Impulsantwort (englisch finite impulse response filter, FIR Filter, oder manchmal auch Transversalfilter genannt) ist ein diskreter, meist digital implementierter Filter und wird im Bereich der digitalen… …   Deutsch Wikipedia

  • Nicht-rekursiver Filter — Ein Filter mit endlicher Impulsantwort (englisch finite impulse response filter, FIR Filter, oder manchmal auch Transversalfilter genannt) ist ein diskreter, meist digital implementierter Filter und wird im Bereich der digitalen… …   Deutsch Wikipedia

  • Transversalfilter — Ein Filter mit endlicher Impulsantwort (englisch finite impulse response filter, FIR Filter, oder manchmal auch Transversalfilter genannt) ist ein diskreter, meist digital implementierter Filter und wird im Bereich der digitalen… …   Deutsch Wikipedia

  • Segmentierte Faltung — Die segmentierte Faltung (englisch overlap add, OA, OLA) ist ein Verfahren zur Schnellen Faltung und wird in der digitalen Signalverarbeitung eingesetzt. Dabei wird eine Eingangsfolge in einander überlappende Teilfolgen zerlegt und die… …   Deutsch Wikipedia

  • Modifizierte diskrete Kosinustransformation — Die modifizierte diskrete Kosinustransformation (englisch Modified Discrete Cosine Transform, MDCT) ist eine reellwertige, diskrete, lineare, orthogonale Transformation, die zu der Gruppe der diskreten Fouriertransformationen (DFT) zählt und eine …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”