Cap 11 — FFT (Fast Fourier Transform): DFT calculata rapid

← inapoi la cuprins · Materie pentru examen (dupa partial) · Notitele colegilor: Cursul 16, p. 37–38 · Inainte: Cap 6 (DFT)

Ce cade: la examen FFT apare la teorie, nu la calcul. Intrebarile reale: “complexitatea Fast Fourier Transform” si “comparatie FFT cu DFT” (examen 2023 A si 2026). Raspunsurile model sunt in sectiunea 10. Daca ai doar 10 minute, citeste sectiunea 1, sectiunea 6 si sectiunea 10.

Cum citesti pagina: sectiunea 1 (de ce e DFT lenta) → sectiunea 2 (ideea, pe un exemplu cu 4 numere, facut de mana) → sectiunea 3 (de ce merge) → sectiunea 4 (schema desenata la curs, pentru $N = 8$) → sectiunea 5 (de unde vine $N\log_2 N$) → sectiunea 6 (tabelul DFT vs FFT, pentru examen).

Ce trebuie sa stii dinainte: ce este DFT si ce inseamna un numar $X(k)$ — Cap 6. Ce e $j$ si cercul pe care se invarte $e^{j\theta}$ — Cap 0 §3–4. Aici le reamintesc pe scurt, la locul unde apar.

Dupa esantionare avem o lista de $N$ numere: $x(0), x(1), \dots, x(N-1)$. Litera $n$ e numarul de ordine al esantionului, iar $N$ e cate esantioane sunt in total.

DFT transforma lista asta in alta lista, tot de $N$ numere: $X(0), X(1), \dots, X(N-1)$. Fiecare $X(k)$ spune “cat din frecventa cu numarul $k$ se afla in semnal” (Cap 6).

Reteta DFT pentru un singur $X(k)$: iei fiecare esantion, il inmultesti cu un anumit numar de pe cerc si aduni toate produsele. Hai sa numaram cata munca inseamna asta.

Luam lista $x = [1, 2, 3, 4]$, deci $N = 4$.

Numerele cu care inmultim. Pentru $N = 4$, inmultitorii sunt mereu unul din aceste 4 numere:

Sunt 4 puncte asezate pe un cerc, ca orele 3, 6, 9 si 12 pe un ceas. Un pas inseamna un sfert de tura, in sensul acelor de ceas. Dupa 4 pasi esti inapoi la $1$.

Tabelul intreg al DFT. Pe fiecare rand e un $X(k)$. In fiecare casuta e un produs: esantionul ori inmultitorul lui.

Numaram: tabelul are 4 randuri si 4 coloane, deci $4 \cdot 4 = 16$ inmultiri. In general: $N$ randuri (cate un $X(k)$) ori $N$ coloane (cate un esantion):

$$ \text{DFT directa: } N \cdot N = N^2 \text{ inmultiri} $$

Pentru 4 numere, 16 inmultiri nu sunt nimic. Problema apare cand $N$ e mare. Sa zicem ca un calculator face $1\,000\,000\,000$ ($10^9$, un miliard) de operatii pe secunda.

Uita-te la randul cu muzica: ca sa analizezi o secunda de sunet ai nevoie de doua secunde de calcul. Nu poti tine pasul cu melodia. Tot ce analizeaza semnale “pe loc” (egalizatorul din telefon, recunoasterea vocii, Wi-Fi-ul) ar fi mult prea lent cu DFT directa.

In formula FFT apare $\log_2(N)$ (“logaritm in baza 2 din N”). Suna greu, dar inseamna un lucru simplu:

$\log_2(N)$ = de cate ori poti injumatati pe $N$ pana ajungi la 1.

• $8 \to 4 \to 2 \to 1$: 3 injumatatiri, deci $\log_2(8) = 3$
• $16 \to 8 \to 4 \to 2 \to 1$: 4 injumatatiri, deci $\log_2(16) = 4$
• $1024 \to 512 \to 256 \to 128 \to 64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1$: 10 injumatatiri, deci $\log_2(1024) = 10$

Analogie: cauti un cuvant intr-un dictionar de 1024 de pagini. Nu citesti toate paginile. Deschizi la mijloc, vezi in care jumatate e cuvantul si arunci cealalta jumatate. Dupa 10 astfel de deschideri ai ramas cu o singura pagina. 1024 de pagini, dar numai 10 pasi. Asta e $\log_2$: un numar mic chiar si pentru $N$ urias.

FFT calculeaza aceleasi $X(k)$ cu aproximativ $N \cdot \log_2(N)$ operatii in loc de $N^2$. De unde vine exact aceasta formula vezi in sectiunea 5. Deocamdata, doar numerele:

