FFT staat voor Fast Fourier Transform. Het is een geoptimaliseerd algoritme voor het uitvoeren van de Fourier transformatie (genoemd naar Jean-Baptiste Joseph Fourier).
De normale (langzame) DFT (Discrete Fourier Transform) is een N-kwadraat-algoritme. Dat wil zeggen dat je N maal N bewerkingen moet uitvoeren: het aantal inputsamples maal het aantal output-harmonischen.
Het FFT-algoritme is vooral bij grotere aantallen inputsamples (ook wel de window size genoemd) veel efficienter: FFT is een N*log(N)-algoritme. Dat wil zeggen dat je slechts N maal de logaritme van N bewerkingen hoeft uit te voeren.
De uitkomsten van DFT en FFT zijn hetzelfde, het is gewoon een heel slimme truc: butterfly-unfolding; bit-reverse......