Med Java

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Cap 11 — FFT (Fast Fourier Transform): DFT calculata rapid ======

[[ps:start|← inapoi la cuprins]] · Materie pentru examen (dupa partial) · Notitele colegilor: Cursul 16, p. 37–38 · Inainte: [[ps:cap6-dft|Cap 6 (DFT)]]

<note tip>
**Ideea capitolului, in 3 propozitii:**
  - **FFT NU este o alta transformata.** Da **exact aceleasi numere** $X(k)$ ca DFT din [[ps:cap6-dft|Cap 6]]. Difera doar **drumul** pe care ajungi la ele.
  - DFT calculata "ca la carte" face cam $N^2$ operatii. FFT face cam $N\cdot\log_2(N)$ operatii. Pentru $N$ mare, diferenta e uriasa (minute fata de sutimi de secunda).
  - Trucul: imparti lista in doua jumatati (esantioanele pare si cele impare), calculezi DFT pe fiecare jumatate, apoi **lipesti** cele doua rezultate. Si repeti pe fiecare jumatate.
</note>

**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)$ — [[ps:cap6-dft|Cap 6]]. Ce e $j$ si cercul pe care se invarte $e^{j\theta}$ — [[ps:cap0-baze|Cap 0 §3–4]]. Aici le reamintesc pe scurt, la locul unde apar.

===== 1. Problema: DFT e scumpa =====

==== 1.1 Ce avem de calculat ====

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" ([[ps:cap6-dft|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.

==== 1.2 Numaram operatiile pentru N = 4 ====

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:

^ numarul ^ $1$ ^ $-j$ ^ $-1$ ^ $j$ ^
| unde sta pe cerc | dreapta | jos | stanga | sus |
| cati pasi ai facut | 0 pasi | 1 pas | 2 pasi | 3 pasi |

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$.

<note tip>
**Ce e $j$ si de ce apare un cerc?** $j$ este numarul "special" din [[ps:cap0-baze|Cap 0 §3]], cel pentru care $j \cdot j = -1$. Numerele cu $j$ se deseneaza intr-un plan: pe orizontala partea obisnuita (reala), pe verticala partea cu $j$. Numarul $1$ e in dreapta, $j$ e sus, $-1$ e in stanga, $-j$ e jos. Toate patru sunt la distanta 1 de centru, deci stau pe un cerc. Pentru capitolul asta ajunge sa stii **doua reguli de calcul**: "minus ori minus da plus" (de exemplu $(-j)\cdot(-2) = 2j$) si "numerele cu $j$ se aduna separat de cele fara $j$" (de exemplu $1 - 2j - 3 + 4j = -2 + 2j$).
</note>

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

^ ^ $x(0) = 1$ ^ $x(1) = 2$ ^ $x(2) = 3$ ^ $x(3) = 4$ ^ suma = $X(k)$ ^
| $X(0)$ | $1 \cdot 1$ | $2 \cdot 1$ | $3 \cdot 1$ | $4 \cdot 1$ | $1 + 2 + 3 + 4 = 10$ |
| $X(1)$ | $1 \cdot 1$ | $2 \cdot (-j)$ | $3 \cdot (-1)$ | $4 \cdot j$ | $1 - 2j - 3 + 4j = -2 + 2j$ |
| $X(2)$ | $1 \cdot 1$ | $2 \cdot (-1)$ | $3 \cdot 1$ | $4 \cdot (-1)$ | $1 - 2 + 3 - 4 = -2$ |
| $X(3)$ | $1 \cdot 1$ | $2 \cdot j$ | $3 \cdot (-1)$ | $4 \cdot (-j)$ | $1 + 2j - 3 - 4j = -2 - 2j$ |

<note tip>
**De unde stiu ce inmultitor vine in fiecare casuta?** Regula: in casuta de pe randul $k$ si coloana $n$ faci $k \cdot n$ pasi pe cerc.
  * Randul $X(1)$: $1\cdot0 = 0$ pasi, $1\cdot1 = 1$ pas, $1\cdot2 = 2$ pasi, $1\cdot3 = 3$ pasi → $1, -j, -1, j$.
  * Randul $X(2)$: $0, 2, 4, 6$ pasi. 4 pasi = o tura intreaga = inapoi la start, iar 6 pasi = o tura si inca 2 pasi → $1, -1, 1, -1$.
  * Randul $X(3)$: $0, 3, 6, 9$ pasi → $1, j, -1, -j$.
