imported>Hybridrix: /* Literatur */Link zu Kammeyer

2025-08-22T16:46:30Z

Literatur: Link zu Kammeyer

Neue Seite

Die '''segmentierte Faltung''' (englisch '''overlap add''', '''OA''', '''OLA''') ist ein Verfahren zur [[Schnelle Faltung|Schnellen Faltung]] und wird in der [[digitale Signalverarbeitung|digitalen Signalverarbeitung]] eingesetzt. Dabei wird eine Eingangsfolge in einander nicht überlappende Teilfolgen zerlegt. Diese Segmente werden mit Nullen aufgefüllt, von denen dann die [[Diskrete_Fourier-Transformation|DFT]] (bzw. [[Schnelle_Fourier-Transformation|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 Faltung]]soperation der zur schnellen Faltung eingesetzten [[schnelle Fourier-Transformation|schnellen Fourier-Transformation]] in die aperiodische Faltungsoperation zu überführen. Bei der segmentierten Faltung können, im Gegensatz zu dem Overlap-Save-Verfahren, prinzipbedingte [[Laufzeit (Elektrotechnik)|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-Filter]]n höherer Ordnung verwendet. Die segmentierte Faltung hat dabei im Gegensatz zur direkten Implementierung der aperiodischen Faltungsoperation in [[digitaler Signalprozessor|digitalen Signalprozessoren]] (DSP) den Vorteil, Ressourcen wie Speicher oder Rechenzeit zu sparen.

== Verfahren ==
=== Funktion ===
[[Datei:Depiction of overlap-add algorithm.png|rechts|miniatur|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]:

: <math> 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]</math>

wobei ''h''[m] außerhalb des Intervalls [1, M] gleich 0 gesetzt ist. Dieses Verfahren zur [[schnelle Faltung|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 <math>x_k</math> 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:
: <math>x_k[n] \ \stackrel{\mathrm{def}}{=}
\begin{cases}
x[n+kL] & n=1,2,\ldots,L\\0
& \textrm{ansonsten}
\end{cases}
</math>
* 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]

: <math>x[n] = \sum_{k} x_k[n-kL]</math> ,

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

: <math>
\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}
</math>

Die Ausgangsteilfolgen

: <math>y_k[n] \ \stackrel{\mathrm{def}}{=} \ x_k[n]*h[n]</math>

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 [[schnelle Fourier-Transformation|schnellen Fourier-Transformation]] (FFT) beziehungsweise der inversen schnellen Fourier-Transformation (IFFT) nach folgender Form implementiert werden kann:

: <math>y_k[n] = \textrm{IFFT}\left(\textrm{FFT}\left(x_k[n]\right)\cdot\textrm{FFT}\left(h[n]\right)\right)</math>

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:

: <math>N = L + M = 2^p, \quad p \in \N</math>

=== Pseudocode ===
In Abhängigkeit vom FFT-Algorithmus <code>N</code> und <code>L</code> wählen.

<syntaxhighlight lang="text">
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
</syntaxhighlight>

== Literatur ==
* {{Literatur
|Autor=[[Karl-Dirk Kammeyer]], Kristian Kroschel
|Titel=Digitale Signalverarbeitung
|Auflage=6.
|Verlag=Teubner
|Datum=2006
|ISBN=3-8351-0072-6}}
* {{Literatur
|Autor=Alan V. Oppenheim, Ronald W. Schafer
|Titel=Zeitdiskrete Signalverarbeitung
|Auflage=3.
|Verlag=R.Oldenbourg
|Datum=1999
|ISBN=3-486-24145-1}}
* {{Literatur
|Autor=Steven W. Smith
|Titel=The Scientist and Engineer's Guide to Digital Signal Processing
|Auflage=
|Verlag=Elsevier Ltd.
|Ort=Oxford
|Datum=2002
|ISBN=978-0-7506-7444-7
|Kapitel=18
|Sprache=en
|Online=http://www.dspguide.com/}}

== Weblinks ==
* [http://www.dspguide.com/ch18/2.htm www.dspguide.com/ch18/2.htm]

[[Kategorie:Digitale Signalverarbeitung]]
[[Kategorie:Algorithmus]]
[[Kategorie:Filter (Elektrotechnik)|!]]

Segmentierte Faltung - Versionsgeschichte

imported>Hybridrix: /* Literatur */Link zu Kammeyer