JW Cooley și JW Tukey sunt recunoscuți pentru aducerea FFT în lume prin lucrarea lor: "An algorithm for the machine calculation of complex Fourier Series," Mathematics Computation, Vol. 19, 1965, pp 297-301. În retrospectivă, alții au descoperit tehnica cu mulți ani înainte. De exemplu, marele matematician german Karl Friedrich Gauss (1777-1855) a folosit metoda mai mult de un secol mai devreme. Această lucrare timpurie a fost în mare parte uitată pentru că nu avea instrumentul să o facă practic: calculatorul digital. Cooley și Tukey sunt onorați pentru că au descoperit FFT la momentul potrivit, începutul revoluției computerelor.

FFT se bazează pe DFT complexă, o versiune mai sofisticată a DFT reală, discutată în ultimele patru capitole. Aceste transformate sunt numite pentru modul în care fiecare reprezintă date, adică folosind numere complexe sau folosind numere reale. Termenul de complex nu înseamnă că această reprezentare este dificilă sau complicată, dar că se folosește un anumit tip de matematică. Matematica complexă este adesea dificilă și complicată, dar nu de aici vine numele. Capitolul 29 discută DFT complexă și oferă baza necesară pentru a înțelege detaliile algoritmului FFT. Subiectul acestui capitol este mai simplu: cum se utilizează FFT pentru a calcula DFT reală, fără a se îneca într-o mlaștină a matematicii avansată.

Figura 12-1 Compararea DFT reală cu DFT complexă.

DFT reală ia un semnal de N puncte din domeniul timp și creează două semnale de N/2 + 1 puncte în domeniul frecvență. DFT complexă ia două semnale de N puncte din domeniul timp și creează două semnale de N puncte în domeniul frecvență. Regiunile hașurate încrucișat arată valoarea comună a celor două transformate.

Deoarece FFT este un algoritm pentru calculul DFT complexe, este important să înțelegem cum se transferă datele DFT reale în și din formatul DFT complexă. Figura 12-1 compară modul în care DFT reală și DFT complexă stochează datele. DFT reală transformă un semnal din domeniu timp de N puncte în două semnale din domeniu frecvență de N/2 + 1 puncte. Semnalul din domeniul timp este numit chiar așa: semnalul din domeniul timp. Cele două semnale din domeniul frecvență se numesc partea reală și partea imaginară, care dețin amplitudinile undelor cosinus, respectiv, undelor sinus. Acest lucru ar trebui să fie foarte familiar din capitolele trecute.

În comparație, DFT complexă transformă două semnale din domeniu timp de N puncte în două semnale din domeniu frecvență de N puncte. Cele două semnale din domeniu timp se numesc partea reală și partea imaginară, la fel ca semnalele din domeniu frecvență. În ciuda numelor lor, toate valorile din aceste tablouri sunt doar numere obișnuite. (Dacă sunteți familiarizați cu numere complexe: j-urile nu sunt incluse în valorile matricei, ele fac parte din matematică. Rețineți că operatorul Im ( ) generează un număr real).

Să presupunem că aveți un semnal de N puncte, și trebuie să se calculeze DFT reală prin intermediul DFT complexă (cum ar fi prin utilizarea algoritmului FFT). Mai întâi, mutați semnalul de N puncte în partea reală a domeniului timp a DFT complexă, apoi setați toate eșantioanele din partea imaginară la zero. Calculul DFT complexă are ca rezultat un semnal real și un semnal imaginar în domeniul frecvență, fiecare compus din N puncte. Eșantioanele 0 până la N/2 ale acestor semnale corespund spectrului DFT reală.

Așa cum am discutat în Capitolul 10, domeniul frecvență al DFT este periodic când sunt incluse frecvențele negative (vezi Fig. 10-9). Alegerea unei singure perioade este arbitrară; ea poate fi aleasă între -1,0 și 0, -0,5 și 0,5, 0 și 1,0, sau orice alt interval unitate raportat la rata de eșantionare. Spectrul de frecvență al DFT complexe include frecvențele negative din aranjamentul de la 0 la 1.0. Cu alte cuvinte, o perioadă întreagă se întinde de la eșantionul 0 la eșantionul N -1, corespunzând cu 0 până la de 1,0 ori rata de eșantionare. Frecvențele pozitive se situează între eșantionul 0 și N/2, corespunzând cu 0 până la 0,5. Celelalte eșantioane, între N/2 + 1 și N - 1, conțin valorile de frecvență negative (care sunt de obicei ignorate).

Calculul unei DFT inverse reale folosind o DFT inversă complexă este un pic mai greu. Acest lucru se datorează faptului că trebuie să vă asigurați că frecvențele negative sunt încărcate în formatul corect. Amintiți-vă că punctele de la 0 la N/2 din DFT complexă sunt aceleași ca în DFT real, atât pentru părțile reale, cât și pentru cele imaginare. Pentru partea reală, punctul N/2 + 1 este același ca și la punctul N/2 - 1, punctul N/2 + 2 este același ca și la punctul N/2 - 2, etc. Acest lucru continuă până la punctul N -1 fiind același ca și punctul 1. Același model de bază este folosit pentru partea imaginară, cu excepția faptului că semnul este schimbat. Adică, punctul N/2 + 1 este negativul punctului N/2 - 1, punctul N/2 + 2 este negativul punctului N/2 - 2, etc. Observați că eșantioanele 0 și N/2 nu au un punct de potrivire în această schemă de duplicare. Utilizați figura 10-9 pentru a înțelege această simetrie. În practică, încărcați spectrul de frecvență al DFT reală în eșantioanele 0 la N/2 din matricele DFT complexe și apoi utilizați o subrutină pentru a genera frecvențele negative între eșantioanele N 2 + 1 și N-1. Tabelul 12-1 prezintă un astfel de program. Pentru a verifica dacă este prezentă simetria corespunzătoare, după ce ați aplicat FFT inversă, uitați-vă la partea imaginară a domeniului timp. Va conține toată zerouri dacă totul este corect (cu excepția câtorva părți-pe-milion de zgomot, folosind calcule de simplă precizie).

Secțiunea următoare: Cum funcționează FFT