E aceeasi regula ca in [[ps:cap6-dft|Cap 6]], unde ai calculat de mana o DFT cu $N = 4$.
</note>

**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} $$

<note>
**Notatia din curs pentru inmultitori.** Un pas pe cerc se noteaza $w_N$ (litera w, cu $N$ jos):
$$ w_N = e^{-j\frac{2\pi}{N}} $$
Tradus: "$\frac{1}{N}$ dintr-o tura ($2\pi$ = o tura intreaga, vezi [[ps:cap0-baze|Cap 0 §4]]), in sensul acelor de ceas (asta face semnul minus)". $w_N^k$ inseamna "$k$ pasi". Pentru $N = 4$: $w_4^0 = 1$, $w_4^1 = -j$, $w_4^2 = -1$, $w_4^3 = j$, adica exact tabelul de mai sus. Cu notatia asta, formula DFT din curs,
$$ X(k) = \sum_{n=0}^{N-1} x(n)\, e^{-j\frac{2\pi nk}{N}}, $$
se citeste: "aduna, pentru fiecare $n$, esantionul $x(n)$ inmultit cu $k\cdot n$ pasi pe cerc", adica $x(n)\cdot w_N^{kn}$. E tabelul nostru, scris cu litere.
</note>

==== 1.3 Cat inseamna N² in practica ====

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.

^ $N$ (cate esantioane) ^ $N^2$ (operatii la DFT directa) ^ cat dureaza ^
| $8$ | $64$ | nimic |
| $1024$ | $1\,048\,576$ (cam un milion) | $0.001$ s |
| $44\,100$ (o secunda de muzica de pe CD, vezi [[ps:cap5-cuantizare-snr-db|Cap 5]]) | $1\,944\,810\,000$ (cam 2 miliarde) | cam $2$ s |
| $1\,000\,000$ | $1\,000\,000\,000\,000$ ($10^{12}$) | $1000$ s, adica aproape **17 minute** |

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.

<note tip>
**De ce creste atat de repede?** Pentru ca $N$ apare de doua ori: mai multe esantioane inseamna si mai multe coloane in tabel, si mai multe randuri. Daca $N$ se dubleaza, tabelul are de 2 ori mai multe randuri **si** de 2 ori mai multe coloane, deci de $2 \cdot 2 = 4$ ori mai multe casute. De 10 ori mai multe esantioane → de 100 de ori mai multa munca.
</note>

==== 1.4 Inainte de solutie: ce e log2 ====

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$

^ $N$ ^ 2 ^ 4 ^ 8 ^ 16 ^ 64 ^ 1024 ^ cam 1 000 000 ^
| $\log_2(N)$ | 1 | 2 | 3 | 4 | 6 | 10 | cam 20 |

**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.

<note tip>
**Legatura cu log10 din [[ps:cap5-cuantizare-snr-db|Cap 5 §4.0]].** Acolo $\log_{10}$ numara "de cate ori poti imparti la 10" (cate zerouri are numarul). Aici $\log_2$ numara "de cate ori poti imparti la 2". Aceeasi idee, alt numar la care imparti. Verificare in sens invers: $\log_2(8) = 3$ pentru ca $2 \cdot 2 \cdot 2 = 2^3 = 8$.
</note>

==== 1.5 Ce promite FFT ====

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:

^ $N$ ^ DFT directa: $N^2$ ^ FFT: $N\cdot\log_2(N)$ ^ timp DFT ^ timp FFT ^ de cate ori mai putin ^
| $8$ | $64$ | $8 \cdot 3 = 24$ | nimic | nimic | cam 3 ori |
| $1024$ | $1\,048\,576$ | $1024 \cdot 10 = 10\,240$ | $0.001$ s | $0.00001$ s | cam 100 de ori |
| $44\,100$ | cam 2 miliarde | cam $680\,000$ | cam $2$ s | sub $0.001$ s | cam 2900 de ori |
| $1\,000\,000$ | $10^{12}$ | cam $20\,000\,000$ | $17$ minute | $0.02$ s | cam 50 000 de ori |

{{ps:cap11:n2_vs_nlogn.png?1000|Numarul de operatii: N patrat fata de N log2 N}}

**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$.

<note important>
**De retinut de aici:** FFT a fost publicata in **1965** de **Cooley si Tukey**. Reduce complexitatea DFT de la $O(N^2)$ la $O(N \log N)$. Scrierea cu "O mare" inseamna doar "numarul de operatii creste **cam ca** ...": la DFT cam ca $N^2$, la FFT cam ca $N \cdot \log_2 N$. Rezultatul este **acelasi**.
</note>

