Vad är en snabb Fouriertransform?

En snabb Fouriertransform är en effektiv algoritm för att arbeta ut diskreta fouriertransformen - som i sig är en Fourier omformar på "diskreta" data, som kan hållas på en dator. Jämför detta till en "kontinuerlig Fourier omformar' på, säg, en kurva. Man skulle behöva en oändlig mängd datapunkter som verkligen representerar en kurva, något som inte kan göras med en dator.

Kolla in: The Scientist och ingenjörens Guide till Digital signalbehandling. Det är en gratis, nedladdningsbara bok som behandlar, bland annat Fourier transformer; kapitel 8-12 är nära förbunden med din fråga. Detta är en mycket praktisk, yer-ärmar-summera boka, som titeln säger, forskare och ingenjörer, men Smith beskriver den bakomliggande teorin bra. Exempelkoden medföljer boken är i BASIC och FORTRAN, av alla saker; författaren gör detta för didaktiska ändamål göra exemplen lätt att förstå i stället för effektiv.