Fast Fourier transform

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

De Fast Fourier transform ("snelle fouriertransformatie", afgekort tot FFT) is een algoritme van de numerieke wiskunde waarmee van een discreet signaal (dat wil zeggen waarvan waarden bekend zijn voor een eindig aantal N punten op een eindige afstand van elkaar) uitgerekend kan worden met een efficiëntie van O(Nlog2N). De conventionele fouriertransformatie, die wel de discrete fouriertransformatie (DFT) wordt genoemd, levert een O(N2)-algoritme op. De tijdwinst die hiermee gemoeid kan zijn is voor grote N zeer groot.

Het algoritme komt er in zijn oorspronkelijke vorm, ontwikkeld door James Cooley en John Tukey in 1965, 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 functies sinus en cosinus. Door deze opsplitsing recursief toe te passen ontstaat een verbetering van N/log2N. Voor N=8192 is dat al een factor 630.

Een zo toegepaste recursie 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.

Zie ook[bewerken]