===== 2. Ideea: imparte in doua jumatati =====

==== 2.1 De ce ajuta sa imparti ====

**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.

<note tip>
**De ce trebuie ca $N$ sa fie putere a lui 2 (2, 4, 8, 16, ..., 1024, ...)?** Pentru ca injumatatim de mai multe ori la rand si de fiecare data trebuie sa iasa doua jumatati egale. $8 \to 4 \to 2 \to 1$ merge. $6 \to 3 \to$ ? nu mai merge (3 nu se imparte in doua jumatati egale). Ce faci cand $N$ nu e putere a lui 2 vezi in sectiunea 6 si in Problema 3.
</note>

==== 2.2 Cele mai mici DFT: un numar si doua numere ====

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:

^ ^ $a$ ^ $b$ ^ suma ^
| $X(0)$ | $a \cdot 1$ | $b \cdot 1$ | $a + b$ |
| $X(1)$ | $a \cdot 1$ | $b \cdot (-1)$ | $a - b$ |

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.

==== 2.3 FFT de mana pentru x = [1, 2, 3, 4] ====

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]$

{{ps:cap11:impartire_par_impar.png?1000|Lista [1,2,3,4] impartita in esantioane pare si impare}}

**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$:

^ ce calculezi ^ regula ^ cu numere ^ rezultat ^
| $X(0)$ | $X_{par}(0) + w_4^0 \cdot X_{imp}(0)$ | $4 + 1 \cdot 6$ | $10$ |
| $X(1)$ | $X_{par}(1) + w_4^1 \cdot X_{imp}(1)$ | $-2 + (-j)\cdot(-2)$ | $-2 + 2j$ |
| $X(2)$ | $X_{par}(0) - w_4^0 \cdot X_{imp}(0)$ | $4 - 1 \cdot 6$ | $-2$ |
| $X(3)$ | $X_{par}(1) - w_4^1 \cdot X_{imp}(1)$ | $-2 - (-j)\cdot(-2)$ | $-2 - 2j$ |

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

{{ps:cap11:fft4_exemplu.png?1000|FFT pentru N = 4 pe lista [1,2,3,4], cu valorile de pe fiecare linie}}

**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)$.

<note tip>
**De ce apare $w$ in fata jumatatii impare? De ce nu adun pur si simplu cele doua jumatati?** Uita-te la randul $X(1)$ din tabelul de la 1.2 si grupeaza casutele: intai cele pare, apoi cele impare.
$$ X(1) = \underbrace{1\cdot 1 + 3\cdot(-1)}_{\text{esantioanele pare}} \;+\; \underbrace{2\cdot(-j) + 4\cdot j}_{\text{esantioanele impare}} $$
  * Grupul par: $1 - 3 = -2$. Este exact $X_{par}(1)$ (diferenta listei $[1, 3]$).
  * Grupul impar: scoate in fata factorul comun $(-j)$: $\;2\cdot(-j) + 4\cdot j = (-j)\cdot(2 - 4) = (-j)\cdot(-2)$. Paranteza $2 - 4 = -2$ este exact $X_{imp}(1)$ (diferenta listei $[2, 4]$).
Deci $X(1) = X_{par}(1) + (-j)\cdot X_{imp}(1)$. Factorul $(-j) = w_4^1$ apare pentru ca esantioanele impare stau **cu un loc mai la dreapta** decat cele pare ($x(1)$ vine dupa $x(0)$, $x(3)$ dupa $x(2)$). Un loc mai la dreapta inseamna "inca $k$ pasi pe cerc" pentru fiecare dintre ele. Acesti pasi in plus sunt aceiasi pentru toata jumatatea impara, asa ca ii scoti in fata o singura data.
</note>

<note tip>
**De unde vine castigul? Unde am "sarit" peste munca?** Uita-te la tabelul de lipire: $X(0)$ si $X(2)$ folosesc **aceleasi doua numere**, $X_{par}(0) = 4$ si $X_{imp}(0) = 6$, o data cu plus si o data cu minus. La fel $X(1)$ si $X(3)$. DFT directa calcula suma $1 + 3$ de doua ori (o data pe randul $X(0)$, o data pe randul $X(2)$), fara sa observe ca e aceeasi. FFT o calculeaza **o singura data** si o refoloseste. Asta e tot secretul: **nu calcula de doua ori acelasi lucru**.
</note>

