De Fast Fourier Transform
Directe implementatie van de DFT van N samples veronderstelt het uitvoeren van een
complexe matrix van NxN elementen en dus N² bewerkingen. Wanneer echter het aantal
samples een macht van 2 is, of m.a.w.
N = 2 p
dan kan het aantal bewerkingen herleid worden tot N.log2(N)
.Dit maakt de berekening véél sneller en zeer efficient in geheugengebruik van de
computer.
Dit turbo algoritme staat bekend in de literatuur als de Fast Fourier Transform of
kortweg FFT. Er zijn echter vele varianten op deze techniek bekend , de meeste zijn
geïmplementeerd in vele computertalen zoals Visual Basic, C, Labview (welke wij hier
gebruiken in de voorbeelden) enz. Wij gebruiken derhalve uitsluitend dit algoritme in onze
voorbeelden.
Zero padding
Wat als de grootte van de sampel geen macht van 2 is, is er geen fft? Toch wel. Men
voegt dan nullen toe op het einde van de sample tot het aantal elementen een macht van
twee is. Deze operatie verandert het spectrum van het signaal niet!! Bovendien, niet
alleen verloopt de berekening veel vlugger maar ook de spectrale resolutie wordt beter
immers df = fs/N en N neemt toe door padding met nullen.