DFT poate fi calculată în trei moduri complet diferite. În primul rând, problema poate fi abordată ca un set de ecuații simultane. Această metodă este utilă pentru a înțelegere DFT, dar este prea ineficientă pentru a fi de folos practic. A doua metodă aduce o idee din ultimul capitol: corelația. Aceasta se bazează pe detectarea unei forme de undă cunoscute într-un alt semnal. A treia metodă, numită Fast Fourier Transform (FFT), este un algoritm ingenios care descompune o DFT cu N puncte, în N DFT fiecare cu un singur punct. FFT este de obicei de sute de ori mai rapidă decât celelalte metode. Primele două metode sunt discutate aici, în timp ce FFT este subiectul capitolului 12. Este important să rețineți că toate cele trei metode produc o ieșire identică. Ce ar trebui să utilizați? În practica actuală, corelația este tehnica preferată dacă DFT are mai puțin de aproximativ 32 de puncte, în caz contrar se folosește FFT.

DFT prin ecuații simultane

Gândiți-vă la calculul DFT în modul următor. Vă sunt date N valori din domeniul timp și ați cerut să calculați N valori din domeniul frecvență (ignorând cele două valori din domeniul frecvență pe care le cunoașteți că trebuie să fie zero). Algebra de bază oferă răspunsul: pentru a rezolva pentru N necunoscute, trebuie să puteți scrie N ecuații independente liniare. Pentru aceasta, luați primul eșantion din fiecare sinusoid și adunați-le împreună. Suma trebuie să fie egală cu primul eșantion din semnalul domeniului timp, asigurând astfel prima ecuație. De asemenea, o ecuație poate fi scrisă pentru fiecare dintre punctele rămase din semnalul domeniului timp, rezultând N ecuații. Soluția poate fi apoi găsită utilizând metode stabilite pentru rezolvarea ecuațiilor simultane, cum ar fi Eliminarea Gauss. Din păcate, această metodă necesită un număr imens de calcule și practic nu este niciodată utilizată în DSP. Totuși, este importantă pentru un alt motiv, se arată de ce este posibil să se descompună un semnal în sinusoide, cât de multe sinusoide sunt necesare, și că funcțiile de bază trebuie să fie liniar independente (mai multe despre acest lucru în scurt timp).

DFT prin corelație

Să trecem la o modalitate mai bună, modul standard de calcul al DFT. Un exemplu va arăta modul în care funcționează această metodă. Să presupunem că încercăm să calculăm DFT a unui semnal de 64 de puncte. Aceasta înseamnă să calculăm cele 33 de puncte din partea reală și cele 33 de puncte din partea imaginară a domeniului frecvență. În acest exemplu vom arăta doar cum se calculează un singur eșantion, ImX[3], adică amplitudinea undei sinus care face trei cicluri complete între punctul 0 și punctul 63. Toate celelalte valori ale domeniului frecvență sunt calculate într- manieră similară.

Figura 8-8 ilustrează utilizarea corelației pentru a calcula ImX[3]. Figurile (a) și (b) prezintă două semnale din domeniul timp, numite: x1[ ] și x2[ ], respectiv. Primul semnal, x1[ ], este compus numai dintr-o undă sinus care face trei cicluri între punctele 0 și 63. În schimb, x2[ ] este compus din mai multe unde sinus și cosinus, dintre care nici una nu face trei cicluri între punctele 0 și 63. Aceste două semnale ilustrează ce face algoritmul pentru calculul ImX[3]. Când a fost introdus x1[ ], algoritmul trebuie să producă o valoare de 32, amplitudinea undei sinusoidale prezente în semnal (modificată de factorii de scalare din Ec. 8-3). În comparație, atunci când algoritmul este alimentat cu celălalt semnal, x2[ ], trebuie să se producă o valoare zero, indicând faptul că această undă sinus nu este prezentă în acest semnal.