==== 2.4 Acelasi lucru, scris cu litere ====

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.

<note>
**Notatia din notitele de curs.** Acolo jumatatea para se numeste $X_1(k)$ si cea impara $X_2(k)$, iar formula e scrisa $X(k) = X_1(k) + w_N^k\, X_2(k)$. E acelasi lucru: $X_1 = X_{par}$, $X_2 = X_{imp}$. Aici le-am dat nume care spun singure ce sunt.
</note>

===== 3. De ce merge =====

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.

{{ps:cap11:cerc_w8.png?1000|Puterile lui w8 si w4 pe cerc}}

**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.

==== 3.1 Faptul 1: jumatate de tura inseamna semn schimbat ====

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.

==== 3.2 Faptul 2: jumatatile se repeta ====

$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}$.

==== 3.3 Cele doua fapte puse cap la cap ====

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$. ✓

<note>
**Cum arata asta in notitele de curs (pentru cine vrea sa urmareasca randurile de acolo).** Se porneste de la formula DFT si se rupe suma in doua: termenii cu $n$ par (scrisi $x(2n)$) si cei cu $n$ impar (scrisi $x(2n+1)$):
$$ X(k) = \sum_{n=0}^{N/2-1} x(2n)\, e^{-j\frac{2\pi (2n) k}{N}} + \sum_{n=0}^{N/2-1} x(2n+1)\, e^{-j\frac{2\pi (2n+1) k}{N}} $$
Din a doua suma se scoate in fata factorul comun $e^{-j\frac{2\pi k}{N}} = w_N^k$ (pasii in plus ai esantioanelor impare). Ce ramane in fiecare suma este o DFT cu $N/2$ puncte:
$$ X(k) = X_1(k) + w_N^k\, X_2(k) $$
Apoi notitele demonstreaza cele doua fapte: $w_{N/2}^{\,n(k + N/2)} = w_{N/2}^{\,nk}$ (faptul 2) si $w_N^{\,k+N/2} = -w_N^{\,k}$ (faptul 1). E exact ce am facut mai sus, cu numere si cu cercul.
</note>

===== 4. Schema "fluture" (butterfly) pentru N = 8 =====

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

==== 4.1 Un singur fluture ====

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

{{ps:cap11:fluture_unu.png?1000|Un fluture: doua intrari, o inmultire, o adunare si o scadere}}

**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})$.

==== 4.2 N = 8: primul pas al ideii ====

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$

{{ps:cap11:fft8_doua_dft4.png?1000|FFT pentru N = 8 din doua DFT de N = 4 si o lipire}}

**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)$.

==== 4.3 Mergem pana jos: schema completa, cu 3 etaje ====

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**:

{{ps:cap11:fft8_schema.png?1000|Schema FFT radix-2 completa pentru N = 8}}

**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**.

<note warning>
**Atentie la notitele de curs:** in schema desenata acolo, nodurile din etajele 2 si 3 apar toate cu plus (⊕). Corect este ca in desenul de mai sus: in fiecare fluture, nodul de **sus** e ⊕ si nodul de **jos** e ⊖. Asa cere a doua formula de lipire (cea cu minus), iar exemplul numeric de la 4.5 iese corect doar asa.
</note>

==== 4.4 De unde vine ordinea 0, 4, 2, 6, 1, 5, 3, 7 ====

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

^ pasul ^ cum arata lista de numere de ordine ^
| la inceput | $0, 1, 2, 3, 4, 5, 6, 7$ |
| impart o data: pozitiile pare, apoi cele impare | $[0, 2, 4, 6]$ si $[1, 3, 5, 7]$ |
| impart fiecare bucata inca o data, la fel | $[0, 4]$, $[2, 6]$, $[1, 5]$, $[3, 7]$ |
| citesc de la stanga la dreapta | $0, 4, 2, 6, 1, 5, 3, 7$ |

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.

<note>
**Scurtatura (optionala): "inversarea bitilor".** Scrie numarul de ordine in baza 2, pe 3 cifre, si citeste cifrele de la coada la cap. Obtii pozitia din schema.
^ numarul ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^
| in baza 2 | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| citit invers | 000 | 100 | 010 | 110 | 001 | 101 | 011 | 111 |
| adica | 0 | 4 | 2 | 6 | 1 | 5 | 3 | 7 |
Randul de jos e chiar ordinea de la intrare. In engleza se numeste //bit reversal//. Daca nu stii baza 2, foloseste tabelul cu impartirea in pare si impare; da acelasi rezultat.
</note>

