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 Überlappungsbereiche, im Gegensatz zum Overlap-Save-Verfahren, aufaddiert. Das Ziel dieses Verfahrens ist die zyklische Faltungsoperation der zur schnellen Faltung eingesetzten schnellen Fourier-Transformation in die aperiodische Faltungsoperation überzuführen. Bei der segmentierten Faltung können, im Gegensatz zu dem Overlap-Save-Verfahren, prinzipbedingte Signallaufzeiten auftreten, welche im Bereich der Dauer eines Blockes zur schnellen Fourier-Transformation liegen.

In den Anwendungen wird die segmentierte Faltung zur effizienten Implementierung von FIR-Filtern höherer Ordnung verwendet. Die segmentierte Faltung hat dabei im Gegensatz zur direkten Implementierung der aperiodischen Faltungsoperation in digitalen Signalprozessoren (DSP) den Vorteil, Ressourcen wie Speicher oder Rechenzeit zu sparen.

Verfahren

Funktion

Grafische Darstellung der schnellen Faltung mittels segmentierter Faltung

Die direkte Ausführung der aperiodischen Faltungsoperation zwischen einer beliebig langen Eingangsfolge x[n] und der Impulsantwort h[n] der Länge M ergibt die Ausgangsfolge y[n]:

$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 h[m] außerhalb des Intervalls [1, M] gleich 0 gesetzt ist. Dieses Verfahren zur schnellen Faltung beruht auf der folgenden Idee:

• Das unendlich lange Eingangssignal wird in kurze Abschnitte der Länge L aufgeteilt, welche im Folgenden mit dem Index k zur Unterscheidung versehen sind.
• Da das Ergebnis der Faltung eines Abschnittes der Länge L mit einer Funktion der Länge M L+M Werte lang ungleich 0 sein kann und keine Information vom Ergebnis verloren gehen soll, wird jeder der Abschnitte x_k mit M Nullen aufgefüllt (dies wird auch als Zero-Padding bezeichnet), um das Ergebnis der Faltungsoperation auf die Länge L+M zu bringen:

$x_k[n] \ \stackrel{\mathrm{def}}{=} \begin{cases} x[n+kL] & n=1,2,\ldots,L\\0 & \textrm{ansonsten} \end{cases}$

• Nun werden die Ergebnisse der einzelnen Faltungen dort addiert, wo die einzelnen Faltungsprodukte sich überlappen – und das Ergebnis dieser Operation entspricht der Faltung der unendlich langen Eingangsfolge.

Mathematische Beschreibung

Die Eingangsfolge x[n] besteht aus der Summe der Teilfolgen x_k[n]

x[n] =	∑	xk[n − kL]
	k

womit die Ausgangsfolge y[n] als Summe einzelner Faltungen dargestellt werden kann:

$\begin{align} y[n] = \left(\sum_{k} x_k[n-kL]\right) * h[n] &= \sum_{k} \left(x_k[n-kL]* h[n]\right)\\ &= \sum_{k} y_k[n-kL] \end{align}$

Die Ausgangsteilfolgen

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

sind außerhalb des Intervalls [1,L+M-1] Null. Für jeden Wert des Parameters N, der größer-gleich als L+M-1 gewählt sein muss, ergibt sich die zirkulare Faltungsoperation der Ausgangsfolge. Die einzelnen Ausgabefolgen y_k[k] überlappten sich in den Intervallen [k(L+1),k(L+M)] und durch die Summation wird die Ausgabefolge y[k] gebildet.

Vorteile dieses Verfahrens

Der Vorteil besteht darin, dass die zirkulare Faltungsoperation zur Bildung der Teilfolgen y_k effizient in Form der schnellen Fourier-Transformation (FFT) beziehungsweise der inversen schnellen Fourier-Transformation (IFFT) nach folgender Form implementiert werden kann:

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

Je nach verwendeten FFT-Algorithmus ist es sinnvoll, die konkrete Blocklänge N zur Berechnung der zirkularen Teilfaltungen abzustimmen. Bei Verwendung des FFT-Algorithmus nach Cooley und Tukey (Radix-2-Algorithmus) ist es günstig die Blocklänge als Zweierpotenz zu wählen:

$N = L + M = 2^p, \quad p \in \N$

Pseudocode

In Abhängigkeit des FFT-Algorithmus N und L wählen.
    H = FFT(h,N)
    i = 1
    while i <= Nx
        il = min(i+L-1,Nx)
        yt = IFFT( FFT(x(i:il),N) * H, N)
        k  = min(i+N-1,Nx)
        y(i:k) = y(i:k) + yt    (die überlappenden Bereiche addieren)
        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.
• Steven W. Smith, Ph.D.: The Scientist and Engineer's Guide to Digital Signal Processing. 1 Auflage. Elsevier Ltd, Oxford, 2002, ISBN 978-0750674447, 18 (http://www.dspguide.com).

Weblinks

• www.dspguide.com/ch18/2.htm