Conceptul de corelație a fost introdus în Capitolul 7. Pe scurt, pentru a detecta o formă de undă cunoscută conținută într-un alt semnal, înmulțiți cele două și adunați punctele din produsul rezultat. Singurul număr care rezultă din această procedură este o măsură a modului în care sunt similare cele două semnale. Figura 8-8 ilustrează această abordare. Figurile (c) și (d) afișează semnalul pe care îl căutăm, o undă sinus care face 3 cicluri între eșantioanele 0 și 63. Figura (e) arată rezultatul multiplicării (a) și (c). De asemenea, (f) arată rezultatul multiplicării (b) și (d). Suma tuturor punctelor din (e) este 32, în timp ce suma tuturor punctelor din (f) este zero, arătând că am găsit algoritmul dorit.

Celelalte eșantioane din domeniul frecvență sunt calculate în același mod. Această procedură este formalizată în ecuația de analiză, metoda matematică de calculare a domeniului frecvență din domeniul timp:

În cuvinte, fiecare eșantion din domeniul frecvență se găsește prin înmulțirea semnalului din domeniul timp cu unda sinus sau cosinus care este căutată și adunarea punctelor rezultate. Dacă cineva vă întreabă ce faceți, spuneți cu încredere: "Corelez semnalul de intrare cu fiecare funcție de bază". Tabelul 8-2 prezintă un program de calculator pentru calculul DFT în acest mod.

Ecuația de analiză nu necesită o manipulare specială a primului și ultimului punct, ca și ecuația de sinteză. Există, totuși, un semn negativ în partea imaginară din Ec. 8-4. La fel ca înainte, acest semn negativ face ca DFT reală să fie în concordanță cu DFT complexă și nu este întotdeauna inclus.

Figura 8-8

Două exemple de semnale, (a) și (b), sunt analizate pentru conținutul funcției de bază specifică arătată în (c) și (d). Figurile (e) și (f) arată rezultatul multiplicării fiecărui exemplu de semnal cu funcția de bază. Figura (e) are o medie de 0,5, indicând că x1[ ] conține funcția de bază cu o amplitudine de 1,0. Invers, (f) are o medie zero, indicând că x2[ ] nu conține funcția de bază.

Pentru ca acest algoritm de corelare să funcționeze, funcțiile de bază trebuie să aibă o proprietate interesantă: fiecare dintre ele trebuie să fie complet necorelată cu toate celelalte. Aceasta înseamnă că dacă multiplicați oricare două dintre funcțiile de bază, suma punctelor rezultate va fi egală cu zero. Funcțiile de bază care au această proprietate sunt numite ortogonale. Multe altele funcții ortogonale de bază există, inclusiv: undei pătrate, unde triunghiulare, impulsuri etc. Semnalele pot fi descompuse în aceste alte funcții de bază ortogonale utilizând corelația, la fel ca aici cu sinusoide. Acest lucru nu înseamnă că acest lucru este util, ci doar că este posibil.

Așa cum am arătat anterior în Tabelul 8-1, DFT Inversă are două moduri de a fi implementată într-un program de calculator. Această diferență implică schimbarea buclelor interioare și exterioare în timpul sintezei. În timp ce acest lucru nu schimbă ieșirea din program, el face o diferență în ceea ce privește modul în care vedeți ce se face. Programul DFT din Tabelul 8-2 poate fi, de asemenea, schimbat în acest mod, prin schimbarea buclelor interioare și exterioare în liniile 310-380. La fel ca înainte, ieșirea programului este aceeași, dar modul în care vă gândiți la calcul e diferit. (Aceste două modalități diferite de vizualizare a DFT și DFT inversă ar putea fi descrise ca algoritmi "partea de intrare" și "partea de ieșire", la fel ca pentru convoluție).

Așa cum este scris programul din Tabelul 8-2, el descrie modul în care un eșantion individual din domeniul frecvență este afectat de toate eșantioanele din domeniul timp. Adică programul calculează fiecare dintre valorile din domeniul frecvență succesiv, nu ca grup. Când se schimbă buclele interioare și exterioare, programul buclează prin fiecare eșantion în domeniul timp, calculând contribuția acelui punct la domeniul frecvență. Domeniul frecvență general se găsește prin adăugarea contribuțiilor din punctele individuale ale domeniului timp. Aceasta ne aduce întrebarea următoare: ce fel de contribuție oferă un eșantion individual din domeniul timp la domeniul frecvență? Răspunsul este conținut într-un aspect interesant al domeniului Fourier numit dualitate.

Secțiunea următoare: Dualitate