==== 4.5 Un exemplu trecut prin schema ====

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 [[ps:cap6-dft|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.

^ linia ^ intrare ^ dupa etajul 1 ^ dupa etajul 2 ^ dupa etajul 3 ^ ^
| 1 | $x(0) = 1$ | $1 + 1 = 2$ | $2 + 1\cdot(-2) = 0$ | $0 + w_8^0\cdot 0 = 0$ | $X(0) = 0$ |
| 2 | $x(4) = 1$ | $1 - 1 = 0$ | $0 + (-j)\cdot 0 = 0$ | $0 + w_8^1\cdot 0 = 0$ | $X(1) = 0$ |
| 3 | $x(2) = -1$ | $-1 + (-1) = -2$ | $2 - 1\cdot(-2) = 4$ | $4 + w_8^2\cdot 0 = 4$ | $X(2) = 4$ |
| 4 | $x(6) = -1$ | $-1 - (-1) = 0$ | $0 - (-j)\cdot 0 = 0$ | $0 + w_8^3\cdot 0 = 0$ | $X(3) = 0$ |
| 5 | $x(1) = 0$ | $0$ | $0$ | $0 - w_8^0\cdot 0 = 0$ | $X(4) = 0$ |
| 6 | $x(5) = 0$ | $0$ | $0$ | $0 - w_8^1\cdot 0 = 0$ | $X(5) = 0$ |
| 7 | $x(3) = 0$ | $0$ | $0$ | $4 - w_8^2\cdot 0 = 4$ | $X(6) = 4$ |
| 8 | $x(7) = 0$ | $0$ | $0$ | $0 - w_8^3\cdot 0 = 0$ | $X(7) = 0$ |

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.

===== 5. Numararea operatiilor: de unde vine N·log2(N) =====

==== 5.1 Numaram pe schema pentru N = 8 ====

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.

==== 5.2 Acelasi lucru pentru orice N ====

<note tip>
**De ce sunt exact $\log_2(N)$ etaje?** Fiecare etaj corespunde unei injumatatiri: liste de $N$ → liste de $N/2$ → ... → liste de 1. Numarul de injumatatiri pana la 1 este, prin definitie, $\log_2(N)$ (sectiunea 1.4). Pentru $N = 8$: $8 \to 4 \to 2 \to 1$, deci 3 etaje.
</note>

  * 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)

^ $N$ ^ etaje: $\log_2 N$ ^ fluturi pe etaj: $N/2$ ^ fluturi in total ^ adunari si scaderi: $N\log_2 N$ ^ DFT directa: $N^2$ inmultiri ^
| $8$ | $3$ | $4$ | $12$ | $24$ | $64$ |
| $16$ | $4$ | $8$ | $32$ | $64$ | $256$ |
| $1024$ | $10$ | $512$ | $5120$ | $10\,240$ | $1\,048\,576$ |

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

<note tip>
**De ce se spune "$N\log N$" si nu "$\frac{N}{2}\log N$" sau "$\frac{3N}{2}\log N$"?** Pentru ca la "O mare" numarul din fata nu conteaza. Conteaza doar **cum creste** munca atunci cand creste $N$. Fie ca numeri doar inmultirile ($\frac{N}{2}\log_2 N$), doar adunarile ($N\log_2 N$) sau pe toate ($\frac{3N}{2}\log_2 N$), forma e aceeasi: "$N$ ori $\log N$". La fel, la DFT directa spui $O(N^2)$ indiferent daca numeri $N^2$ sau $4N^2 - N$ operatii.
</note>

==== 5.3 Numaratoarea din notitele de curs ====

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$ ✓.

===== 6. DFT vs FFT =====

Asa cum ai scrie la examen la "comparati DFT cu FFT":

^ ^ DFT (calculata direct, din formula) ^ FFT ^
| Ce este | o **transformata**: reteta care spune ce sunt numerele $X(k)$ | un **algoritm**: un mod rapid de a calcula aceleasi $X(k)$ |
| Ce rezultat da | $X(0), \dots, X(N-1)$ | **exact aceleasi** $X(0), \dots, X(N-1)$ |
| Cum lucreaza | pentru fiecare $k$, inmulteste toate cele $N$ esantioane si aduna | imparte in esantioane pare si impare, calculeaza DFT pe jumatati si le lipeste; repeta pana la liste de 1 numar |
| Numar de operatii | cam $N^2$ → $O(N^2)$ | cam $N\log_2 N$ → $O(N\log N)$ |
| Exemplu, $N = 1024$ | cam $1\,000\,000$ | cam $10\,000$ (de 100 de ori mai putin) |
| Conditie pentru $N$ | orice $N$ | varianta de la curs (radix-2): $N$ **putere a lui 2** |
| Ce faci daca $N$ nu e bun | nimic, merge oricum | completezi lista cu **zerouri** pana la urmatoarea putere a lui 2 (zero-padding, [[ps:cap8-leakage-ferestre|Cap 8]]) |
| Cand a aparut | — | 1965, Cooley si Tukey |

<note important>
**Ce NU schimba FFT.** Pentru ca numerele $X(k)$ sunt aceleasi, tot ce ai invatat despre DFT ramane valabil si cand "faci FFT": legatura dintre $k$ si frecventa ($f_k = k\cdot f_s/N$), simetria, inaltimea $N\cdot A/2$ a liniilor ([[ps:cap6-dft|Cap 6]]), scurgerea spectrala si ferestrele ([[ps:cap8-leakage-ferestre|Cap 8]]). De aceea in practica (si in subiectele de examen) se spune "spectrul vazut cu FFT" cu sensul de "spectrul dat de DFT". In Python, ''np.fft.fft(x)'' intoarce exact valorile DFT.
</note>

===== 7. Probleme rezolvate pe puncte =====

==== Problema 1: FFT de mana pentru N = 4 ====

**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.

=== Punctul a) ===

