Fast Fourier transform: verschil tussen versies

Verwijderde inhoud Toegevoegde inhoud
Hansblomme (overleg | bijdragen)
kGeen bewerkingssamenvatting
-/- Engelse ziekte, kleine aanpassingen
Regel 1:
De '''FFTFast Fourier Transform''' ('''F'''ast"snelle '''F'''ourierFouriertransformatie", afgekort tot '''TFFT'''ransform) is een [[algoritme]] waarmee een (discrete) [[Fourier transformatieFouriertransformatie]] van een signaal (array) met N punten uitgerekend kan worden met een efficiëntie van '''O(NlogN)'''. De recht-toe-rechtaan berekening van de Fourier TransformatieFouriertransformatie levert een '''O(N<sup>2</sup>)''' algoritme op. De tijdwinst die hiermee gemoeid kan zijn is voor grote N dramatischzeer groot.
 
Het algoritme komt er in kort bestek op neer dat een [[Fourier transformatieFouriertransformatie]] met lengte N wordt gesplitst in twee transformaties met lengte N/2. Door deze opsplitsing met [[recursie]]f toe te passen ontstaat een verbetering van
N/log<sub>2</sub>N. Voor N=8192 is dat al een factor 630...
 
Een zo toegepaste recursie impliceert een lengte die altijd een macht van 2 is.
In zijn eerste vorm, als ontwikkeld door Cooley en Tukey, kon de FFT inderdaad alleen gebruikt worden als het aantal punten een macht van 2 was. Later is dit gegeneraliseerd naar andere [[priemfactor]]en, waardoor een meer algemene toepasbaarheid ontstond. Als het aantal punten een grote priemfactor heeft, kan dit echter zeer nadelige gevolgen hebben voor de rekentijd. Voor praktische toepassing zoals in [[signaalanalyse]] heeft de 'alleen-beperking tot machten- van-twee- beperking'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.
 
zieZie ook [[Fourieranalyse|Fourier analyse]].
 
[[Categorie:Algoritme]]