Ce vezi in desen: pe orizontala e $N$ (cate esantioane are lista), pe verticala numarul de operatii. Linia rosie e DFT directa ($N^2$), linia verde e FFT ($N\log_2 N$). In stanga, pentru $N$ pana la 64: rosul urca tot mai abrupt (ajunge la 4096), verdele abia se ridica (384). In dreapta, pentru $N$ pana la 1024, pe o scara unde fiecare liniuta de pe verticala inseamna “de 10 ori mai mult”: distanta dintre cele doua linii creste mereu. La $N = 1024$ sunt $1\,048\,576$ fata de $10\,240$.

Analogie: ai de pus in ordine alfabetica un teanc mare de lucrari. Un teanc mare se sorteaza greu: cu cat e mai mare, cu atat cauti mai mult locul fiecarei foi. Mai usor: imparti teancul in doua teancuri mici, sortezi fiecare teanc mic (mult mai repede), apoi le interclasezi dintr-o singura trecere: te uiti mereu doar la foaia de deasupra a fiecarui teanc si o iei pe cea care vine prima. Doua treburi mici plus o lipire ieftina costa mai putin decat o treaba mare. FFT face exact asta cu DFT.

Cu numere. DFT directa costa $N^2$. Pentru $N = 8$: $8^2 = 64$.

• Impartim lista in doua liste de cate 4. Doua DFT de cate 4 costa $2 \cdot 4^2 = 2 \cdot 16 = 32$. Jumatate din 64!
• Mai trebuie lipite rezultatele. Vom vedea ca lipirea costa cam 8 operatii. Total: $32 + 8 = 40$, fata de 64.
• Dar si listele de cate 4 se pot imparti in liste de cate 2: $4 \cdot 2^2 = 16$, plus doua randuri de lipiri ($8 + 8$). Total: $32$.
• Si listele de cate 2 se impart in liste de cate 1. DFT unui singur numar nu costa nimic (vezi 2.2). Raman doar lipirile: $8 + 8 + 8 = 24$.

Am ajuns de la 64 la 24. Si $24 = 8 \cdot 3 = N \cdot \log_2(N)$: cate 8 operatii pentru fiecare din cele 3 injumatatiri.

Injumatatirea se opreste la liste foarte scurte. Pe acestea trebuie sa le stim pe de rost.

DFT pentru un singur numar ($N = 1$). Tabelul din 1.2 ar avea un rand si o coloana: $X(0) = x(0) \cdot 1$. Deci DFT unui singur numar este chiar numarul. Nicio operatie.

DFT pentru doua numere ($N = 2$). Fie lista $[a, b]$. Pentru $N = 2$ un pas pe cerc e jumatate de tura, deci inmultitorii sunt doar $1$ (0 pasi) si $-1$ (1 pas). Tabelul:

Deci DFT pentru doua numere = suma lor si diferenta lor:

$$ [a,\ b] \;\longrightarrow\; [a + b,\ a - b] $$

Exemple: $[1, 3] \to [1 + 3,\ 1 - 3] = [4, -2]$. Si $[2, 4] \to [2 + 4,\ 2 - 4] = [6, -2]$. Le folosim imediat.

Stim deja raspunsul corect din tabelul de la 1.2: $X = [10,\ -2 + 2j,\ -2,\ -2 - 2j]$. Acum il obtinem pe drumul scurt.

Pas 1 — imparte lista in esantioane pare si impare. “Par” si “impar” se refera la numarul de ordine $n$, nu la valoare.

• esantioanele cu $n$ par ($n = 0$ si $n = 2$): $x(0) = 1$, $x(2) = 3$ → lista para $[1, 3]$
• esantioanele cu $n$ impar ($n = 1$ si $n = 3$): $x(1) = 2$, $x(3) = 4$ → lista impara $[2, 4]$

Ce vezi in desen: in stanga lista intreaga; pe orizontala e numarul esantionului $n$, pe verticala valoarea lui. Esantioanele cu $n$ par sunt albastre, cele cu $n$ impar sunt portocalii. In mijloc si in dreapta: cele doua jumatati, fiecare cu cate 2 numere.

Pas 2 — DFT pe fiecare jumatate. Sunt liste de cate 2 numere, deci “suma si diferenta” (din 2.2):

• lista para $[1, 3]$ → $[4, -2]$. Le notam $X_{par}(0) = 4$ si $X_{par}(1) = -2$.
• lista impara $[2, 4]$ → $[6, -2]$. Le notam $X_{imp}(0) = 6$ si $X_{imp}(1) = -2$.

Pas 3 — lipeste cele doua jumatati. Regula de lipire (o explicam imediat dedesubt) foloseste inmultitorii $w_4^0 = 1$ si $w_4^1 = -j$:

Pas 4 — verificare. Am obtinut $[10,\ -2 + 2j,\ -2,\ -2 - 2j]$. E exact lista din tabelul de la 1.2. Aceleasi numere, alt drum.