**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:**
  - $n$ par: $x(0) = 2$ si $x(2) = 1$.
  - $n$ impar: $x(1) = 0$ si $x(3) = 3$.

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

=== Punctul b) ===

**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:**
  - lista para $[2, 1]$: $2 + 1 = 3$ si $2 - 1 = 1$.
  - lista impara $[0, 3]$: $0 + 3 = 3$ si $0 - 3 = -3$.

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

=== Punctul c) ===

**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:**
  - $k = 0$, cu plus: $X(0) = 3 + 1\cdot 3 = 6$.
  - $k = 0$, cu minus: $X(2) = 3 - 1\cdot 3 = 0$.
  - $k = 1$: intai produsul $w_4^1\cdot X_{imp}(1) = (-j)\cdot(-3) = 3j$ (minus ori minus da plus).
  - $k = 1$, cu plus: $X(1) = 1 + 3j$.
  - $k = 1$, cu minus: $X(3) = 1 - 3j$.

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

{{ps:cap11:fft4_problema.png?1000|Problema 1: schema FFT pentru lista [2,0,1,3]}}

**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).

=== Punctul d) ===

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

**Pasi:**
  - $X(0) = 2\cdot1 + 0\cdot1 + 1\cdot1 + 3\cdot1 = 6$
  - $X(1) = 2\cdot1 + 0\cdot(-j) + 1\cdot(-1) + 3\cdot j = 2 - 1 + 3j = 1 + 3j$
  - $X(2) = 2\cdot1 + 0\cdot(-1) + 1\cdot1 + 3\cdot(-1) = 2 + 1 - 3 = 0$
  - $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.

==== Problema 2: cate operatii ====

**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?

=== Punctul a) ===

**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:**
  - $16 \to 8 \to 4 \to 2 \to 1$: 4 injumatatiri → $\log_2 16 = 4$ etaje.
  - fluturi pe etaj: $16 : 2 = 8$.
  - fluturi in total: $4 \cdot 8 = 32$.

**Raspuns:** 4 etaje, 32 de fluturi.

=== Punctul b) ===

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

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

**Raspuns:** 10 etaje, 5120 de fluturi.

=== Punctul c) ===

**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:**
  - $N = 16$: $256 : 64 = 4$. Sau direct: $16 : 4 = 4$.
  - $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.)

==== Problema 3: lista nu are lungime putere a lui 2 ====

**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?

=== Punctul a) ===

**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:**
  - $1000$ nu e putere a lui 2 ($1000 \to 500 \to 250 \to 125 \to$ nu se mai imparte in jumatati egale).
  - Urmatoarea putere a lui 2 este $1024$.
  - Adaugi la sfarsitul listei $1024 - 1000 = 24$ de **zerouri**. Operatia se numeste zero-padding ([[ps:cap8-leakage-ferestre|Cap 8]]).

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

