Fast Fourier transform: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
k r2.7.3) (Robot: toegevoegd: he:FFT |
Wat betekent "De Fast Fourier transform is een algoritme van de numerieke wiskunde waarmee van een discreet signaal uitgerekend kan worden"? Naar mijn idee betekent het niets, want er ontbreekt wat. |
||
Regel 1:
[[Bestand:FFT Butterfly radix8.svg|thumb|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(Nlog<sub>2</sub>N). De conventionele fouriertransformatie, die wel de [[discrete fouriertransformatie]] (DFT) wordt genoemd, levert een O(N<sup>2</sup>)
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 [[recursie]]f toe te passen ontstaat een verbetering van N/log<sub>2</sub>N. Voor N=8192 is dat al een factor 630.
| |||