Ce vezi in desen: aceiasi pasi, desenati ca o schema care se citeste de la stanga la dreapta. In stanga intra esantioanele, in ordinea: intai cele pare (albastru), apoi cele impare (portocaliu). Etajul 1 face cele doua DFT de cate 2 numere (suma si diferenta). Etajul 2 face lipirea. Cercul cu plus (⊕) aduna cele doua linii care intra in el. Cercul cu minus (⊖) scade: linia venita de sus, pe diagonala, minus linia lui. Punctul rosu inseamna “inmulteste cu numarul scris deasupra”. In dreapta ies $X(0), \dots, X(3)$.

Pentru o lista de $N$ esantioane ($N$ par):

• $X_{par}(k)$ = DFT listei formate din esantioanele cu numar par: $x(0), x(2), x(4), \dots$ (o lista de $N/2$ numere)
• $X_{imp}(k)$ = DFT listei formate din esantioanele cu numar impar: $x(1), x(3), x(5), \dots$ (tot $N/2$ numere)
• $w_N^k$ = $k$ pasi pe cerc, un pas fiind $\frac{1}{N}$ dintr-o tura (nota din 1.2)

Regula de lipire, pentru $k = 0, 1, \dots, \frac{N}{2} - 1$:

$$ \boxed{X(k) = X_{par}(k) + w_N^k \cdot X_{imp}(k)} \qquad\qquad \boxed{X\!\left(k + \tfrac{N}{2}\right) = X_{par}(k) - w_N^k \cdot X_{imp}(k)} $$

Prima formula da prima jumatate a rezultatului ($X(0), \dots, X(\frac{N}{2}-1)$). A doua da a doua jumatate ($X(\frac{N}{2}), \dots, X(N-1)$). Ambele folosesc aceleasi doua numere, $X_{par}(k)$ si $w_N^k \cdot X_{imp}(k)$. Singura diferenta e semnul.

Verificare cu exemplul ($N = 4$, deci $N/2 = 2$): pentru $k = 0$ formulele dau $X(0)$ si $X(0 + 2) = X(2)$; pentru $k = 1$ dau $X(1)$ si $X(1 + 2) = X(3)$. Exact cele 4 randuri din tabelul de lipire.

Regula de lipire sta pe doua fapte despre pasii pe cerc. Le aratam pe cercul cu 8 puncte ($N = 8$), unde se vad cel mai bine.

Ce vezi in desen: doua cercuri de raza 1. Pe orizontala e partea reala, pe verticala partea imaginara (cea cu $j$). In stanga: cele 8 puncte $w_8^0, w_8^1, \dots, w_8^7$. Pornesti din dreapta ($w_8^0 = 1$) si faci pasi de cate o optime de tura, in sensul acelor de ceas. Punctele de aceeasi culoare sunt unul in fata celuilalt, legate cu linie punctata. In dreapta: cu rosu, cele 4 puncte la care ajungi cu pasi de un sfert de tura ($w_4$). Punctele gri sunt celelalte puncte ale lui $w_8$, peste care sari.

Pe cercul din stanga, fa 4 pasi din orice punct. 4 pasi din 8 inseamna jumatate de tura, deci ajungi in punctul diametral opus. Punctul opus lui $z$ este $-z$.

• din $w_8^0 = 1$, dupa 4 pasi: $w_8^4 = -1$
• din $w_8^2 = -j$, dupa 4 pasi: $w_8^6 = j = -(-j)$
• din $w_8^1$, dupa 4 pasi: $w_8^5 = -w_8^1$ (perechea verde din desen)

Cu litere: $\;w_N^{k + N/2} = -\,w_N^k$.

La ce foloseste: de aici vine minusul din a doua formula de lipire. Pentru $X(k + \frac{N}{2})$ ar trebui inmultitorul $w_N^{k+N/2}$. Dar el este $-w_N^k$, adica acelasi numar ca la $X(k)$, cu semn schimbat. Deci nu mai faci o inmultire noua: refolosesti produsul $w_N^k \cdot X_{imp}(k)$ si doar il scazi in loc sa-l aduni.

$X_{par}$ si $X_{imp}$ sunt DFT-uri pe liste de $N/2$ numere. Pentru $N = 8$, sunt DFT-uri cu 4 puncte, deci folosesc pasi de un sfert de tura (cercul din dreapta). Cu pasi de un sfert de tura, dupa 4 pasi esti inapoi de unde ai plecat: $w_4^4 = w_4^0$, $w_4^5 = w_4^1$ si asa mai departe.

Urmarea: daca ai cere “$X_{par}(4)$”, ai folosi exact aceiasi inmultitori ca la $X_{par}(0)$, deci ai obtine acelasi numar. La fel $X_{par}(5) = X_{par}(1)$ etc.