<note tip>
**De ce nu tai lista la 512 esantioane?** S-ar putea, dar ai arunca 488 de esantioane masurate, adica aproape jumatate din informatie. Zerourile adaugate nu strica nimic si nu arunca nimic.
</note>

=== Punctul b) ===

**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}$ ([[ps:cap6-dft|Cap 6]]). In formula intra **noul** $N$.

**Pasi:**
  - Distanta dintre doua casute vecine: inainte $8000 : 1000 = 8$ Hz; acum $8000 : 1024 = 7.8125$ Hz. Casutele sunt putin mai dese.
  - 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.
  - Inaltimea liniei: $500$ in ambele cazuri (cate esantioane **adevarate** sunt, ori $\frac{A}{2}$: $1000 \cdot \frac12 = 500$). Zerourile nu adauga nimic la suma.
  - 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 [[ps:cap8-leakage-ferestre|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.

=== Punctul c) ===

**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.

===== 8. Ce trebuie sa stii din Cap 11 (fisa de 1 minut) =====

  * **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)$.

===== 9. Grile de verificare =====

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

**G1.** Fata de DFT, FFT calculeaza:
  - A. o alta transformata, mai noua
  - B. exact aceleasi valori $X(k)$, cu mai putine operatii
  - C. doar o aproximare a valorilor $X(k)$
  - D. doar modulul $|X(k)|$, fara faza

**G2.** Complexitatea FFT este:
  - A. $O(N)$
  - B. $O(N^2)$
  - C. $O(N \log N)$
  - D. $O(\log N)$

**G3.** Cate etaje are schema FFT radix-2 pentru $N = 1024$?
  - A. 10
  - B. 512
  - C. 1024
  - D. 32

**G4.** Cati fluturi are, in total, schema FFT radix-2 pentru $N = 16$?
  - A. 16
  - B. 8
  - C. 256
  - D. 32

**G5.** Ai 600 de esantioane si vrei sa folosesti o FFT radix-2. Ce faci?
  - A. nu se poate, FFT merge doar daca ai din start o putere a lui 2
  - B. adaugi 424 de zerouri, pana la 1024
  - C. adaugi 400 de zerouri, pana la 1000
  - D. repeti fiecare esantion de doua ori, pana la 1200

**G6.** In regula de lipire, $X(k + \frac{N}{2})$ este egal cu:
  - A. $X_{par}(k) + w_N^k X_{imp}(k)$
  - B. $X_{imp}(k) - X_{par}(k)$
  - C. $X_{par}(k) - w_N^k X_{imp}(k)$
  - D. $w_N^k X_{par}(k)$

**G7.** DFT listei $[5, 3]$ (adica $N = 2$) este:
  - A. $[8, 2]$
  - B. $[2, 8]$
  - C. $[15, 2]$
  - D. $[8, -2]$

**G8.** In ce ordine intra esantioanele in schema FFT radix-2 pentru $N = 8$?
  - A. $0, 1, 2, 3, 4, 5, 6, 7$
  - B. $0, 2, 4, 6, 1, 3, 5, 7$
  - C. $7, 6, 5, 4, 3, 2, 1, 0$
  - D. $0, 4, 2, 6, 1, 5, 3, 7$

==== 9.1 Raspunsuri ====

