FFT este un algoritm complicat, iar detaliile sale sunt lăsate de obicei celor care se specializează în astfel de lucruri. Această secțiune descrie funcționarea generală a FFT, dar ocolește o problemă cheie: utilizarea numerelor complexe. Dacă aveți o bază în matematică complexă, puteți citi între linii pentru a înțelege natura adevărată a algoritmului. Nu vă faceți griji dacă detaliile vă scapă; puțini oameni de știință și ingineri care folosesc FFT ar putea scrie programul de la zero.

În notația complexă, domeniile timp și frecvență conțin fiecare un semnal alcătuit din N puncte complexe. Fiecare dintre aceste puncte complexe este compus din două numere, partea reală și partea imaginară. De exemplu, atunci când vor-bim despre eșantionul complex X[42], se referă la combinația dintre ReX[42] și ImX[42]. Cu alte cuvinte, fiecare variabi-lă complexă deține două numere. Când se înmulțesc două variabile complexe, cele patru componente individuale trebuie combinate pentru a forma cele două componente ale produsului (cum ar fi în ecuația 9-1). Următoarea discuție pe tema "Cum funcționează FFT" folosește acest jargon de notație complexă. Adică, termenii singulari: semnal, punct, eșantion, și valoare se referă la combinația dintre partea reală și partea imaginară.

FFT funcționează prin descompunerea unui semnal din domeniu timp de N puncte în N semnale din domeniu timp fiecare compus dintr-un singur punct. A doua etapă este de a calcula cele N spectre de frecvență corespunzătoare la aceste N semnale din domeniu timp. La urmă, cele N spectre sunt sintetizate într-un singur spectru de frecvență.

Figura 12-2 prezintă un exemplu de descompunere a domeniului timp utilizat în FFT. În acest exemplu, un semnal de 16 puncte este descompus prin patru etape separate. Prima etapă împarte semnalul de 16 puncte în două semnale, fiecare alcătuit din 8 puncte. A doua etapă descompune datele în patru semnale de 4 puncte. Acest model continuă până când există N semnale compuse dintr-un singur punct. O descompunere intercalată este utilizată de fiecare dată când un semnal este rupt în două, adică semnalul este separat în eșantioanele sale cu numere pare și impare. Cea mai bună modalitate de a înțelege acest lucru este prin inspectarea figurii 12-2 până când înțelegeți modelul. Există etape Log₂N necesare în această descompunere, adică un semnal de 16 puncte (2⁴) necesită 4 etape, un semnal de 512 puncte (2⁷) necesită 7 etape, un semnal de 4096 puncte (2¹²) necesită 12 etape, etc. Amintiți-vă această valoare, Log₂N; aceasta va fi menționată de mai multe ori în acest capitol.

Figura 12-2 Descompunerea FFT.
Un semnal de N puncte este descompus în N semnale ce conțin un singur punct.
Fiecare etapă utilizează descompunere intercalată, separând eșantioanele numerotate par și impar.

Figura 12-3 Sortarea inversă a biților FFT.
Descompunerea în domeniul timp a FFT poate fi implementată
prin sortarea eșantioanelor după ordinea inversată a biților.

Acum că înțelegeți structura descompunerii, aceasta poate fi mult simplificată. Descompunerea nu este altceva decât o reordonare a eșantioanelor din semnal. Figura 12-3 prezintă modelul de rearanjare necesar. În stânga, numerele eșantioanelor semnalului original sunt listate împreună cu echivalentele lor binare. În dreapta, numerele eșantioanelor rearanjate sunt listate, de asemenea, împreună cu echivalentele lor binare. Ideea importantă este că numerele binare sunt inversate reciproc. De exemplu, eșantionul 3 (0011) este schimbat cu numărul eșantionului 12 (1100). La fel, eșantionul numărul 14 (1110) este schimbat cu numărul eșantionului 7 (0111) și așa mai departe. Descompunerea domeniului timp FFT este de obicei efectuată printr-un algoritm de sortare inversată a biților. Aceasta presupune rearanjarea ordinii celor N eșantioane din domeniul timp prin numărarea în binar cu biții inversați din stânga-dreapta (cum ar fi în coloana din dreapta din Figura 12-3).

Următorul pas în algoritmul FFT este de a găsi spectrele de frecvență ale semnalelor din domeniu timp de 1 punct. Nimic nu poate fi mai ușor; spectrul de frecvență al unui semnal de 1 punct este egal cu el însuși. Aceasta înseamnă că nu este necesar să faceți acest pas. Deși nu există nici o lucrare implicată, nu uitați că fiecare dintre semnalele de 1 punct este acum un spectru de frecvență și nu un semnal din domeniu timp.

