Când DFT este calculată prin corelație (ca în Tabelul 12-2), programul folosește două bucle imbricate, fiecare rulând prin N puncte. Aceasta înseamnă că numărul total de operațiuni este proporțională ori N x N. Timpul de finalizare a programului este astfel dat de:

unde N este numărul de puncte din DFT și k_DFT este o constantă de proporționalitate. Dacă valorile sinus și cosinus sunt calculate în buclele imbricate, k_DFT este egală cu aproximativ 25 microsecunde pe un Pentium la 100 MHz. Dacă pre-calculați valorile sinus și cosinus și le stocați într-un tabel de căutare, k_DFT scade la aproximativ 7 microsecunde. De exemplu, o DFT de 1024 de puncte va necesita aproximativ 25 de secunde sau aproape 25 de milisecunde pe punct. E lentă!

Folosind aceeași strategie putem deduce timpul de execuție pentru FFT. Timpul necesar pentru inversarea biților este neglijabil. În fiecare dintre etapele Log₂N există N/2 calcule butterfly. Aceasta înseamnă că timpul de execuție pentru program este aproximat de:

Valoarea lui k_FFT este de aproximativ 10 microsecunde pe un sistem Pentium de 100 MHz. O FFT de 1024 puncte necesită aproximativ 70 milisecunde pentru a executa, sau 70 de microsecunde pe punct. Acest lucru este mai mult de 300 de ori mai rapid decât DFT calculat prin corelație!

Nu numai că NLog₂N este mai mic decât N², ci crește cu mult mai lent când N devine mai mare. De exemplu, o FFT de 32 de puncte este de aproximativ zece ori mai rapidă decât metoda corelației. Dar, o FFT de 4096 puncte este de o mie de ori mai rapidă. Pentru valori mici ale lui N (de exemplu, 32 la 128), FFT este importantă. Pentru valori mari ale lui N (1024 și mai sus), FFT este absolut critică. Fig. 12-8 compară timpii de execuție ai celor doi algoritmi în formă grafică.

FFT are un alt avantaj în afară de viteza brută. FFT se calculează mai precis, deoarece numărul mai mic de calcule are ca rezultat o eroare mai mică de rotunjire. Acest lucru poate fi demonstrat prin aplicarea FFT unui semnal arbitrar, și apoi rularea spectrului de frecvență printr-o FFT Inversă. Aceasta reconstruiește semnalul inițial din domeniul timp, cu excepția adăugării zgomotului de rotunjire de la calcule. Un singur număr care caracterizează acest zgomot poate fi obținut prin calcularea deviației standard a diferenței dintre cele două semnale. Pentru comparație, aceeași procedură poate fi repetată folosind o DFT calculată prin corelație și o DFT inversă corespunzătoare. Cum se compară zgomotul de rotunjire al FFT cu DFT prin corelație? Consultați figura 12-9.

Secțiunea următoare: Creșterea vitezei în continuare