^ Grila ^ Raspuns ^ De ce e corect ^ De ce sunt gresite celelalte ^
| G1 | **B** | FFT e un algoritm rapid pentru DFT; rezultatul e identic (sectiunea 2.3, pasul 4) | A: transformata e aceeasi, DFT. C: nu se aproximeaza nimic, valorile sunt exacte. D: iese tot numarul complex, cu modul si faza. |
| G2 | **C** | $\log_2 N$ etaje a cate $N/2$ fluturi (sectiunea 5.2) | A: ar insemna un singur etaj. B: asta e DFT directa. D: ar insemna mai putine operatii decat esantioane, imposibil (fiecare esantion trebuie macar citit). |
| G3 | **A** | $\log_2 1024 = 10$ injumatatiri | B: 512 e numarul de fluturi dintr-un etaj. C: 1024 e numarul de linii. D: $32 \cdot 32 = 1024$, dar asta e radical, nu logaritm. |
| G4 | **D** | 4 etaje × 8 fluturi = 32 | A: 16 e numarul de linii. B: 8 sunt fluturii unui singur etaj. C: 256 = $16^2$ e numarul de inmultiri al DFT directe. |
| G5 | **B** | 1024 e prima putere a lui 2 mai mare ca 600; $1024 - 600 = 424$ | A: zero-padding rezolva problema. C: 1000 nu e putere a lui 2. D: 1200 nu e putere a lui 2, iar repetarea esantioanelor schimba semnalul. |
| G6 | **C** | a doua formula de lipire; minusul vine din $w_N^{k+N/2} = -w_N^k$ (sectiunea 3.1) | A: asta e formula pentru $X(k)$, prima jumatate. B: ordinea e inversa si lipseste $w$. D: $w$ inmulteste jumatatea impara, nu pe cea para, si lipseste al doilea termen. |
| G7 | **A** | suma si diferenta: $5 + 3 = 8$, $5 - 3 = 2$ | B: ordinea e suma intai, apoi diferenta. C: 15 e produsul, nu suma. D: diferenta e $5 - 3$, nu $3 - 5$. |
| G8 | **D** | impartire repetata in pare si impare (sectiunea 4.4) | A: ordinea obisnuita e la **iesire**, nu la intrare. B: asta e dupa o singura impartire (schema cu doua cutii de la 4.2), nu dupa toate. C: inversarea listei nu are legatura cu FFT. |

===== 10. Intrebari de teorie ca la examen =====

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

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

<note>
**Raspuns model:** FFT calculeaza DFT unui semnal cu $N$ esantioane in $O(N \log N)$ operatii, fata de $O(N^2)$ cat cere calculul direct din formula DFT. Schema radix-2 are $\log_2 N$ etaje, fiecare cu $N/2$ operatii de tip "fluture" (o inmultire, o adunare, o scadere). Exemplu: pentru $N = 1024$, cam $10\,000$ de operatii in loc de cam $1\,000\,000$.
</note>

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

<note>
**Raspuns model:**
  * DFT este transformata: $X(k) = \sum_{n=0}^{N-1} x(n)e^{-j2\pi nk/N}$, $k = 0, \dots, N-1$. FFT este un **algoritm rapid** care calculeaza **exact aceleasi valori** $X(k)$.
  * Calculul direct al DFT cere $N$ inmultiri pentru fiecare din cele $N$ valori, deci $O(N^2)$. FFT cere $O(N\log N)$.
  * FFT (radix-2, Cooley si Tukey, 1965) cere ca $N$ sa fie putere a lui 2; altfel semnalul se completeaza cu zerouri.
  * Fiind aceleasi valori, toate proprietatile DFT (legatura $k$ ↔ frecventa, simetria, leakage) sunt valabile si pentru rezultatul FFT.
</note>

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

<note>
**Raspuns model:** Semnalul se imparte in esantioanele cu indice par si cele cu indice impar. Se calculeaza DFT (cu $N/2$ puncte) pe fiecare jumatate, $X_1(k)$ si $X_2(k)$, apoi rezultatele se combina: $X(k) = X_1(k) + w_N^k X_2(k)$ si $X(k + N/2) = X_1(k) - w_N^k X_2(k)$, unde $w_N = e^{-j2\pi/N}$. Se foloseste faptul ca $w_N^{k+N/2} = -w_N^k$ si ca DFT-urile pe jumatati sunt periodice cu $N/2$, deci aceleasi produse se refolosesc pentru doua iesiri. Impartirea se repeta pana la liste de un esantion; rezulta $\log_2 N$ etaje a cate $N/2$ fluturi.
</note>

**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?**

<note>
**Raspuns model:** Algoritmul radix-2 injumatateste lista in mod repetat, pana la liste de un singur esantion, deci $N$ trebuie sa se imparta la 2 de fiecare data, adica $N = 2^m$. Daca nu este, adaugam zerouri la sfarsitul semnalului pana la urmatoarea putere a lui 2 (zero-padding). Zerourile nu adauga informatie; spectrul este acelasi, doar esantionat in mai multe puncte (casutele de frecventa sunt mai dese, la $f_s/N$ cu noul $N$).
</note>

----
**Inainte:** [[ps:cap6-dft|Cap 6 — DFT]] · **Legat:** [[ps:cap8-leakage-ferestre|Cap 8 — leakage, zero-padding, ferestre]] · [[ps:subiecte-reale|Subiecte reale]] · [[ps:start|Cuprins]].