Cu litere: $\;X_{par}(k + \tfrac{N}{2}) = X_{par}(k)$ si $X_{imp}(k + \tfrac{N}{2}) = X_{imp}(k)$.

La ce foloseste: rezultatul final are $N$ valori ($X(0), \dots, X(N-1)$), dar jumatatile au doar cate $N/2$ valori. Faptul 2 spune ca nu e nicio problema: pentru a doua jumatate a rezultatului refolosesti aceleasi $N/2$ valori ale lui $X_{par}$ si $X_{imp}$.

Prima formula, $X(k) = X_{par}(k) + w_N^k X_{imp}(k)$, e valabila pentru orice $k$ (e doar gruparea “pare + impare” din caseta de la 2.3). O aplicam pentru $k + \frac{N}{2}$:

$$ X\!\left(k + \tfrac{N}{2}\right) = \underbrace{X_{par}\!\left(k + \tfrac{N}{2}\right)}_{=\,X_{par}(k)\ \text{(faptul 2)}} + \underbrace{w_N^{k+N/2}}_{=\,-w_N^k\ \text{(faptul 1)}} \cdot \underbrace{X_{imp}\!\left(k + \tfrac{N}{2}\right)}_{=\,X_{imp}(k)\ \text{(faptul 2)}} = X_{par}(k) - w_N^k \cdot X_{imp}(k) $$

Aceasta e a doua formula de lipire.

Verificare cu numerele din 2.3 ($N = 4$, $k = 0$): $X(2) = X_{par}(0) - w_4^0 \cdot X_{imp}(0) = 4 - 1\cdot 6 = -2$. In tabelul de la 1.2, randul $X(2)$ da $1 - 2 + 3 - 4 = -2$. ✓

La curs, FFT se deseneaza ca o schema. Piesa din care e construita toata schema se numeste fluture.

Un fluture e regula de lipire pentru o pereche de numere:

Ce vezi in desen: in stanga, fluturele cu litere. Intra doua numere: $a$ pe linia de sus si $b$ pe linia de jos. Punctul rosu de pe linia de jos inmulteste $b$ cu $w$. Apoi liniile se incruciseaza (de aici numele: desenul seamana cu aripile unui fluture). Nodul ⊕ de sus da $a + w\cdot b$. Nodul ⊖ de jos da $a - w\cdot b$. In dreapta, acelasi fluture cu numerele de la randurile $X(1)$ si $X(3)$ din 2.3: $a = X_{par}(1) = -2$, $b = X_{imp}(1) = -2$, $w = -j$.

Ce costa un fluture: 1 inmultire (cu $w$), 1 adunare si 1 scadere. Din 2 numere face 2 numere.

Legatura cu formulele din 2.4: $a$ este $X_{par}(k)$, $b$ este $X_{imp}(k)$, iesirea de sus este $X(k)$, iesirea de jos este $X(k + \frac{N}{2})$.

Avem 8 esantioane: $x(0), \dots, x(7)$. Aplicam ideea o singura data:

• esantioanele pare $x(0), x(2), x(4), x(6)$ → o DFT cu 4 puncte → $X_{par}(0), \dots, X_{par}(3)$
• esantioanele impare $x(1), x(3), x(5), x(7)$ → alta DFT cu 4 puncte → $X_{imp}(0), \dots, X_{imp}(3)$
• lipire: 4 fluturi, cu inmultitorii $w_8^0, w_8^1, w_8^2, w_8^3$

Ce vezi in desen: in stanga intra esantioanele, sus cele pare (albastru), jos cele impare (portocaliu). Cele doua cutii sunt DFT-uri de cate 4 puncte (deocamdata nu ne intereseaza cum sunt facute inauntru). In dreapta e lipirea: fluturele numarul $k$ leaga linia $X_{par}(k)$ de linia $X_{imp}(k)$, care e cu 4 linii mai jos. Nodurile ⊕ dau $X(0), \dots, X(3)$. Nodurile ⊖ dau $X(4), \dots, X(7)$.

Fiecare cutie “DFT cu 4 puncte” se face la randul ei din doua DFT de cate 2 puncte si o lipire. Fiecare DFT de 2 puncte se face din doua “DFT de 1 punct” (care nu fac nimic) si o lipire. Daca desfaci toate cutiile, raman numai fluturi:

Ce vezi in desen: 8 linii orizontale, citite de la stanga la dreapta. In stanga intra esantioanele (in ordinea ciudata $x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)$ — explicata la 4.4). In dreapta ies $X(0), \dots, X(7)$, in ordine. Intre ele sunt 3 etaje:

