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 nicht überlappende Teilfolgen zerlegt. Diese Segmente werden mit Nullen aufgefüllt, von denen dann die DFT (bzw. FFT) gebildet wird. Das Ergebnis bildet einen Teil der Ausgangsfolge, bei deren Zusammensetzung die Überlappungsbereiche – im Gegensatz zum Overlap-Save-Verfahren – addiert werden. Das Ziel dieses Verfahrens ist es, die zyklische Faltungsoperation der zur schnellen Faltung eingesetzten schnellen Fourier-Transformation in die aperiodische Faltungsoperation zu überfü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]:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 verlorengehen soll, wird jeder der Abschnitte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 sich die einzelnen Faltungsprodukte ü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]

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x[n] = \sum_{k} x_k[n-kL]} ,

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Summierung 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = L + M = 2^p, \quad p \in \N}

Pseudocode

In Abhängigkeit vom 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: The Scientist and Engineer's Guide to Digital Signal Processing. Elsevier Ltd., Oxford 2002, ISBN 978-0-7506-7444-7, Kap. 18 (englisch, dspguide.com). 

Weblinks

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