Funktion

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

${\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 ${\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:

${\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]

${\displaystyle x[n]=\sum _{k}x_{k}[n-kL]}$ ,

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

${\displaystyle {\begin{aligned}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{aligned}}}$

Die Ausgangsteilfolgen

${\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:

${\displaystyle 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:

${\displaystyle N=L+M=2^{p},\quad p\in \mathbb {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