• Etajul 1 (albastru): 4 fluturi intre linii vecine. Fiecare e o DFT de 2 puncte (suma si diferenta). Inmultitorul e $w_2^0 = 1$.
• Etajul 2 (verde): 4 fluturi intre linii aflate la distanta 2. Lipesc DFT-urile de cate 2 in DFT-uri de cate 4. Inmultitori: $w_4^0 = 1$ si $w_4^1 = -j$.
• Etajul 3 (portocaliu): 4 fluturi intre linii aflate la distanta 4. Lipesc cele doua DFT de cate 4 in DFT-ul de 8. Inmultitori: $w_8^0, w_8^1, w_8^2, w_8^3$. E exact lipirea din desenul de la 4.2.

Schema se numeste radix-2 (“in baza 2”), pentru ca la fiecare pas imparte in doua.

Ordinea de la intrare nu e aleasa la intamplare. E ce obtii daca imparti de 3 ori in “pare, apoi impare”:

Atentie la randul al treilea: din $[0, 2, 4, 6]$ iau elementele de pe pozitiile pare ale bucatii (primul si al treilea: 0 si 4), apoi pe cele de pe pozitiile impare (al doilea si al patrulea: 2 si 6).

Perechile de la sfarsit, $[0, 4]$, $[2, 6]$, $[1, 5]$, $[3, 7]$, sunt exact cei 4 fluturi din etajul 1.

Luam $x = [1, 0, -1, 0, 1, 0, -1, 0]$. Este un cosinus de amplitudine 1 care face 2 perioade in cele 8 esantioane. Din Cap 6 stim ce trebuie sa iasa: doua linii de inaltime $N \cdot \frac{A}{2} = 8 \cdot \frac{1}{2} = 4$, la $k = 2$ si la $k = 8 - 2 = 6$, si zero in rest.

Trecem lista prin schema de la 4.3. Fiecare coloana a tabelului arata ce e pe cele 8 linii dupa un etaj.

Cum citesti tabelul, pe cateva casute:

• Etajul 1, liniile 1 si 2 (un fluture intre linii vecine, $w = 1$): intra $1$ si $1$ → sus $1 + 1 = 2$, jos $1 - 1 = 0$.
• Etajul 2, liniile 1 si 3 (fluture la distanta 2, $w = w_4^0 = 1$): intra $2$ (linia 1) si $-2$ (linia 3) → sus $2 + (-2) = 0$, jos $2 - (-2) = 4$.
• Etajul 3, liniile 3 si 7 (fluture la distanta 4, $w = w_8^2$): intra $4$ (linia 3) si $0$ (linia 7) → sus $4 + w\cdot 0 = 4$, jos $4 - w\cdot 0 = 4$.

Rezultat: $X = [0, 0, 4, 0, 0, 0, 4, 0]$. Doua linii de inaltime 4, la $k = 2$ si $k = 6$, exact ce prezicea Cap 6. Schema da aceleasi numere ca DFT.

Uita-te la schema de la 4.3:

• sunt 3 etaje;
• fiecare etaj are 4 fluturi (8 linii, cate 2 linii pe fluture);
• in total $3 \cdot 4 = 12$ fluturi.

Fiecare fluture face 1 inmultire, 1 adunare si 1 scadere. Deci:

• inmultiri: $12 \cdot 1 = 12$
• adunari si scaderi: $12 \cdot 2 = 24$

Comparatie: DFT directa pentru $N = 8$ face $8^2 = 64$ de inmultiri (tabelul de la 1.2, cu 8 randuri si 8 coloane) si inca $8 \cdot 7 = 56$ de adunari.

• numarul de etaje: $\log_2(N)$
• fluturi pe etaj: $\frac{N}{2}$ (cele $N$ linii, luate cate doua)
• fluturi in total: $\frac{N}{2}\cdot\log_2(N)$
• inmultiri: $\frac{N}{2}\cdot\log_2(N)$ (una pe fluture)
• adunari si scaderi: $N\cdot\log_2(N)$ (doua pe fluture)

De aici vine formula: numarul de operatii al FFT creste ca $N \cdot \log_2(N)$. Se scrie pe scurt $O(N \log N)$.

La curs s-a numarat mai amanuntit. Rezultatul e acelasi ca forma.

DFT directa. Un inmultitor de pe cerc are o parte reala (un cosinus) si una imaginara (un sinus). Pentru un singur $X(k)$:

• $N$ inmultiri pentru partea reala ($x(n)\cdot\cos\theta$)
• $N$ inmultiri pentru partea imaginara ($x(n)\cdot\sin\theta$)
• $2N - 1$ adunari
• total: $N + N + 2N - 1 = 4N - 1$ operatii

Sunt $N$ valori $X(k)$, deci $N\cdot(4N - 1) = 4N^2 - N$ operatii. Pentru $N = 8$: $4 \cdot 64 - 8 = 248$. Termenul care conteaza e $N^2$ → $O(N^2)$.

