De Fast Fourier Transformatie
Rob Bisseling
In dit eerstejaars prakticum wordt gekeken
naar de zgn. Fourier Transformatie.
Met deze transformatie kan een signaal worden omgevormd
in frequentiecomponenten.
Dit kan echter alleen als het signaal in stukjes gehakt is:
het moet gesampled (bemonsterd) zijn.
Ge-sample-de signalen kom je vooral tegen in de vorm
van beeld en geluid op een computer.
Hier vindt de Fourier Transformatie dan ook een ruime toepassing.
En het spreekt voor zich, dat een grote snelheid zeer gewenst is.
De Discrete Fourier Transformatie (DFT)
In eerste instantie wordt gekeken naar een recht-toe-recht-aan
benadering van het algoritme.
De wiskundige formule wordt rechtstreeks omgezet in C- of Java code.
Dit levert een programma, dat 2048 sample-punten in 26,9 seconden
kan transformeren. (Op een Sun Sparcstation 10 voor een C-programma.)
In Java gaat het wel wat trager.
De Fast Fourier Tranformatie (FFT)
Na de DFT, wordt de FFT bekeken. De FFT doet precies hetzelfde als de DFT, maar dan sneller. Dit komt doordat de formule eerst in een zodanige vorm wordt herschreven, dat het zich veel beter leent voor grootschalig rekenwerk. Het programma transformeert nu dezelfde 2048 punten in 0,25 seconde. Dat is dus 100 keer zo snel. En naarmate er meer sample-punten zijn, zal deze factor alleen nog maar toenemen.
Toepassing
Bij het praktikum wordt er ook nog aan een toepassing gewerkt. Iedereen neemt een stukje geluid op met de computer, en bewerkt dat signaal daarna.
Eindverslag
Het eindverslag wordt op de traditionele manier
in LaTeX geschreven of, minder conventioneel in HTML.
In het laatste geval kunnen ook interactieve
Java-applets gepresenteerd worden.
Een voorbeeld van zo'n verslag is het
Verslag FFT (feb. 1997),
van Mark Stijnman, eerstejaars student Computational Science.
Zie in het bijzonder de
FFT demo applet .
Laatst bijgewerkt door Rob Bisseling op 24 februari 1997.
Rob.Bisseling@math.uu.nl