12.4 Comparații de viteze și precizie
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:
Ecuația 12-1 Timp de execuție a DFT.
Timpul necesar pentru a calcula o DFT prin corelație este proporțional cu lungimea la pătrat a DFT.
unde N este numărul de puncte din DFT și kDFT este o constantă de proporționalitate. Dacă valorile sinus și cosinus sunt calculate în buclele imbricate, kDFT 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, kDFT 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 Log2N există N/2 calcule butterfly. Aceasta înseamnă că timpul de execuție pentru program este aproximat de:
Ecuația 12-2 Timp de execuție a FFT.
Timpul necesar pentru a calcula o DFT utilizând FFT este proporțional cu N multiplicat cu logaritm din N.
Valoarea lui kFFT 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ă NLog2N este mai mic decât N2, 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ă.
Figura 12-8 Timpi de execuție pentru calcularea DFT.
Metoda corelației se referă la algoritmul descris în Tabelul 12-2. Această metodă poate fi făcută mai rapidă prin precalcularea valorilor sinus și cosinus și stocarea lor într-un tabel look-up (LUT). FFT (Tabelul 12-3) este cel mai rapid algoritm când DFT este mai mare de 16 puncte lungime. Timpii arătați sunt pentru un procesor Pentium la 100 MHz.
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