FFT, pe schema pentru $N = 8$. Se numara nodurile ⊕/⊖ si punctele de inmultire:

• nodurile: 3 etaje a cate 8 noduri → $3 \cdot 8 = 24$ operatii
• inmultirile cu $w$: 4 pe etaj, dar numai in etajele 2 si 3 (in etajul 1 inmultitorul e $1$, deci nu e nimic de calculat) → $(3 - 1)\cdot 4 = 8$ operatii
• total: $24 + 8 = 32$ operatii, fata de 248

Cu litere, exact cum e scris in notite:

$$ \log_2 N \cdot N + (\log_2 N - 1)\cdot\frac{N}{2} = N\log_2 N + \frac{N}{2}\log_2 N - \frac{N}{2} \;\longrightarrow\; O(N \log N) $$

Verificare pentru $N = 8$: $3\cdot 8 + 2\cdot 4 = 24 + 8 = 32$ ✓.

Asa cum ai scrie la examen la “comparati DFT cu FFT”:

Enunt. Fie $x = [2, 0, 1, 3]$. a) Imparte lista in esantioane pare si impare. b) Calculeaza DFT pe fiecare jumatate. c) Lipeste jumatatile si scrie $X(0), \dots, X(3)$. d) Verifica rezultatul cu DFT calculata direct.

Ce se cere: cele doua liste de cate 2 numere.

Ce stim: $x(0) = 2$, $x(1) = 0$, $x(2) = 1$, $x(3) = 3$. “Par” si “impar” se refera la numarul de ordine $n$.

Pasi:

1. $n$ par: $x(0) = 2$ si $x(2) = 1$.
2. $n$ impar: $x(1) = 0$ si $x(3) = 3$.

Raspuns: lista para $[2, 1]$, lista impara $[0, 3]$.

Ce se cere: $X_{par}(0), X_{par}(1)$ si $X_{imp}(0), X_{imp}(1)$.

Ce stim: DFT pentru doua numere $[a, b]$ este $[a + b,\ a - b]$ (sectiunea 2.2).

Pasi:

1. lista para $[2, 1]$: $2 + 1 = 3$ si $2 - 1 = 1$.
2. lista impara $[0, 3]$: $0 + 3 = 3$ si $0 - 3 = -3$.

Raspuns: $X_{par} = [3, 1]$, $X_{imp} = [3, -3]$.

Ce se cere: $X(0), X(1), X(2), X(3)$.

Ce stim: regula de lipire din 2.4, cu $N = 4$: $X(k) = X_{par}(k) + w_4^k X_{imp}(k)$ si $X(k + 2) = X_{par}(k) - w_4^k X_{imp}(k)$, pentru $k = 0$ si $k = 1$. Inmultitorii: $w_4^0 = 1$, $w_4^1 = -j$.

Pasi:

1. $k = 0$, cu plus: $X(0) = 3 + 1\cdot 3 = 6$.
2. $k = 0$, cu minus: $X(2) = 3 - 1\cdot 3 = 0$.
3. $k = 1$: intai produsul $w_4^1\cdot X_{imp}(1) = (-j)\cdot(-3) = 3j$ (minus ori minus da plus).
4. $k = 1$, cu plus: $X(1) = 1 + 3j$.
5. $k = 1$, cu minus: $X(3) = 1 - 3j$.

Raspuns: $X = [6,\ 1 + 3j,\ 0,\ 1 - 3j]$.

Ce vezi in desen: aceeasi rezolvare pe schema. In stanga intra esantioanele in ordinea pare, apoi impare: $x(0), x(2), x(1), x(3)$. Dupa etajul 1 pe linii sunt $3, 1, 3, -3$ (raspunsul de la b). Dupa etajul 2 ies $6,\ 1 + 3j,\ 0,\ 1 - 3j$ (raspunsul de la c).

Ce se cere: aceleasi valori, din tabelul DFT (ca in 1.2).

Pasi:

1. $X(0) = 2\cdot1 + 0\cdot1 + 1\cdot1 + 3\cdot1 = 6$
2. $X(1) = 2\cdot1 + 0\cdot(-j) + 1\cdot(-1) + 3\cdot j = 2 - 1 + 3j = 1 + 3j$
3. $X(2) = 2\cdot1 + 0\cdot(-1) + 1\cdot1 + 3\cdot(-1) = 2 + 1 - 3 = 0$
4. $X(3) = 2\cdot1 + 0\cdot j + 1\cdot(-1) + 3\cdot(-j) = 2 - 1 - 3j = 1 - 3j$

Raspuns: $[6,\ 1 + 3j,\ 0,\ 1 - 3j]$, identic cu punctul c). ✓ Drumul direct a folosit 16 inmultiri. Drumul FFT a folosit 4 fluturi.

