Fast Fourier Transform: Forskelle mellem versioner

Den første matematiker, som anvendte FFT, var [[Gauss]] omkring 1805. Pga. af hans store grundighed nåede han, som så meget andet, ikke at publicere sine resultater. Det medførte, at de gik i glemmebogen, indtil de genopdagedes af [[James Cooley|James W. Cooley]] og [[John W. Tukey]] i 1965.

 

De hyppigst anvendte algoritmer bygger på et "del og hersk"-princip. [[Vektor (matematik)|Serien]] opdeles i to mindre serier, som derefter hver især opdeles igen ved [[Rekursiv|rekursion]], indtil man når frem til så små serier, at de nemt kan transformeres. Metoden beskrives her ved pseudo-kode.

 

:<math> \mathrm{return}\ \operatorname{fft}(\vec c) </math>

 

 

Man kan beregne fouriertransformationen for en diskret serie ved at gå ud fra udtrykket:

Hvis n eksempelvis er 1024, så reduceres antallet af trigonometriske beregninger og multiplikationer fra 1.048.576 til 10 og 10240, hhv. Alt andet lige reducerer det beregningstiden med mindst en faktor 100.

 

 

For at vise hvordan metoden virker er her et eksempel med en serie med længden 8.

I dette eksempel, hvor serien af hensyn til overskueligheden er ganske lille, er besparelsen også lille. Når serien bliver stor, bliver besparelsen større.

 

 

Den her viste metode bygger på, at længden af serien reduceres ved at dele den lige over i to halvdele. Heraf kommer kravet om, at ''n'' skal være en potens af 2.

Der er senere udviklet metoder, hvor man udnytter primfaktoropløsning af ''n''. Når ''m'' indgår som [[Faktor (matematik)|primfaktor]] i ''n'', så kan serien opdeles i ''m'' mindre serier, som hver har længden ''n / m''. Disse kan så igen opdeles, indtil længden af serierne selv bliver et [[primtal]].

 

* [[Fouriertransformation]]

* [[Vinduesfunktion]]