Așa cum am discutat în capitolul 8, DFT reală poate fi calculată prin corelarea semnalului din domeniul timp cu unde sinus și cosinus (vezi Tabelul 8-2). Tabelul 12-2 prezintă un program pentru a calcula DFT complexă prin aceeași metodă. Într-o comparație mere-cu-mere, acesta este programul pe care FFT se îmbunătățește.

Tabelele 12-3 și 12-4 prezintă două programe FFT diferite, unul în FORTRAN și unul în BASIC. În primul rând vom examina rutina BASIC din Tabelul 12-4. Această subrutină produce exact aceeași ieșire ca și tehnica de corelație din Tabelul 12-2, cu excepția faptului că o face mult mai rapid. Diagrama bloc din Fig. 12-7 poate fi utilizată pentru identificarea diferitelor secțiuni ale acestui program. Datele sunt transmise la această subrutină FFT în matricele: REX[ ] și IMX[ ], fiecare executând de la eșantionul 0 la N-1. La revenirea din subrutină, REX[ ] și IMX[ ] sunt suprascrise cu datele domeniului frecvență. Acesta este un alt mod în care FFT este extrem de optimizată; aceleași matrici sunt utilizate pentru intrare, stocare intermediară și ieșire. Această utilizare eficientă a memoriei este importantă pentru proiectarea hardware-ului rapid pentru a calcula FFT. Termenul de calcul local este utilizat pentru a descrie această utilizare a memoriei.

În timp ce toate programele FFT produc același rezultat numeric, există variații subtile în programare pe care trebuie să le priviți. Câteva dintre aceste diferențe importante sunt ilustrate de programul FORTRAN listat în Tabelul 12-3. Acest program utilizează un algoritm numit decimare în frecvență, în timp ce algoritmul descris anterior este numit decimare în timp. Într-un algoritm decimare în frecvență, sortarea inversării biților se face după cele trei bucle imbricate. Există, de asemenea, rutine FFT care elimină complet sortarea inversării biților. Nici una dintre aceste variante nu îmbunătățește semnificativ performanța FFT și nu trebuie să vă faceți griji cu privire la care dintre ele utilizați.

Diferențele importante dintre algoritmii FFT privesc modul în care sunt transmise datele către și de la subrutine. În programul BASIC, datele intră și părăsesc subrutina în matricele REX[ ] și IMX[ ], cu eșantioane care rulează de la indexul 0 la N -1. În programul FORTRAN, datele sunt transmise în matricea complexă X( ), cu eșantioanele rulând de la 1 la N. Deoarece aceasta este o matrice de variabile complexe, fiecare eșantion din X( ) constă din două numere, o parte reală și o parte imaginară. Lungimea DFT trebuie, de asemenea, trecută la aceste subrutine. În programul BASIC, variabila N% este utilizată în acest scop. În comparație, programul FORTRAN utilizează variabila M, care este definită ca egală cu Log₂N. De exemplu, M va fi 8 pentru un DFT de 256 de puncte, 12 pentru un DFT de 4096 puncte, etc. Ideea este că programatorul care scrie o subrutină FFT are multe opțiuni pentru interfața cu programul gazdă. Șirurile care rulează de la 1 la N, cum ar fi în programul FORTRAN, sunt deosebit de agravante. Cea mai mare parte a literaturii DSP (inclusiv această lucrare) explică algoritmii presupunând că șirurile rulează de la eșantionul 0 la N -1. De exemplu, dacă șirurie rulează de la 1 la N, simetria în domeniul frecvență se situează în jurul punctelor 1 și N/2+ 1, mai degrabă decât ​​punctele 0 și N/2.

Utilizarea DFT complexă pentru a calcula DFT reală are un alt avantaj interesant. DFT complexă este mai simetrică între domeniile timp și frecvență decât DFT reală. Adică, dualitatea este mai puternică. Printre altele, aceasta înseamnă că DFT Inversă este aproape identică cu DFT Directă. De fapt, cel mai simplu mod de a calcula o FFT Inversă este de a calcula o FFT Directă și apoi de a ajusta datele. Tabelul 12-5 prezintă o subrutină pentru calculul FFT inversă în acest mod.

Să presupunem că ați copiat unul dintre acești algoritmi FFT în programul computerului și începeți să îl executați. De unde știi dacă funcționează corect? Două trucuri sunt utilizate frecvent pentru depanare. Mai întâi, începeți cu un semnal arbitrar din domeniu timp, cum ar fi de la un generator de numere aleatoare, și rulați-l prin FFT. Apoi rulați spectrul de frecvență rezultat prin FFT Inversă și comparați rezultatul cu semnalul original. Acestea ar trebui să fie identice, cu excepția zgomotului de rotunjire (câteva părți-pe-milion pentru simplă precizie).

Al doilea test de funcționare corectă este acela că semnalele au simetria corectă. Când partea imaginară a semnalului din domeniul timp este compusă toată din zerouri (cazul normal), domeniul frecvență al DFT complexă va fi simetric în jurul eșantioanelor 0 și N/2, așa cum a fost descris anterior.

De asemenea, atunci când această simetrie corectă este prezentă în domeniul frecvență, DFT Inversă va produce un domeniu timp care are o parte imaginară compusă toată din zerouri (plus zgomotul de rotunjire). Aceste tehnici de depanare sunt esențiale pentru utilizarea FFT; familiarizați-vă cu ele.

Secțiunea următoare: Comparații de viteză și precizie