Enunt. a) Cate etaje si cati fluturi are schema FFT radix-2 pentru $N = 16$? b) Dar pentru $N = 1024$? c) De cate ori e FFT mai rapida decat DFT directa in fiecare caz?

Ce se cere: numarul de etaje si numarul de fluturi pentru $N = 16$.

Ce stim: etaje = $\log_2 N$; fluturi pe etaj = $N/2$ (sectiunea 5.2).

Pasi:

1. $16 \to 8 \to 4 \to 2 \to 1$: 4 injumatatiri → $\log_2 16 = 4$ etaje.
2. fluturi pe etaj: $16 : 2 = 8$.
3. fluturi in total: $4 \cdot 8 = 32$.

Raspuns: 4 etaje, 32 de fluturi.

Ce se cere: acelasi lucru pentru $N = 1024$.

Pasi:

1. $\log_2 1024 = 10$ (10 injumatatiri, vezi 1.4) → 10 etaje.
2. fluturi pe etaj: $1024 : 2 = 512$.
3. fluturi in total: $10 \cdot 512 = 5120$.

Raspuns: 10 etaje, 5120 de fluturi.

Ce se cere: raportul dintre munca DFT directe si munca FFT.

Ce stim: DFT directa face cam $N^2$ operatii, FFT cam $N\log_2 N$. Raportul este $\frac{N^2}{N \log_2 N} = \frac{N}{\log_2 N}$ (un $N$ se simplifica).

Pasi:

1. $N = 16$: $256 : 64 = 4$. Sau direct: $16 : 4 = 4$.
2. $N = 1024$: $1\,048\,576 : 10\,240 = 102.4$. Sau direct: $1024 : 10 = 102.4$.

Raspuns: de 4 ori pentru $N = 16$ si de aproximativ 100 de ori pentru $N = 1024$. Cu cat $N$ e mai mare, cu atat castigul e mai mare. (Numerele sunt orientative: depind de ce operatii numeri, vezi caseta de la 5.2. Daca numeri doar inmultirile, iese 8 ori si 205 ori.)

Enunt. Un semnal a fost esantionat cu $f_s = 8000$ Hz si avem $1000$ de esantioane. Semnalul este un cosinus de amplitudine 1 si frecventa 1000 Hz. a) Ce faci ca sa poti folosi o FFT radix-2? b) Ce se schimba in spectru? c) Ce NU se schimba?

Ce se cere: cum ajungi la o lungime buna pentru FFT.

Ce stim: radix-2 cere $N$ putere a lui 2. Puterile lui 2 din jurul lui 1000 sunt $512$ si $1024$.

Pasi:

1. $1000$ nu e putere a lui 2 ($1000 \to 500 \to 250 \to 125 \to$ nu se mai imparte in jumatati egale).
2. Urmatoarea putere a lui 2 este $1024$.
3. Adaugi la sfarsitul listei $1024 - 1000 = 24$ de zerouri. Operatia se numeste zero-padding (Cap 8).

Raspuns: completezi cu 24 de zerouri pana la $N = 1024$ si aplici FFT pe lista de 1024.

Ce se cere: ce e diferit in spectrul cu $N = 1024$ fata de cel cu $N = 1000$.

Ce stim: frecventa casutei $k$ este $f_k = k\cdot\frac{f_s}{N}$ (Cap 6). In formula intra noul $N$.

Pasi:

1. Distanta dintre doua casute vecine: inainte $8000 : 1000 = 8$ Hz; acum $8000 : 1024 = 7.8125$ Hz. Casutele sunt putin mai dese.
2. Unde cade cosinusul de 1000 Hz: inainte la $k = 1000 : 8 = 125$; acum la $k = 1000 : 7.8125 = 128$. Linia s-a mutat pe alt numar $k$, desi frecventa ei e aceeasi.
3. Inaltimea liniei: $500$ in ambele cazuri (cate esantioane adevarate sunt, ori $\frac{A}{2}$: $1000 \cdot \frac12 = 500$). Zerourile nu adauga nimic la suma.
4. Casutele vecine: inainte erau exact $0$. Acum au valori mici, in jur de $12$ (cam 2% din 500). Motivul: noile casute nu mai cad exact pe zerourile spectrului unui cosinus taiat la 1000 de esantioane. E efectul de scurgere spectrala, explicat in Cap 8.

Raspuns: casutele sunt mai dese (7.8125 Hz in loc de 8 Hz), linia apare la $k = 128$ in loc de $k = 125$, iar langa ea apar valori mici care inainte erau zero.

Ce se cere: ce ramane la fel.

Raspuns:

