Fast Fourier transform

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
FFT-vlinderberekening

In de numerieke wiskunde is een Fast Fourier transform (snelle fouriertransformatie, afgekort tot FFT) een algoritme voor het efficiënt berekenen van de discrete fouriertransformatie (DFT) van een discreet signaal waarvan de waarden bekend zijn in een eindig aantal N equidistante punten. Terwijl directe berekening een efficiëntie heeft van O(N^2), is de efficiëntie van een FFT O(N\log_2N). De daarmee gemoeide tijdwinst is aanzienlijk, zeker voor grote N.

Het algoritme is ontwikkeld door James Cooley en John Tukey in 1965, en komt er in zijn oorspronkelijke vorm op neer dat een fouriertransformatie met lengte N wordt gesplitst in twee transformaties met lengte N/2, waarbij gebruikgemaakt wordt van de periodiciteit en symmetrie in de sinus en cosinus. Door deze opsplitsing recursief toe te passen ontstaat een verbetering van de orde N/\log_2N. Voor bijvoorbeeld N=8192 is dat al een factor 630.

Voor de toegepassing van een dergelijke recursie is vereist dat N een macht van 2 is. Later is deze methode gegeneraliseerd naar een ontbinding in willekeurige priemfactoren, waardoor een meer algemene toepasbaarheid ontstond. Gebruik van grote priemfactoren kan echter zeer nadelige gevolgen hebben voor de rekentijd. Voor praktische toepassing zoals in signaalanalyse heeft de beperking tot machten van twee nauwelijks gevolgen. Wanneer een 3-dimensionale FFT wordt gebruikt, zoals in de kristallografie, kan het echter leiden tot bijna 8 keer meer geheugengebruik en 24 keer meer rekentijd dan strikt noodzakelijk.

Het algoritme van Cooley en Tukey[bewerken]

Aan de hand van het algoritme van Cooley en Tukey is goed te zien hoe een discrete fouriertransformatie van dimensie 2n gereduceerd kan worden tot 2 transformaties van dimensie n.

Laat (x_0, \ldots, x_{2n-1}) een discreet signaal zijn van dimensie 2n. De DFT van dit signaal is:

X_m =\sum_{k=0}^{2n-1} x_k \, e^{-\frac{2\pi i}{2n}mk }=\sum_{k=0}^{2n-1} x_k w_{km}(2n),
\quad
m = 0,\ldots,2n-1

Noem de ingangsdata met even index:

x'_r = x_{2r}, \quad r = 0,\ldots,n-1

met DFT X',

en die met oneven index

x''_r = x_{2r+1}, \quad r = 0,\ldots,n-1

met DFT X''.

Dan is:


\begin{align}

X_m & =   \sum_{r=0}^{n-1} x_{2r  } w_{2r,m}(2n)
       +  \sum_{r=0}^{n-1} x_{2r+1} w_{2r+1,m}(2n) \\
    & = \sum_{r=0}^{n-1} x' _r w_{r,m}(n)
       +  w_{1,m}(n) \sum_{r=0}^{n-1} x''_r w_{r,m}(n)\\
& =  
\begin{cases}
 X'_m     +  w_{1,m}(n)  X''_m     & \text{ als } m<n \\
 X'_{m-n} -  w_{1,n-m}(n)X''_{m-n} & \text{ als } m \geq n
\end{cases}

\end{align}

Merk ook op dat de wegingsfactoren w_{r,m}(n) slechts eenmaal berekend hoeven te worden voor de beide n-dimensionale transformaties.

Zie ook[bewerken]