Versie van 30 mrt 2012 06:41 bewerken ErikvanB (overleg \| bijdragen) uitgebreid bevestigde gebruikers, Terugdraaiers 548.640 bewerkingen conform discrete fouriertransformatie ← Oudere bewerking		Versie van 30 mrt 2012 08:32 bewerken ongedaan maken ErikvanB (overleg \| bijdragen) uitgebreid bevestigde gebruikers, Terugdraaiers 548.640 bewerkingen Geen bewerkingssamenvatting Nieuwere bewerking →
Regel 2: 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>) 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 ~~gebruik gemaakt~~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. ~~N/log<sub>2</sub>N. Voor N=8192 is dat al een factor 630.~~ Een zo toegepaste recursie vereist dat N een macht van 2 is.

Fast Fourier transform: verschil tussen versies