• frecventa la care apare linia: tot 1000 Hz;
• inaltimea ei: tot 500;
• informatia din semnal: zerourile nu aduc informatie noua, deci nu poti separa mai bine doua frecvente apropiate decat inainte;
• valorile in sine: FFT pe lista de 1024 da exact DFT listei de 1024. Diferentele de la b) vin de la zerourile adaugate, nu de la faptul ca am folosit FFT.

• FFT = DFT calculata rapid. Aceleasi numere $X(k)$, mai putine operatii. Nu e alta transformata.
• DFT directa: cam $N^2$ operatii → $O(N^2)$. FFT: cam $N\log_2 N$ operatii → $O(N\log N)$.
• $\log_2(N)$ = de cate ori injumatatesti pe $N$ pana la 1. $\log_2 8 = 3$, $\log_2 1024 = 10$.
• $N = 1024$: cam un milion de operatii fata de cam zece mii (de 100 de ori mai putin).
• Publicata in 1965 de Cooley si Tukey.
• Ideea: imparti in esantioane pare si impare, faci DFT pe fiecare jumatate, lipesti. Repeti pana la liste de 1 numar.
• Lipirea: $X(k) = X_{par}(k) + w_N^k X_{imp}(k)$ si $X(k + \frac{N}{2}) = X_{par}(k) - w_N^k X_{imp}(k)$, cu $w_N = e^{-j2\pi/N}$.
• Merge datorita a doua fapte: $w_N^{k+N/2} = -w_N^k$ (jumatate de tura = semn schimbat) si jumatatile se repeta cu perioada $N/2$.
• DFT pentru 2 numere: $[a, b] \to [a + b,\ a - b]$.
• Schema: $\log_2 N$ etaje, $\frac{N}{2}$ fluturi pe etaj; un fluture = 1 inmultire + 1 adunare + 1 scadere.
• Radix-2 cere $N$ putere a lui 2. Altfel: completezi cu zerouri (zero-padding).
• Intrarile schemei pentru $N = 8$: $x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)$.

Raspunsurile, cu explicatie pentru fiecare varianta, sunt la 9.1.

G1. Fata de DFT, FFT calculeaza:

1. A. o alta transformata, mai noua
2. B. exact aceleasi valori $X(k)$, cu mai putine operatii
3. C. doar o aproximare a valorilor $X(k)$
4. D. doar modulul $|X(k)|$, fara faza

G2. Complexitatea FFT este:

1. A. $O(N)$
2. B. $O(N^2)$
3. C. $O(N \log N)$
4. D. $O(\log N)$

G3. Cate etaje are schema FFT radix-2 pentru $N = 1024$?

1. A. 10
2. B. 512
3. C. 1024
4. D. 32

G4. Cati fluturi are, in total, schema FFT radix-2 pentru $N = 16$?

1. A. 16
2. B. 8
3. C. 256
4. D. 32

G5. Ai 600 de esantioane si vrei sa folosesti o FFT radix-2. Ce faci?

1. A. nu se poate, FFT merge doar daca ai din start o putere a lui 2
2. B. adaugi 424 de zerouri, pana la 1024
3. C. adaugi 400 de zerouri, pana la 1000
4. D. repeti fiecare esantion de doua ori, pana la 1200

G6. In regula de lipire, $X(k + \frac{N}{2})$ este egal cu:

1. A. $X_{par}(k) + w_N^k X_{imp}(k)$
2. B. $X_{imp}(k) - X_{par}(k)$
3. C. $X_{par}(k) - w_N^k X_{imp}(k)$
4. D. $w_N^k X_{par}(k)$

G7. DFT listei $[5, 3]$ (adica $N = 2$) este:

1. A. $[8, 2]$
2. B. $[2, 8]$
3. C. $[15, 2]$
4. D. $[8, -2]$

G8. In ce ordine intra esantioanele in schema FFT radix-2 pentru $N = 8$?

1. A. $0, 1, 2, 3, 4, 5, 6, 7$
2. B. $0, 2, 4, 6, 1, 3, 5, 7$
3. C. $7, 6, 5, 4, 3, 2, 1, 0$
4. D. $0, 4, 2, 6, 1, 5, 3, 7$

Raspunsurile sunt scrise asa cum le-ai scrie pe foaie.

T1. (examen 2026) Care este complexitatea Fast Fourier Transform?

T2. (examen 2023 varianta A, examen 2026) Comparati DFT cu FFT.

T3. (intrebare de antrenament, nu e luata dintr-un examen) Explicati pe scurt ideea algoritmului FFT.

T4. (intrebare de antrenament, nu e luata dintr-un examen) De ce cere FFT ca numarul de esantioane sa fie putere a lui 2 si ce facem daca nu este?

Inainte: Cap 6 — DFT · Legat: Cap 8 — leakage, zero-padding, ferestre · Subiecte reale · Cuprins.