Ultimul pas în FFT este de a combina cele N spectre de frecvență în ordinea exact inversă în care a avut loc descom-punerea din domeniul timp. Acesta este locul unde algoritmul devine încurcat. Din păcate, comanda rapidă de inversare a biților nu este aplicabilă și trebuie să ne întoarcem o etapă la un moment dat. În prima etapă, 16 spectre de frecvență (câte 1 punct fiecare) sunt sintetizate în 8 spectre de frecvență (câte 2 puncte fiecare). În a doua etapă, cele 8 spectre de frecvență (câte 2 puncte fiecare) sunt sintetizate în 4 spectre de frecvență (4 puncte fiecare) și așa mai departe. Ultima etapă are ca rezultat ieșirea FFT, un spectru de frecvență de 16 puncte.

Figura 12-4 arată cum două spectre de frecvență, fiecare compus din 4 puncte, sunt combinate într-un singur spectru de frecvență de 8 puncte. Această sinteză trebuie să anuleze descompunerea intercalată efectuată în domeniul timp. Cu alte cuvinte, operarea domeniului frecvență trebuie să corespundă procedurii din domeniu timp de combinare a două semnale de 4 puncte prin intercalare. Considerați două semnale din domeniu timp, abcd și efgh. Un semnal din domeniul timp de 8 puncte poate fi format prin două etape: diluați fiecare semnal de 4 puncte cu zerouri pentru a-l face semnal de 8 puncte, apoi adunați semnalele împreună. Adică, abcd devine a0b0c0d0, iar efgh devine 0e0f0g0h. Adunarea acestor două semnale de 8 puncte produce aebfcgdh. După cum se arată în figura 12-4, diluarea domeniului timp cu zerouri corespunde unei dublări a spectrului de frecvență. Prin urmare, spectrele de frecvență sunt combinate în FFT prin duplicarea lor, și apoi adunate spectrele duplicate împreună.

Figura 12-4 Sinteza FFT.
Când un semnal din domeniul timp este diluat cu zerouri, domeniul frecvență este duplicat. Dacă semnalul din domeniul timp este și deplasat cu un eșantion pe durata diluției, spectrul va fi multiplicat suplimentar cu o sinusoidă.

Pentru a se potrivi când este adunate, cele două semnale din domeniul timp sunt diluate cu zerouri într-un mod ușor diferit. Într-un semnal, punctele impare sunt zero, în timp ce în celălalt semnal, punctele pare sunt zero. Cu alte cuvinte, unul din semnalele din domeniul timp (0e0f0g0h din Figura 12-4) este deplasat spre dreapta cu un eșantion. Această deplasare în domeniu timp corespunde multiplicării spectrului cu o sinusoidă. Pentru a vedea acest lucru, amintiți-vă că o deplasare în domeniul timp este echivalentă cu convoluția semnalului cu o funcție delta deplasată. Aceasta multiplică spectrul semnalului cu spectrul funcției delta deplasate. Spectrul unei funcții delta deplasate este o sinusoidă (vezi Fig. 11-2).

Figura 12-5 prezintă o diagramă flux pentru combinarea a două spectre de 4 puncte într-un singur spectru de 8 puncte. Pentru a reduce situația chiar mai mult, observați că figura 12-5 este formată din modelul de bază din figura 12-6 repetată și repetată.

Această simplă diagramă flux este numită fluture datorită aspectului ei înaripat. Fluturele este elementul de bază al calculului FFT, transformând două puncte complexe în două alte puncte complexe.

Figura 12-7 prezintă structura întregii FFT. Descompunerea domeniului timp se realizează cu un algoritm de sortare inversă a biților. Transformarea datelor descompuse în domeniul frecvență nu implică nimic și, prin urmare, nu apare în figură.

Sinteza domeniului frecvență necesită trei bucle. Bucla exterioară trece prin etapele Log₂N (adică, fiecare nivel din Fig. 12-2, pornind de jos și deplasându-se spre partea de sus). Bucla medie trece prin fiecare dintre spectrele de frecvență individuale din etapa în care se lucrează (adică, fiecare dintre căsuțe pe oricare un nivel din Figura 12-2). Cea mai interioară buclă utilizează butterfly pentru a calcula punctele din fiecare spectru de frecvență (adică, trecând bucla prin eșantioanele din interiorul oricărei căsuțe din Figura 12-2). Căsuțele overhead din Fig. 12-7 determină indicii de început și de sfârșit pentru bucle, precum și calcularea sinusoidelor necesare în fluturi. Acum ajungem la inima acestui capitol, programele FFT reale.

Secțiunea următoare: Programe FFT