Fast Fourier transform

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.

Fourieranalyse zet een signaal om vanuit het oorspronkelijke domein (meestal tijd of ruimte) naar een voorstelling in het frequentie-domein en vice versa. De discrete fouriertransformatie bekomt men door een reeks waarden te ontbinden in componenten met verschillende frequenties. Deze bewerking is erg belangrijk voor een aantal toepassingen, maar de directe berekening is vaak te langzaam om bruikbaar te zijn. Dit wordt opgelost met de snelle fouriertransformatie.

Terwijl directe berekening een efficiëntie heeft van $O(N^{2})$, is de efficiëntie van een FFT $O(N\log _{2}N)$. 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 _{2}N$. Voor bijvoorbeeld $N=8192$ is dat al een factor 630.

Voor de toepassing 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

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

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

Zie ook

• Fourieranalyse