Transformarea rapidă Fourier (FFT) este un algoritm complex, iar detaliile sale sunt de obicei studiate de cei implicați în procesarea semnalelor digitale. Această secțiune descrie principiile generale ale operațiunii FFT bazate pe utilizarea numerelor complexe. Dacă aveți experiență care lucrează în matematică complexă, veți înțelege cu ușurință adevăratul sens al algoritmului. Nu vă faceți griji dacă ni s-au scăpat câteva detalii: puțini oameni de știință și ingineri care folosesc FFT pot scrie un program de la zero.
În domeniul frecvenței și al timpului, semnalul este reprezentat de puncte N complexe. Fiecare dintre aceste puncte este format din două numere: părțile reale și imaginare. De exemplu, atunci când vorbim despre un număr de X integrat [42], este o combinație de Rex [42] și IMx [42]. După înmulțirea a două variabile complexe, este necesar să se combine patru componente separate în două. O discuție ulterioară cu tema "Cum funcționează FFT" utilizează termeni specifici: semnalul, punctul, numărul și valoarea reprezintă o combinație de părți reale și imaginare.
FFT funcționează odată cu descompunerea intervalului de timp N al semnalului în n-goluri de semnal de timp N, fiecare dintre ele constituind un singur punct. A doua etapă este de a calcula spectrele de frecvență N corespunzătoare acestor intervale de timp. După aceasta, un spectru de frecvență unic este sintetizat pe baza spectrelor N.
Figura 12.2 prezintă un exemplu de împărțire a domeniului de timp utilizând un FFT. În acest exemplu, un semnal de 16 puncte este descompus în patru componente separate. Primul pas este împărțirea semnalului de 16 puncte în două semnale de 8 puncte. În a doua etapă, aceste semnale sunt descompuse în patru semnale în 4 puncte. Această procedură continuă până la formarea semnalelor N formate dintr-un singur punct. Descompunerea interline se utilizează atunci când se împarte semnalul de eșantion în două probe. Semnalul este împărțit atât pentru eșantioane paralele, cât și pentru eșantioane. În sistem, sunt realizate etape de 2 N în expansiune, adică la semnalul de 16 puncte (2 4) cuprinde patru faze 512 puncte (2 7) necesită 7 etape, punctul 4096 (2 12) cuprinde 12 etape, etc. Amintiți-vă, această valoare - aceasta va fi găsită de mai multe ori în acest capitol.
Figura 12.2 - Procedura semnalului separat
Acum că structura descompunerii este de înțeles, ea poate fi mult simplificată. Descompunerea nu este altceva decât o redistribuire a probelor de semnal. Acest lucru este ilustrat în figura 12.3. În stânga sunt numerele eșantioanelor semnalului original, împreună cu echivalentele lor binare. În dreapta, numerele modificate, precum și echivalentele lor binare. Ideea este că numerele binare sunt inverse unele de altele. De exemplu, numărul de numere 3 (0011) poate fi obținut din numărul de referință 12 (1100). Contorul nr. 14 (1110) este obținut din proba nr. 7 (0111) și așa mai departe. Partiționarea domeniului de timp într-un FFT se face de obicei folosind algoritmul de sortare a biților inversați. Aceasta implică schimbarea domeniului N timp, un număr în format binar și inversând biții de la stânga la dreapta (de exemplu, coloana din dreapta din Fig. 12.3).
Figura 12.3 - Procedura de redistribuire a eșantioanelor de semnal
Următorul pas în algoritmul FFT este de a găsi frecvența spectrului de semnal unic determinat în domeniul de timp. Acest lucru este făcut elementar: spectrul unui semnal cu un singur punct este egal cu el însuși. Aceasta înseamnă că la acest pas nu este nevoie de nimic. Deși nu trebuie uitat că fiecare dintre semnalele cu un singur punct reprezintă acum un spectru de frecvență, mai degrabă decât un semnal de domeniu temporal
Ultimul pas în FFT este de a combina spectrele de frecvență N în ordine inversă în ceea ce privește divizarea timpului. În acest caz, algoritmul nu funcționează corect. Din păcate, conversia rapidă inversă nu se aplică și trebuie să ne întoarcem la un moment dat. În prima etapă, 16 spectre de frecvență unică sunt combinate în 8 spectre de frecvență cu câte 2 puncte fiecare. În a doua etapă, 8 spectre de frecvență sunt sintetizate în 4 spectre și așa mai departe. În ultima etapă, obținem rezultatul FFT ca un spectru de frecvență de 16 puncte.
Figura 12.4 prezintă modul în care cele două spectre de frecvență, fiecare compus din 4 puncte, sunt combinate într-un singur interval de frecvență cu 8 puncte. Sindicatul ar trebui să excludă aceleași extinderi în domeniul temporal. Cu alte cuvinte, operația în domeniul frecvenței trebuie să corespundă operației din domeniul temporal, cu excepția intersecțiilor. Luați în considerare două semnale de domeniu temporal. 8 puncte de semnal de sincronizare formirutesya în două etape: 4 diluție a fiecărui semnal punctului zero pentru a obține un semnal de 8 puncte, iar apoi se combină semnalele împreună. Prin urmare, semnalul 1 devine a0b0c0d0. și 2 devine 0e0f0g0h. Rezumarea acestor două semnale oferă un semnal de 8 puncte aebfcgdh. După cum se arată în Fig. 12.4, adăugarea realizării timpului a semnalului cu zerouri corespunde dublării spectrului de frecvență. Astfel, spectrele de frecvență din FFT sunt duplicate și apoi se adaugă una la cealaltă.
Figura 12.4 - Procedura de sintetizare a spectrului de frecvență al unui semnal
Pentru a obține consistență, cele două semnale din domeniul timpului sunt diluate cu zerouri într-o formă ușor diferită. Într-un singur semnal, probele impare sunt zero, iar în celălalt semnal probele uniforme sunt zero. Cu alte cuvinte, unul din semnalele domeniului timp (0e0f0g0h în Figura 12.4) este deplasat spre dreapta cu un număr. Această schimbare de domeniu de timp corespunde multiplicării cu spectrul sinusoidal. Pentru a vedea acest lucru, amintiți-vă că o schimbare în domeniul timpului este echivalentă cu convoluția unui semnal cu o funcție delta deplasată. Spectrul funcției delta deplasate este un sinusoid.
Figura 12.5 prezintă schema combinării a două spectre în 4 puncte într-un spectru de 8 puncte. Rețineți că Fig. 12.5 este format conform schemei de bază din figura 12.6 cu repetarea din nou și din nou.
Figura 12.5 - schemă de combinare a unui spectru de 4 puncte în 8 puncte.