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 6 — Semnale discrete, DTFT si DFT ======

[[ps:start|← inapoi la cuprins]] · Materie pentru examenul final · Carte: cap. 6.1–6.2 · Notitele colegilor: Cursurile 10–11 (p. 22–25) · Inainte: [[ps:cap5-cuantizare-snr-db|Cap 5]] · Urmeaza: [[ps:cap7-convolutie|Cap 7 — Convolutia]]

<note important>
**De aici incepe materia de dupa partial.** Pana acum am lucrat cu semnale analogice (formule in timpul $t$) si am vazut cum le transformam in numere (esantionare, cuantizare). De acum lucram **doar cu liste de numere**. Capitolul asta raspunde la o singura intrebare: **cum aflu spectrul unei liste de numere?** Unealta se numeste **DFT**. La examen apare si la teorie ("legatura dintre $k$ si frecventele reale"), si la probleme ("cum arata $|X(k)|$?").
</note>

<note tip>
**Ideea capitolului in 3 fraze:**
  - Dupa convertorul analog-digital avem o **lista de $N$ numere**. **DFT** ia lista si scoate alte $N$ numere, $X(0), X(1), \dots, X(N-1)$: cat din fiecare frecventa e in lista.
  - Numarul $k$ (al catelea rezultat) inseamna frecventa reala **$f_k = k\cdot f_s/N$**. Rezultatele din jumatatea de sus ($k > N/2$) sunt de fapt **frecventele negative**.
  - Un cosinus de amplitudine $A$ care "cade exact pe o casuta" $m$ da **doua bete de inaltime $N\cdot A/2$**: la $k = m$ si la $k = N - m$.
</note>

<note>
**Notatii.** Aici scriem lista cu $x(n)$ si spectrul ei cu $X(k)$. In cursul profesorului si in notitele colegilor aceleasi lucruri sunt scrise $s(n)$ si $S(k)$ (uneori chiar $s(k)$ cu litera mica), iar frecventa de esantionare e scrisa $F_s$. E acelasi lucru, doar alta litera.
</note>

===== 1. Unde suntem si de ce ne trebuie un instrument nou =====

==== 1.1 Ce avem in mana dupa convertorul analog-digital ====

Sa luam un exemplu concret. Avem un semnal analog: un cosinus de 1000 Hz (adica face 1000 de cicluri pe secunda). Il trecem printr-un convertor analog-digital (ADC) care il masoara de 8000 de ori pe secunda.

  * "De 8000 de ori pe secunda" este **frecventa de esantionare**, $f_s = 8000$ Hz ([[ps:cap4-esantionare|Cap 4 §1]]).
  * Fiecare masuratoare se numeste **esantion**.
  * Intre doua masuratori trece timpul $T_s = 1/f_s = 1/8000$ s $= 0.125$ ms. Asta e **perioada de esantionare**.

Daca masuram timp de 1 ms, prindem 8 esantioane:

{{ps:cap6:lista_numere.png?950|Din semnal analog in lista de numere}}

**Ce vezi in desen:** in stanga, cosinusul analog (linia gri) si cele 8 momente in care ADC-ul il masoara (bulinele). In dreapta, ce ramane dupa masurare: 8 numere, desenate ca bete. Pe axa orizontala nu mai e timpul, ci **al catelea numar din lista** este.

Calculatorul nu primeste nici desenul, nici formula. Primeste doar lista:

$$ x = [1,\ 0.71,\ 0,\ -0.71,\ -1,\ -0.71,\ 0,\ 0.71] $$

Cuvintele pe care le folosim de acum:

^ Simbol ^ Ce este ^ In exemplu ^
| $n$ | **indicele esantionului** = al catelea numar din lista (numaratoarea incepe de la 0) | $n = 0, 1, \dots, 7$ |
| $x(n)$ | valoarea esantionului cu numarul $n$ | $x(0) = 1$, $x(1) = 0.71$, $x(4) = -1$ |
| $N$ | **cate esantioane** are lista | $N = 8$ |
| $f_s$ | frecventa de esantionare (esantioane pe secunda, in Hz) | $f_s = 8000$ Hz |
| $T_s$ | timpul dintre doua esantioane, $T_s = 1/f_s$ | $0.125$ ms |

<note tip>
**De ce ii zice semnal "discret" sau "digital"?** "Discret" inseamna "din bucati separate": semnalul exista doar la $n = 0, 1, 2, \dots$ Nu exista $x(1.5)$. Semnalul analog era "continuu": avea o valoare in orice moment $t$. "Digital" inseamna in plus ca valorile au fost si rotunjite (cuantizate, [[ps:cap5-cuantizare-snr-db|Cap 5]]). In capitolul asta rotunjirea nu conteaza, asa ca folosim cele doua cuvinte ca sinonime.
</note>

==== 1.2 Problema ====

Pana acum am aflat spectrul (ce frecvente sunt intr-un semnal si cat de mult din fiecare) plecand de la **formula** semnalului:

  * in [[ps:cap0-baze|Cap 0 §6]]: vedeam $3\cos(2\pi\cdot 2t)$ si desenam doua linii de $3/2$ la $\pm 2$ Hz;
  * in [[ps:cap2-serii-fourier|Cap 2]]: pentru semnale periodice calculam coeficientii $c_k$;
  * in [[ps:cap3-transformata-fourier-am|Cap 3]]: pentru semnale neperiodice foloseam transformata Fourier.

Acum **nu mai avem formula**. Avem doar $[1, 0.71, 0, -0.71, \dots]$. Un semnal real (voce, muzica, radio) nici nu are o formula.

**Intrebarea capitolului:** avand doar lista de numere, cum aflu ce frecvente sunt in ea?

**Raspunsul:** cu **Transformata Fourier Discreta**, pe scurt **DFT** (Discrete Fourier Transform). E o reteta de calcul: bagi $N$ numere, scoti $N$ numere. Rezultatul e spectrul.

**Ce vei sti sa faci la sfarsitul capitolului:**
  - sa calculezi de mana DFT pentru o lista de 4 numere;
  - sa spui ce frecventa in Hz inseamna fiecare rezultat;
  - sa desenezi direct $|X(k)|$ pentru o suma de cosinusuri, fara calcule lungi (asta se cere la examen);
  - sa citesti invers: din desenul $|X(k)|$ sa spui ce cosinusuri sunt in semnal.

===== 2. Frecventa normalizata f = f_c / f_s =====

==== 2.1 Intai cu numere ====

Luam iar cosinusul de 1000 Hz esantionat cu $f_s = 8000$ Hz. Formula lui analogica este $\cos(2\pi\cdot 1000\cdot t)$.

Esantionul numarul $n$ e masurat la momentul $t = n\cdot T_s = n/8000$ secunde. Inlocuim $t$ in formula:

$$ x(n) = \cos\left(2\pi\cdot 1000\cdot \frac{n}{8000}\right) = \cos\left(2\pi\cdot \frac{1000}{8000}\cdot n\right) = \cos\left(2\pi\cdot \frac{1}{8}\cdot n\right) $$

A aparut numarul $\frac{1}{8}$. El este $\frac{1000}{8000}$, adica **frecventa semnalului impartita la frecventa de esantionare**.

**Ce inseamna $\frac18$:** de la un esantion la urmatorul, cosinusul avanseaza cu o optime de ciclu. Deci un ciclu intreg dureaza 8 esantioane. Verifica pe desenul de mai sus: lista revine la valoarea 1 dupa 8 esantioane.

Alte exemple, toate cu $f_s = 8000$ Hz:

^ Frecventa reala a semnalului ^ Impartita la $f_s$ ^ Cat avanseaza la fiecare esantion ^ Un ciclu dureaza ^
| 500 Hz | $500/8000 = 1/16$ | 1/16 de ciclu | 16 esantioane |
| 1000 Hz | $1000/8000 = 1/8$ | 1/8 de ciclu | 8 esantioane |
| 2000 Hz | $2000/8000 = 1/4$ | un sfert de ciclu | 4 esantioane |
| 4000 Hz | $4000/8000 = 1/2$ | jumatate de ciclu | 2 esantioane |

==== 2.2 Acelasi lucru, scris cu litere ====

Numarul din coloana a doua se numeste **frecventa normalizata**:

$$ \boxed{f = \frac{f_c}{f_s}} $$

  * $f_c$ = frecventa reala a semnalului, in Hz. (Atentie: aici $f_c$ **nu** e frecventa de taiere a unui filtru, ca in Cap 1. Cursul foloseste aceeasi litera pentru "frecventa semnalului".)
  * $f_s$ = frecventa de esantionare, in Hz.
  * $f$ = frecventa normalizata. **Nu are unitate de masura**: e Hz impartit la Hz. O poti citi ca "cicluri pe esantion".

Cu ea, orice cosinus esantionat se scrie $x(n) = A\cos(2\pi f n)$. Nu mai apare nici $t$, nici $f_s$.

**Drumul inapoi**, de la frecventa normalizata la Hz: inmultesti cu $f_s$. Exemplu: $f = 1/8$ si $f_s = 8000$ Hz dau $f_c = \frac18\cdot 8000 = 1000$ Hz.

<note tip>
**De ce ne complicam cu inca o frecventa?** Pentru ca lista de numere "nu stie" cat de repede a fost masurata. Lista $[1, 0.71, 0, -0.71, \dots]$ poate veni de la 1000 Hz masurat cu 8000 Hz, sau de la 1 Hz masurat cu 8 Hz. Numerele sunt aceleasi. Tot ce se vede in lista este "un ciclu la 8 esantioane", adica $f = 1/8$. Hertzii ii punem la loc abia la sfarsit, cand cineva ne spune $f_s$.
</note>

==== 2.3 De ce conteaza doar f intre −1/2 si 1/2 ====

Incercam un cosinus de **9000 Hz**, tot cu $f_s = 8000$ Hz. Frecventa normalizata: $f = 9000/8000 = 9/8 = 1/8 + 1$.

Calculam primele 4 esantioane pentru 1000 Hz si pentru 9000 Hz:

^ $n$ ^ 1000 Hz: $\cos(2\pi\cdot\frac18\cdot n)$ ^ 9000 Hz: $\cos(2\pi\cdot\frac98\cdot n)$ ^
| 0 | $\cos(0) = 1$ | $\cos(0) = 1$ |
| 1 | $\cos(45°) = 0.71$ | $\cos(405°) = \cos(360° + 45°) = 0.71$ |
| 2 | $\cos(90°) = 0$ | $\cos(810°) = \cos(2\cdot 360° + 90°) = 0$ |
| 3 | $\cos(135°) = -0.71$ | $\cos(1215°) = \cos(3\cdot 360° + 135°) = -0.71$ |

**Listele sunt identice.** Din lista nu ai cum sa spui daca a fost 1000 Hz sau 9000 Hz.

<note tip>
**De ce ies aceleasi numere?** Cand adaugi 1 la frecventa normalizata, la esantionul $n$ unghiul creste cu exact $n$ ture complete ($n\cdot 360°$). O tura completa te aduce in acelasi punct de pe cerc, deci cosinusul nu se schimba ([[ps:cap0-baze|Cap 0 §4]]). Cu litere, cum scrie cursul: $e^{j2\pi(f+l)n} = e^{j2\pi fn}\cdot e^{j2\pi ln} = e^{j2\pi fn}$ pentru orice numar intreg $l$, fiindca $e^{j2\pi\cdot\text{intreg}} = 1$.
</note>

Asta e exact ce am vazut in [[ps:cap4-esantionare|Cap 4 §2]]: dupa esantionare, spectrul are **copii la fiecare $f_s$**. In frecventa normalizata, $f_s$ inseamna $f_s/f_s = 1$. Deci:

**Spectrul unui semnal digital se repeta la fiecare 1.** Daca il stii pe o bucata de lungime 1, il stii peste tot.

{{ps:cap6:frecv_normalizata.png?950|Spectrul se repeta la fiecare 1}}

**Ce vezi in desen:** pe verticala, cat de mult din fiecare frecventa e in semnal. Pe orizontala sunt doua rigle pentru acelasi lucru: sus frecventa normalizata, jos frecventa reala in Hz pentru $f_s = 8000$ Hz. Forma albastra e spectrul; formele gri sunt copiile lui, la distanta 1 (adica 8000 Hz). Zona galbena, de la $-1/2$ la $1/2$, e cea la care ne uitam.

Bucata pe care o alegem de obicei este **$f \in [-1/2,\ 1/2]$**, adica in Hz **$[-f_s/2,\ f_s/2]$**.

<note tip>
**De ce tocmai 1/2?** $f = 1/2$ inseamna "jumatate de ciclu la fiecare esantion", adica lista $+1, -1, +1, -1, \dots$ Mai repede de atat o lista de numere nu poate oscila. In Hz, $f = 1/2$ inseamna $f_s/2$: e frecventa Nyquist din [[ps:cap4-esantionare|Cap 4 §3]]. Tot ce e peste ea arata in lista ca o frecventa mai mica (aliasing).
</note>

Cursul mentioneaza si varianta **$f \in [0, 1]$**. E aceeasi informatie: bucata de la $1/2$ la $1$ este copia bucatii de la $-1/2$ la $0$, mutata cu 1 la dreapta. Vom avea nevoie de asta in §6.

===== 3. DTFT pe scurt =====

==== 3.1 Ce este ====

**DTFT** (Discrete Time Fourier Transform, "transformata Fourier cu timp discret") este transformata Fourier adaptata pentru o lista de esantioane. Tu alegi o frecventa normalizata $f$, oricare. Ea iti spune cat din frecventa aceea este in lista.

Formulele din curs sunt acestea. Nu le vei calcula de mana; trebuie doar sa le recunosti:

$$ X(f) = \sum_{n=-\infty}^{\infty} x(n)\, e^{-j2\pi f n}, \qquad f \in [-1/2,\ 1/2] $$

$$ x(n) = \int_{-1/2}^{1/2} X(f)\, e^{j2\pi f n}\, df $$

Cum citesti prima formula:
  * $\sum$ inseamna "aduna". Sub el si deasupra lui scrie de unde pana unde: aici pentru **toate** esantioanele, de la $-\infty$ la $+\infty$.
  * $x(n)$ e esantionul numarul $n$.
  * $e^{-j2\pi fn}$ e un punct de pe cercul de raza 1 ([[ps:cap0-baze|Cap 0 §4]]). Gandeste-l ca pe un ac de ceas care se roteste cu $f$ ture la fiecare esantion.
  * Deci: iei fiecare esantion, il inmultesti cu pozitia acului, aduni tot. Cum functioneaza exact reteta asta vezi in §4, pe un exemplu cu 4 numere.

A doua formula face drumul inapoi (din spectru in lista). Semnul $\int$ este o suma "continua", peste toate frecventele dintre $-1/2$ si $1/2$.

Fata de transformata Fourier din [[ps:cap3-transformata-fourier-am|Cap 3]] s-a schimbat un singur lucru: in loc de timpul continuu $t$ avem indicele $n$, asa ca in loc de integrala peste $t$ avem suma peste $n$.

Proprietatea de retinut: **$X(f)$ se repeta la fiecare 1** (e "periodica de perioada 1"). E desenul din §2.3.

==== 3.2 De ce nu ne ajunge ====

DTFT are doua probleme. Amandoua vin de la cuvantul "infinit":

  - **Cere o infinitate de esantioane.** Suma merge de la $-\infty$ la $+\infty$. Noi avem o lista cu un numar finit de numere.
  - **Da o infinitate de rezultate.** $f$ poate fi orice numar dintre $-1/2$ si $1/2$, si sunt o infinitate de astfel de numere. Un calculator nu poate calcula si memora o infinitate de valori.

Solutia este sa luam un numar finit si in timp, si in frecventa: **$N$ esantioane** la intrare si **$N$ frecvente** la iesire. Asta este DFT.

^ ^ DTFT ^ DFT ^
| Cate esantioane foloseste | o infinitate | $N$ |
| La ce frecvente da rezultat | la orice $f$ din $[-1/2, 1/2]$ (o curba continua) | doar la $N$ frecvente: $f = k/N$, cu $k = 0, 1, \dots, N-1$ (bete) |
| Se poate calcula pe calculator | nu | da |
| La ce foloseste | teorie, demonstratii | practica: asta ruleaza pe calculator |

<note>
**Legatura dintre ele:** DFT da exact valorile DTFT-ului listei de $N$ esantioane, dar citite doar in $N$ puncte: la $f = 0, \frac1N, \frac2N, \dots$ Ce se intampla intre aceste puncte conteaza la "scurgerea spectrala" din [[ps:cap8-leakage-ferestre|Cap 8]].
</note>

===== 4. DFT calculata de mana =====

==== 4.1 Ideea, in cuvinte ====

In [[ps:cap0-baze|Cap 0 §6]] am spus ca spectrul e ca lista de ingrediente a unui smoothie: ce fructe sunt si cat din fiecare. DFT este aparatul care gusta smoothie-ul (lista de numere) si scrie lista de ingrediente.

Aparatul are $N$ **casute de frecventa**, numerotate cu $k = 0, 1, \dots, N-1$. (In engleza si in laborator li se spune "bin"-uri.)

  * Casuta $k$ verifica o singura frecventa: cea care face **$k$ cicluri intregi in cele $N$ esantioane**.
  * Rezultatul casutei se noteaza $X(k)$. Daca frecventa aceea este in lista, $X(k)$ iese mare. Daca nu este, $X(k)$ iese 0.

Lista are $N$ numere, deci avem $N$ casute si $N$ rezultate.

==== 4.2 Unealta: acul care se roteste ====

Verificarea se face cu un **ac de ceas de lungime 1** care se roteste pe cerc. Pozitia acului este un numar complex de pe cercul de raza 1 ([[ps:cap0-baze|Cap 0 §4]]): $e^{-j\cdot\text{unghi}}$. Semnul minus inseamna ca acul se roteste **in sensul acelor de ceas**.

Luam cazul cel mai mic: $N = 4$ esantioane si casuta $k = 1$ ("1 ciclu in 4 esantioane").

  * Un ciclu in 4 esantioane inseamna **un sfert de tura la fiecare esantion**, adica 90°.
  * Acul porneste din dreapta (pozitia 1) si la fiecare esantion mai face un sfert de tura.

{{ps:cap6:cerc_n4.png?430|Cele 4 pozitii ale acului}}

**Ce vezi in desen:** cercul de raza 1. Pe orizontala e partea reala, pe verticala partea imaginara. Cele 4 buline rosii sunt pozitiile acului la pasii $n = 0, 1, 2, 3$: **1, −j, −1, j**.

<note tip>
**Ce sunt $j$ si $-j$?** Sunt doar numele a doua puncte de pe cerc: $j$ e punctul de sus, $-j$ e punctul de jos, la fel cum $1$ e punctul din dreapta si $-1$ cel din stanga ([[ps:cap0-baze|Cap 0 §3]]). Singura regula de calcul de care ai nevoie: $j\cdot j = -1$. Din ea rezulta $j\cdot(-j) = 1$.
</note>

Pentru celelalte casute acul merge cu alta viteza: casuta $k$ face **$k$ sferturi de tura** la fiecare esantion.

^ Casuta ^ Cat se roteste acul la fiecare esantion ^ Pozitia la $n=0$ ^ $n=1$ ^ $n=2$ ^ $n=3$ ^
| $k = 0$ | deloc | 1 | 1 | 1 | 1 |
| $k = 1$ | un sfert de tura | 1 | $-j$ | $-1$ | $j$ |
| $k = 2$ | doua sferturi = jumatate de tura | 1 | $-1$ | 1 | $-1$ |
| $k = 3$ | trei sferturi de tura | 1 | $j$ | $-1$ | $-j$ |

(Randul $k = 3$: trei sferturi de tura in sensul acelor de ceas te duc de la 1 la $j$, apoi la $-1$, apoi la $-j$. Urmareste pe cerc.)

==== 4.3 Reteta ====

Pentru fiecare casuta $k$:
  - iei fiecare esantion $x(n)$;
  - il inmultesti cu pozitia acului din tabel (randul $k$, coloana $n$);
  - aduni cele $N$ produse. Suma este $X(k)$.

==== 4.4 Calculul pentru lista x = [1, 0, −1, 0] ====

**Casuta $k = 0$** (acul sta pe loc: 1, 1, 1, 1):

$$ X(0) = 1\cdot 1 + 0\cdot 1 + (-1)\cdot 1 + 0\cdot 1 = 1 + 0 - 1 + 0 = 0 $$

**Casuta $k = 1$** (acul: 1, $-j$, $-1$, $j$):

$$ X(1) = 1\cdot 1 + 0\cdot(-j) + (-1)\cdot(-1) + 0\cdot j = 1 + 0 + 1 + 0 = 2 $$

**Casuta $k = 2$** (acul: 1, $-1$, 1, $-1$):

$$ X(2) = 1\cdot 1 + 0\cdot(-1) + (-1)\cdot 1 + 0\cdot(-1) = 1 + 0 - 1 + 0 = 0 $$

**Casuta $k = 3$** (acul: 1, $j$, $-1$, $-j$):

$$ X(3) = 1\cdot 1 + 0\cdot j + (-1)\cdot(-1) + 0\cdot(-j) = 1 + 0 + 1 + 0 = 2 $$

**Rezultat:** $X = [0,\ 2,\ 0,\ 2]$.

{{ps:cap6:dft_n4.png?950|DFT pentru N = 4}}

**Ce vezi in desen:** in stanga lista de intrare, cu indicele $n$ pe orizontala. In dreapta rezultatul DFT, cu indicele casutei $k$ pe orizontala si marimea rezultatului pe verticala. Sub fiecare $k$ scrie ce frecventa verifica acea casuta (explicatia vine in §5 si §6).

==== 4.5 Ce ne spune rezultatul ====

  * $X(1) = 2$, diferit de 0. Deci lista contine frecventa "1 ciclu in 4 esantioane". Este adevarat: $[1, 0, -1, 0]$ sunt chiar valorile lui $\cos(2\pi\cdot\frac14\cdot n)$, adica $\cos(0°) = 1$, $\cos(90°) = 0$, $\cos(180°) = -1$, $\cos(270°) = 0$.
  * $X(0) = 0$. Casuta 0 verifica "0 cicluri", adica o valoare constanta. Lista nu are parte constanta (media ei este 0).
  * $X(2) = 0$. Nu exista nimic care sa faca 2 cicluri in 4 esantioane.
  * $X(3) = 2$. De ce apare si casuta 3, cand in lista e un singur cosinus? Pentru ca un cosinus are intotdeauna **doua** linii in spectru, una la frecventa pozitiva si una la cea negativa ([[ps:cap0-baze|Cap 0 §6.1]]). Casuta 3 este frecventa negativa. Explicatia completa este in §6.

<note tip>
**De ce a iesit 2 si nu 1, cat e amplitudinea cosinusului?** Pentru ca DFT **aduna** cele $N$ produse si nu imparte la nimic. In Cap 0, un cosinus de amplitudine 1 dadea doua linii de $\frac12$. Aici fiecare linie iese de $N$ ori mai mare: $4\cdot\frac12 = 2$. Regula generala ($N\cdot A/2$) este in §7.
</note>

==== 4.6 Acelasi lucru, scris cu litere: formula DFT ====

$$ \boxed{X(k) = \sum_{n=0}^{N-1} x(n)\, e^{-j2\pi\frac{k}{N}n}, \qquad k = 0, 1, \dots, N-1} $$

Bucata cu bucata, este exact reteta din §4.3:
  * $\sum_{n=0}^{N-1}$ = "aduna pentru $n$ de la 0 la $N-1$", adica peste toate cele $N$ esantioane;
  * $x(n)$ = esantionul numarul $n$;
  * $e^{-j2\pi\frac{k}{N}n}$ = pozitia acului. Unghiul lui este $2\pi\cdot\frac{k}{N}\cdot n$: la fiecare esantion acul mai face $\frac{k}{N}$ dintr-o tura ($2\pi$ = o tura completa). Pentru $N = 4$, $k = 1$: un sfert de tura la fiecare esantion, cum am folosit mai sus. Minusul = in sensul acelor de ceas.

Compara cu formula DTFT din §3: in loc de frecventa oarecare $f$ scrie acum $\frac{k}{N}$, iar suma se opreste la $N$ esantioane. Deci **casuta $k$ verifica frecventa normalizata $f = k/N$**.

<note tip>
**De ce inmultim cu un ac care se roteste si de ce in sens invers (minus)?** Un cosinus este facut din doua ace care se rotesc in sensuri opuse ([[ps:cap0-baze|Cap 0 §4.3]]). Ca sa "prinzi" un ac care se roteste cu o anumita viteza, il inmultesti cu un ac care se roteste **la fel de repede, dar invers**. Rotatiile se anuleaza si produsul sta pe loc: $e^{j\theta}\cdot e^{-j\theta} = e^{0} = 1$. Atunci toate cele $N$ produse arata in aceeasi directie si **se aduna**. Daca vitezele nu se potrivesc, produsul continua sa se roteasca, produsele arata in toate directiile si **se anuleaza** intre ele.
</note>

Exemplu concret. Lista $[1, j, -1, -j]$ este un ac care se roteste invers acelor de ceas, cu un sfert de tura pe esantion.
  * O inmultim cu acul casutei $k = 1$, adica $[1, -j, -1, j]$: $1\cdot 1 = 1$, $j\cdot(-j) = 1$, $(-1)\cdot(-1) = 1$, $(-j)\cdot j = 1$. Suma: $1 + 1 + 1 + 1 = 4$.
  * O inmultim cu acul casutei $k = 2$, adica $[1, -1, 1, -1]$: produsele sunt $1, -j, -1, j$. Suma: $1 - j - 1 + j = 0$.

{{ps:cap6:aduna_anuleaza.png?900|Se aduna sau se anuleaza}}

**Ce vezi in desen:** cele 4 produse desenate ca sageti puse cap la coada (asa se aduna numerele complexe). In stanga (casuta potrivita) toate sagetile arata spre dreapta si ajungi la 4. In dreapta (casuta nepotrivita) sagetile fac un patrat si te intorci de unde ai plecat: suma 0.

Proprietatea asta ("ace de viteze diferite dau suma 0") se numeste in curs **ortogonalitatea exponentialelor complexe**. Din cauza ei fiecare casuta raspunde doar la frecventa ei.

<note warning>
**Atentie la semnul din notite.** In cartea profesorului (formula 6.5) si la pagina 23 din notitele colegilor, DFT are **minus** la exponent, iar transformata inversa are plus. La pagina 24 din notitele colegilor semnele sunt scrise invers. Foloseste varianta din carte: **minus la DFT**. Pentru desenul $|X(k)|$ al unui semnal real nu se schimba nimic, pentru ca betele vin oricum in perechi simetrice.
</note>

==== 4.7 Modul si faza ====

In exemplul de mai sus $X(k)$ a iesit numar obisnuit (real). In general iese **numar complex**. Exemplu: aceeasi oscilatie, dar intarziata cu un esantion, $x = [0, 1, 0, -1]$ (acestea sunt valorile lui $\sin(2\pi\cdot\frac14\cdot n)$).

$$ X(1) = 0\cdot 1 + 1\cdot(-j) + 0\cdot(-1) + (-1)\cdot j = -j - j = -2j $$

$$ X(3) = 0\cdot 1 + 1\cdot j + 0\cdot(-1) + (-1)\cdot(-j) = j + j = 2j $$

Celelalte doua ies 0. Deci $X = [0,\ -2j,\ 0,\ 2j]$.

Un numar complex are doua parti utile ([[ps:cap0-baze|Cap 0 §3]]):
  * **modulul** $|X(k)|$ = lungimea, adica distanta pana la 0. Pentru $-2j$ modulul este 2. El spune **cat de mult** din frecventa aceea este in lista.
  * **faza** = unghiul. Pentru $-2j$ (punctul de jos) faza este $-90°$. Ea spune **cat de intarziata** este oscilatia.

Comparam: cosinusul a dat $|X| = [0, 2, 0, 2]$, sinusul da tot $|X| = [0, 2, 0, 2]$. **Modulul e acelasi; difera doar faza.** E ce stiam din [[ps:cap0-baze|Cap 0 §6.2]]: sinusul este un cosinus intarziat.

La examen se cere aproape mereu desenul **modulului**, $|X(k)|$.

**Incearca tu:** calculeaza DFT pentru $x = [3, 1, -1, 1]$.

<note>
**Raspuns:** $X(0) = 3 + 1 - 1 + 1 = 4$. $X(1) = 3\cdot 1 + 1\cdot(-j) + (-1)\cdot(-1) + 1\cdot j = 3 - j + 1 + j = 4$. $X(2) = 3 - 1 - 1 - 1 = 0$. $X(3) = 3 + j + 1 - j = 4$. Deci $X = [4, 4, 0, 4]$. (Lista este $1 + 2\cos(2\pi\cdot\frac14 n)$: constanta 1 da $X(0) = 4\cdot 1 = 4$, iar cosinusul de amplitudine 2 da $4\cdot\frac22 = 4$ in casutele 1 si 3. Regulile sunt in §7.)
</note>

===== 5. De la k la Hz: f_k = k·f_s/N =====

==== 5.1 Intai cu numere ====

Exemplul din curs: $N = 8$ esantioane, masurate cu $f_s = 8000$ Hz. Ce frecventa reala verifica casuta $k = 3$?

  - Casuta $k$ verifica "$k$ cicluri in $N$ esantioane". Pentru $k = 3$: 3 cicluri in 8 esantioane, adica $\frac38$ de ciclu pe esantion. Asta este frecventa normalizata $f = \frac38$ (§2).
  - De la frecventa normalizata la Hz inmultim cu $f_s$ (§2.2): $\frac38\cdot 8000 = 3000$ Hz.

La fel pentru toate casutele:

^ $k$ ^ Frecventa normalizata $k/N$ ^ Frecventa reala $k\cdot f_s/N$ ^
| 0 | 0 | 0 Hz (partea constanta) |
| 1 | 1/8 | 1000 Hz |
| 2 | 2/8 | 2000 Hz |
| 3 | 3/8 | 3000 Hz |
| 4 | 4/8 = 1/2 | 4000 Hz ($= f_s/2$) |
| 5 | 5/8 | 5000 Hz |
| 6 | 6/8 | 6000 Hz |
| 7 | 7/8 | 7000 Hz |

(Ultimele trei randuri sunt peste $f_s/2$. Ce inseamna ele de fapt vezi in §6.)

==== 5.2 Acelasi lucru, scris cu litere ====

$$ \boxed{f_k = k\cdot\frac{f_s}{N}} $$

De unde vine: casuta $k$ are frecventa normalizata $\frac{k}{N}$ (§4.6). Frecventa normalizata este $\frac{f_c}{f_s}$ (§2.2). Le egalam: $\frac{f_c}{f_s} = \frac{k}{N}$, deci $f_c = k\cdot\frac{f_s}{N}$.

  * $f_k$ = frecventa reala (in Hz) pe care o verifica casuta $k$;
  * $k$ = numarul casutei;
  * $f_s$ = frecventa de esantionare (Hz);
  * $N$ = numarul de esantioane.

<note important>
**Fara $f_s$ nu poti spune nimic in Hz.** DFT lucreaza doar cu lista si cu $N$. Daca enuntul nu da $f_s$, raspunsul ramane cu $k$ sau cu frecvente normalizate $k/N$ (asa e la testul din Cursul 13, problema P2 de mai jos).
</note>

==== 5.3 Rezolutia in frecventa ====

Distanta dintre doua casute vecine este **$f_s/N$**. In exemplu: $8000/8 = 1000$ Hz. Se numeste **rezolutia in frecventa** (cat de fin "vede" DFT).

  * Toate casutele sunt la multipli ai acestui pas: $0, 1000, 2000, \dots$ De aceea cursul numeste frecventa primei casute, $f_1 = 1/N$ (normalizata), **frecventa fundamentala**: $f_k = k\cdot f_1$.
  * DFT nu are casuta la 1500 Hz. Un cosinus de 1500 Hz "cade intre casute" si se imprastie peste mai multe. Fenomenul se numeste scurgere spectrala (leakage) si este subiectul din [[ps:cap8-leakage-ferestre|Cap 8]].

**Cum faci rezolutia mai fina:** maresti $N$ (iei mai multe esantioane), pastrand $f_s$.

^ $f_s$ ^ $N$ ^ Cat timp ai inregistrat ($N/f_s$) ^ Rezolutia $f_s/N$ ^
| 8000 Hz | 8 | 0.001 s | 1000 Hz |
| 8000 Hz | 80 | 0.01 s | 100 Hz |
| 8000 Hz | 8000 | 1 s | 1 Hz |
| 16000 Hz | 8 | 0.0005 s | 2000 Hz (mai proasta!) |

<note tip>
**De ce mai multe esantioane inseamna rezolutie mai buna?** Uita-te la coloana a treia: rezolutia este exact 1 impartit la durata inregistrarii ($\frac{f_s}{N} = \frac{1}{N\cdot T_s}$). Ca sa deosebesti doua note muzicale foarte apropiate trebuie sa le asculti mai mult timp. Daca asculti o miime de secunda, nu poti deosebi 1000 Hz de 1300 Hz. **Capcana:** daca maresti $f_s$ si pastrezi $N$, inregistrezi mai putin timp, deci rezolutia se strica (ultimul rand).
</note>

==== 5.4 Ce interval de frecvente analizeaza DFT ====

Casutele $k = 0, 1, \dots, N-1$ acopera frecventele de la **0 pana aproape de $f_s$**, din $f_s/N$ in $f_s/N$. Ultima casuta este la $(N-1)\cdot f_s/N$, cu un pas inainte de $f_s$. In frecventa normalizata: de la 0 pana aproape de 1.

Din §2.3 stim ca e acelasi lucru cu intervalul **de la $-f_s/2$ la $f_s/2$**. Cum se face trecerea vezi in sectiunea urmatoare.

===== 6. Jumatatea de sus = frecventele negative =====

==== 6.1 Ce nu se leaga ====

Doua lucruri de mai sus par ciudate:
  * In §4 un singur cosinus a dat doua bete: la $k = 1$ **si** la $k = 3$.
  * In tabelul din §5.1 casuta $k = 7$ inseamna 7000 Hz. Dar cu $f_s = 8000$ Hz cea mai mare frecventa care se poate reprezenta este $f_s/2 = 4000$ Hz ([[ps:cap4-esantionare|Cap 4 §3]]).

Amandoua au aceeasi explicatie.

==== 6.2 Casuta k si casuta k − N sunt aceeasi casuta ====

Intoarce-te la tabelul cu pozitiile acului din §4.2 ($N = 4$). Randul $k = 3$ este: $1, j, -1, -j$.

Acum gandeste-te la casuta "$k = -1$": minus un sfert de tura la fiecare esantion, adica un sfert de tura **in sens invers** (invers acelor de ceas). Pozitiile: $1$, apoi sus la $j$, apoi $-1$, apoi jos la $-j$. Adica $1, j, -1, -j$.

**Sunt aceleasi pozitii.** Trei sferturi de tura intr-un sens te duc in acelasi punct ca un sfert de tura in celalalt sens. Deci casuta 3 si casuta $-1$ fac exact acelasi calcul: $X(3) = X(-1)$.

In general, casutele $k$ si $k - N$ difera prin $N$ pasi de $\frac1N$ de tura la fiecare esantion, adica printr-o tura completa. O tura completa nu schimba nimic. Deci:

$$ X(k) = X(k - N) \qquad\text{si, la fel,}\qquad X(k + N) = X(k) $$

Pentru $N = 8$, $f_s = 8000$ Hz: $X(7) = X(7 - 8) = X(-1)$. Casuta 7 este casuta $-1$, adica frecventa $-1\cdot 1000 = -1000$ Hz. In Hz: $7000 - 8000 = -1000$.

<note tip>
**Am mai vazut asta.** Este aliasingul din [[ps:cap4-esantionare|Cap 4 §4]]: dupa esantionarea cu 8000 Hz, frecventele 7000 Hz si $-1000$ Hz dau aceleasi esantioane, deci nu pot fi deosebite. In §2.3 am vazut acelasi lucru cu 9000 Hz si 1000 Hz.
</note>

**Regula:** pentru casutele din jumatatea de sus ($k > N/2$), frecventa adevarata este cea a casutei $k - N$, adica una **negativa**.

^ $k$ ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^
| $k\cdot f_s/N$ | 0 | 1000 | 2000 | 3000 | 4000 | 5000 | 6000 | 7000 |
| de fapt casuta | 0 | 1 | 2 | 3 | $\pm 4$ | $5 - 8 = -3$ | $6 - 8 = -2$ | $7 - 8 = -1$ |
| frecventa adevarata (Hz) | 0 | 1000 | 2000 | 3000 | $\pm 4000$ | $-3000$ | $-2000$ | $-1000$ |

Casuta din mijloc, $k = N/2 = 4$, este $f_s/2 = 4000$ Hz. Ea este in acelasi timp $+4000$ si $-4000$ Hz ($4 - 8 = -4$): e una singura.

{{ps:cap6:jumatatea_de_sus.png?950|Jumatatea de sus a DFT sunt frecventele negative}}

**Ce vezi in desen:** sus, spectrul asa cum iese din DFT, cu $k$ de la 0 la 7 (sub fiecare $k$ scrie $k\cdot f_s/N$). Casutele portocalii (5, 6, 7) sunt frecventele negative. Jos, acelasi spectru dupa ce am mutat casutele portocalii in stanga lui 0: arata simetric, exact ca spectrele din Cap 0. Semnalul din desen este exemplul din carte: un cosinus de amplitudine 1 pe casuta 1 plus unul de amplitudine 0.5 pe casuta 2.

<note tip>
**Atunci bata de la $k = 7$ e la 7000 Hz sau la −1000 Hz?** Amandoua descriu aceleasi esantioane. Prin conventie citim totul in intervalul $[-f_s/2, f_s/2]$, deci spunem $-1000$ Hz. Daca inainte de ADC a fost pus filtrul anti-aliasing ([[ps:cap4-esantionare|Cap 4 §3]]), in semnal nici nu exista ceva peste $f_s/2$, asa ca raspunsul sigur este $-1000$ Hz.
</note>

==== 6.3 Simetria pentru semnale reale ====

Un semnal **real** este o lista de numere obisnuite, fara $j$. Toate semnalele masurate de un ADC sunt reale.

Pentru un semnal real, betele vin in perechi: **$|X(N - k)| = |X(k)|$**.

De ce: orice cosinus are o linie la $+f$ si una la $-f$, de aceeasi inaltime ([[ps:cap0-baze|Cap 0 §6.1]]). Linia de la $+f$ ajunge in casuta $k$, cea de la $-f$ ajunge in casuta $-k$, care este casuta $N - k$.

Verificare pe exemplele de pana acum:
  * $N = 4$: $|X(1)| = |X(3)| = 2$ (aici $N - k = 4 - 1 = 3$);
  * in desenul de mai sus, $N = 8$: $|X(1)| = |X(7)| = 4$ si $|X(2)| = |X(6)| = 2$.

Mai exact, $X(N-k)$ este **conjugatul** lui $X(k)$: acelasi modul, faza cu semn schimbat. Ai vazut asta la sinus in §4.7: $X(1) = -2j$ si $X(3) = +2j$.

**Consecinta practica:** la un semnal real, jumatatea de sus nu aduce informatie noua. De aceea in laborator se deseneaza adesea doar $k = 0 \dots N/2$. **La examen deseneaza toate betele**, daca nu ti se cere altfel.

==== 6.4 Ce face fftshift ====

In Python (laborator), ''fft(x)'' intoarce rezultatele in ordinea $k = 0, 1, \dots, N-1$. Functia ''fftshift'' doar **rearanjeaza** lista: muta jumatatea de sus in fata, ca sa ai ordinea $k = -N/2, \dots, -1, 0, 1, \dots, N/2 - 1$, cu frecventa 0 la mijloc. Nu calculeaza nimic nou. Este trecerea de la desenul de sus la desenul de jos din figura de mai sus.

==== 6.5 Spectrul DFT se repeta la fiecare N ====

Relatia $X(k + N) = X(k)$ spune ca, daca ai calcula DFT si pentru alte valori ale lui $k$ (negative sau mai mari decat $N - 1$), ai regasi aceleasi $N$ valori, la nesfarsit. Spectrul DFT este **periodic cu perioada $N$**.

{{ps:cap6:periodicitate.png?950|Spectrul DFT e periodic cu perioada N}}

**Ce vezi in desen:** acelasi spectru ca mai sus, desenat pentru $k$ de la $-8$ la $15$. Zona galbena ($k = 0 \dots 7$) este ce calculeaza DFT. In stanga si in dreapta ei apare aceeasi poza, mutata cu 8 casute. Sagetile arata ca bata de la $k = 7$ este aceeasi cu cea de la $k = -1$, iar cea de la $k = 6$ cu cea de la $k = -2$.

Este varianta cu casute a propozitiei din §2.3 ("spectrul unui semnal digital se repeta la fiecare 1"): $N$ casute inseamna frecventa normalizata $N\cdot\frac1N = 1$, adica $f_s$ in Hz.

===== 7. DFT a unui cosinus =====

Asta este sectiunea de care ai nevoie la probleme: cum desenezi $|X(k)|$ **fara** sa faci tot calculul din §4.

<note important>
**Presupunere pentru tot capitolul:** fiecare cosinus "cade exact pe o casuta", adica face un numar **intreg** de cicluri in cele $N$ esantioane. Daca nu cade pe o casuta (de exemplu 8.5 cicluri in 32 de esantioane), spectrul se imprastie. Cazul acela este in [[ps:cap8-leakage-ferestre|Cap 8]].
</note>

==== 7.1 Intai cu numere ====

Luam $N = 16$ esantioane din $x(n) = 3\cos\left(2\pi\cdot\frac{2}{16}\cdot n\right)$.

  * Amplitudinea este $A = 3$.
  * Frecventa normalizata este $\frac{2}{16}$: cosinusul face **2 cicluri intregi** in cele 16 esantioane. Cade exact pe casuta $m = 2$.

Calculul complet al DFT (facut cu calculatorul) da: **24 la $k = 2$, 24 la $k = 14$, si 0 in toate celelalte 14 casute.**

{{ps:cap6:dft_cos.png?950|DFT a unui cosinus}}

**Ce vezi in desen:** in stanga cele 16 esantioane (betele) si cosinusul din care provin (linia intrerupta); se vad cele 2 cicluri. In dreapta $|X(k)|$: doua bete de inaltime 24, la $k = 2$ si la $k = 14 = 16 - 2$.

De unde vine 24: $16\cdot\frac{3}{2} = 24$, adica $N\cdot\frac{A}{2}$.

==== 7.2 De unde vine N·A/2 ====

**Pas 1 — cosinusul este facut din doua ace.** Din formula lui Euler ([[ps:cap0-baze|Cap 0 §4.3]]):

$$ A\cos\left(2\pi\frac{m}{N}n\right) = \frac{A}{2}\,e^{\,j2\pi\frac{m}{N}n} + \frac{A}{2}\,e^{-j2\pi\frac{m}{N}n} $$

Doua ace de lungime $\frac{A}{2}$, care se rotesc in sensuri opuse, cu $m$ ture in $N$ esantioane. Acesta este acel "$A/2$" din Cap 0.

**Pas 2 — ce da un singur ac.** Am vazut in §4.6: un ac de lungime 1 care face $m$ ture in $N$ esantioane da, in casuta potrivita $k = m$, cele $N$ produse egale cu 1. Suma lor este $N$. In toate celelalte casute da 0.

**Pas 3 — punem cap la cap.**
  * Primul ac are lungimea $\frac{A}{2}$ si se potriveste cu casuta $k = m$: da $\frac{A}{2}\cdot N$.
  * Al doilea ac se roteste invers, deci se potriveste cu casuta $k = -m$, care este casuta $N - m$ (§6): da tot $\frac{A}{2}\cdot N$.

$$ \boxed{x(n) = A\cos\left(2\pi\frac{m}{N}n\right) \quad\Longrightarrow\quad |X(k)| = \frac{N\cdot A}{2}\ \text{ la } k = m \text{ si la } k = N - m;\quad 0 \text{ in rest}} $$

Verificare cu exemplul de mana din §4: $N = 4$, $A = 1$, $m = 1$ → $4\cdot\frac12 = 2$ la $k = 1$ si $k = 3$. Corect.

<note tip>
**De ce $N\cdot A/2$ si nu $A/2$, ca in Cap 0?** Pentru ca DFT aduna $N$ produse si nu imparte la $N$. Impartirea la $N$ se face la drumul inapoi (§8). Daca ai desenul si vrei amplitudinea cosinusului, intorci formula: $A = \frac{2\cdot|X(m)|}{N}$. Exemplu: $\frac{2\cdot 24}{16} = 3$.
</note>

<note tip>
**Cum aflu $m$ cand cosinusul e dat in Hz?** Din $f_k = k\cdot f_s/N$ (§5.2): $m = \frac{N\cdot f_c}{f_s}$. Exemplu: 2000 Hz, $f_s = 8000$ Hz, $N = 8$ → $m = \frac{8\cdot 2000}{8000} = 2$. Daca $m$ nu iese numar intreg, cosinusul nu cade pe o casuta (Cap 8).
</note>

==== 7.3 Cum scrie cursul acelasi lucru: cu delta ====

In curs rezultatul este scris asa:

$$ X(k) = \frac{N\cdot A}{2}\,\big(\delta(k - m) + \delta(k + m)\big) $$

$\delta$ ("delta") este un mod scurt de a scrie "o bata intr-un singur loc":

$$ \delta(n) = \begin{cases} 1, & n = 0 \\ 0, & n \neq 0 \end{cases} $$

Adica $\delta(\dots)$ este 1 cand ce e in paranteza este 0, si este 0 in rest.
  * $\delta(k - m)$ este 1 doar cand $k - m = 0$, adica la $k = m$: **o bata la $k = m$**.
  * $\delta(k + m)$ este 1 doar cand $k + m = 0$, adica la $k = -m$: **o bata la $k = -m$**, care este casuta $N - m$.

Exemplul din §7.1 scris asa: $X(k) = 24\,(\delta(k - 2) + \delta(k + 2))$.

==== 7.4 Alte cazuri pe care le intalnesti ====

^ Ce este in lista ^ Ce da DFT ^ De ce ^ Exemplu verificat ^
| o constanta $c$ | **o singura bata, $N\cdot c$, la $k = 0$** | constanta este un singur ac care nu se roteste, de lungime $c$ (nu doua jumatati) | $[2, 2, 2, 2]$ → $X(0) = 4\cdot 2 = 8$ |
| $A\sin\left(2\pi\frac{m}{N}n\right)$ | aceleasi doua bete, $N\cdot A/2$, la $k = m$ si $k = N - m$ | sinusul e un cosinus intarziat; se schimba doar faza (§4.7) | $[0, 1, 0, -1]$ → $\lvert X\rvert = [0, 2, 0, 2]$ |
| cosinus exact pe casuta din mijloc, $m = N/2$ | **o singura bata, $N\cdot A$, la $k = N/2$** | cele doua bete ar fi la $N/2$ si la $N - N/2 = N/2$: cad in aceeasi casuta si se aduna | $3\cos(\pi n) = [3, -3, 3, -3, \dots]$, $N = 8$ → $X(4) = 24$ |
| suma de mai multe cosinusuri | betele fiecaruia, puse pe acelasi desen | DFT a unei sume = suma DFT-urilor (liniaritate, §8) | vezi problemele din §9 |

===== 8. IDFT si proprietatile DFT =====

==== 8.1 Drumul inapoi: IDFT ====

**IDFT** (Inverse DFT, "DFT inversa") face drumul invers: din cele $N$ valori $X(k)$ reface lista $x(n)$.

Intai cu numere. Plecam de la $X = [0, 2, 0, 2]$ (rezultatul din §4.4) si vrem lista inapoi. Reteta este aceeasi, cu doua schimbari: acul se roteste **invers** (plus in loc de minus) si la sfarsit **impartim la $N$**.

Pentru $N = 4$, pozitiile acului care se roteste invers acelor de ceas sunt: casuta 1 → $1, j, -1, -j$ (pentru $n = 0, 1, 2, 3$); casuta 3 → $1, -j, -1, j$. Casutele 0 si 2 nu conteaza, fiindca $X(0) = X(2) = 0$.

  * $x(0) = \frac14\,(2\cdot 1 + 2\cdot 1) = \frac44 = 1$
  * $x(1) = \frac14\,(2\cdot j + 2\cdot(-j)) = \frac04 = 0$
  * $x(2) = \frac14\,(2\cdot(-1) + 2\cdot(-1)) = \frac{-4}{4} = -1$
  * $x(3) = \frac14\,(2\cdot(-j) + 2\cdot j) = \frac04 = 0$

Am regasit $x = [1, 0, -1, 0]$. Nu s-a pierdut nimic.

Acelasi lucru, scris cu litere:

$$ \boxed{x(n) = \frac{1}{N}\sum_{k=0}^{N-1} X(k)\, e^{\,j2\pi\frac{k}{N}n}, \qquad n = 0, 1, \dots, N-1} $$

**In cuvinte:** lista este o suma de $N$ ace care se rotesc cu viteze diferite. $X(k)/N$ spune cat de lung este acul numarul $k$ si din ce pozitie porneste. DFT desface lista in ace; IDFT le aduna la loc.

<note tip>
**De ce se imparte la $N$?** Pentru ca DFT a adunat $N$ produse si a iesit de $N$ ori "prea mare" (§7.2). Drumul inapoi trebuie sa anuleze asta. Fara impartire am fi obtinut $[4, 0, -4, 0]$ in loc de $[1, 0, -1, 0]$.
</note>

==== 8.2 Proprietatile DFT ====

Cursul spune ca proprietatile transformatei Fourier din analog ([[ps:cap2-serii-fourier|Cap 2 §4]], [[ps:cap3-transformata-fourier-am|Cap 3 §2]]) raman valabile si pentru DFT. Iata-le, fiecare cu un exemplu verificat numeric.

^ Proprietatea ^ In cuvinte ^ Exemplu ^
| **$N$ numere intra, $N$ numere ies** | lista si spectrul au acelasi numar de elemente; numarul de esantioane $N$ hotaraste cate casute de frecventa vezi | $N = 4$: 4 esantioane → $X(0) \dots X(3)$ |
| **Liniaritate** | spectrul unei sume este suma spectrelor; daca inmultesti lista cu un numar, spectrul se inmulteste cu acelasi numar | cosinus pe casuta 1 + cosinus pe casuta 2 → betele amandurora (P1 din §9) |
| **Periodicitate**: $X(k + N) = X(k)$ | spectrul se repeta la fiecare $N$ casute | $N = 8$: $X(7) = X(-1)$ (§6.5) |
| **Simetrie** (semnale reale): $\lvert X(N-k)\rvert = \lvert X(k)\rvert$ | betele vin in perechi; jumatatea de sus este oglinda celei de jos | $N = 4$: $\lvert X(1)\rvert = \lvert X(3)\rvert = 2$ (§6.3) |
| **Deplasare in timp** (intarziere) | daca intarzii lista, modulele $\lvert X(k)\rvert$ raman la fel; se schimba doar fazele | $[1, 0, -1, 0]$ si $[0, 1, 0, -1]$ au amandoua $\lvert X\rvert = [0, 2, 0, 2]$ (§4.7) |
| **Deplasare in frecventa** | daca inmultesti lista cu un ac care se roteste, $e^{\,j2\pi\frac{m}{N}n}$, tot spectrul se muta cu $m$ casute | $[1, 0, -1, 0]$ inmultita cu $[1, -j, -1, j]$ da $[1, 0, 1, 0]$, cu $X = [2, 0, 2, 0]$: betele de la $k = 1, 3$ s-au mutat cu o casuta la stanga, la $k = 0, 2$ |
| **$X(0)$ = suma esantioanelor** | casuta 0 masoara partea constanta: $X(0) = N\cdot$ media listei | $[3, 1, -1, 1]$: suma 4, media 1, $X(0) = 4$ |
| **Parseval** (energia) | energia calculata din lista este aceeasi cu cea calculata din spectru: $\sum \lvert x(n)\rvert^2 = \frac1N\sum \lvert X(k)\rvert^2$ | $[1, 0, -1, 0]$: $1 + 0 + 1 + 0 = 2$ si $\frac14(0 + 4 + 0 + 4) = 2$ |

<note tip>
**Unde ai mai vazut deplasarea in frecventa?** Este pasul IQ din [[ps:cap4-esantionare|Cap 4 §6]]: inmultirea cu $[1, -j, -1, j, \dots] = e^{-j\frac{\pi}{2}n}$ muta tot spectrul cu $f_s/4$ la stanga. In casute, $f_s/4$ inseamna $N/4$ casute; pentru $N = 4$, o casuta. Exact ce se vede in exemplul din tabel.
</note>

Mai exista o proprietate importanta, care leaga DFT de filtrare: **teorema convolutiei**. Ea are capitolul ei: [[ps:cap7-convolutie|Cap 7]].

**DFT si FFT.** FFT (Fast Fourier Transform) este un mod **mai rapid** de a calcula **exact aceleasi** valori $X(k)$. Tot ce scrie in capitolul asta este valabil si pentru FFT. Cum functioneaza si cat de rapida este: [[ps:cap11-fft|Cap 11]].

===== 9. Probleme rezolvate pe puncte =====

<note>
**Reteta pentru "cum arata $|X(k)|$?"** (semnal = suma de cosinusuri care cad pe casute)
  - Scrie fiecare cosinus in forma $A\cos\left(2\pi\frac{m}{N}n\right)$. Daca e dat in Hz: $m = \frac{N\cdot f_c}{f_s}$. Verifica daca $m$ este numar intreg.
  - Fiecare cosinus da **doua bete de inaltime $N\cdot A/2$**: la $k = m$ si la $k = N - m$. (O constanta $c$ da o singura bata $N\cdot c$ la $k = 0$.)
  - Pune toate betele pe acelasi desen (liniaritate). In rest, 0.
  - Eticheteaza axele: $k$ pe orizontala, $|X(k)|$ pe verticala, cu inaltimile scrise. Daca se cer Hz: $f_k = k\cdot f_s/N$.
</note>

==== P1 — doua cosinusuri, f_s = 8000 Hz, N = 8 (Test 1 din curs) ====

<note important>
Fie $x(n) = \cos(2\pi f_1 nT_s) + \cos(2\pi f_2 nT_s)$, cu $f_1 = 1000$ Hz, $f_2 = 2000$ Hz, $T_s = \frac{1}{8000}$ s. Luam $N = 8$ esantioane.
  - **a)** Scrie semnalul cu frecvente normalizate. Pe ce casute cad cele doua cosinusuri?
  - **b)** Calculeaza $X(k)$ si deseneaza $|X(k)|$.
  - **c)** Ce frecvente reale (in Hz) corespund betelor?
</note>

**PUNCTUL a)**

**Ce se cere:** sa scriem fiecare cosinus ca $\cos\left(2\pi\frac{m}{N}n\right)$ si sa aflam $m$.

**Ce stim:** $f_1 = 1000$ Hz, $f_2 = 2000$ Hz, $T_s = 1/8000$ s, $N = 8$.

**Pasi:**
  - Frecventa de esantionare: $f_s = 1/T_s = 8000$ Hz.
  - Inlocuim $T_s$: $\cos(2\pi\cdot 1000\cdot n\cdot\frac{1}{8000}) = \cos\left(2\pi\cdot\frac{1}{8}\cdot n\right)$. Frecventa normalizata $\frac18$, deci $m_1 = 1$.
  - La fel: $\cos(2\pi\cdot 2000\cdot n\cdot\frac{1}{8000}) = \cos\left(2\pi\cdot\frac{2}{8}\cdot n\right)$. Frecventa normalizata $\frac28$, deci $m_2 = 2$.
  - Verificare cu formula din §7.2: $m_1 = \frac{8\cdot 1000}{8000} = 1$, $m_2 = \frac{8\cdot 2000}{8000} = 2$. Sunt intregi, deci cad pe casute.

<note tip>
**Raspuns a):** $x(n) = \cos\left(2\pi\frac18 n\right) + \cos\left(2\pi\frac28 n\right)$. Primul cosinus cade pe casuta $m = 1$, al doilea pe casuta $m = 2$. Amandoua au amplitudinea $A = 1$.
</note>

**PUNCTUL b)**

**Ce se cere:** valorile $X(k)$ pentru $k = 0 \dots 7$ si desenul modulului.

**Ce stim:** de la a), $m_1 = 1$, $m_2 = 2$, $A = 1$ pentru amandoua, $N = 8$.

**Pasi:**
  - Inaltimea betelor: $N\cdot\frac{A}{2} = 8\cdot\frac12 = 4$, pentru fiecare cosinus.
  - Primul cosinus ($m = 1$): bete la $k = 1$ si la $k = N - 1 = 7$. Cu delta: $X_1(k) = 4\,(\delta(k-1) + \delta(k+1))$.
  - Al doilea cosinus ($m = 2$): bete la $k = 2$ si la $k = N - 2 = 6$. Cu delta: $X_2(k) = 4\,(\delta(k-2) + \delta(k+2))$.
  - Le adunam (liniaritate): $X(k) = X_1(k) + X_2(k)$.

<note tip>
**De ce $k = 7$ si $k = 6$?** $\delta(k+1)$ inseamna o bata la $k = -1$. Casuta $-1$ este casuta $-1 + 8 = 7$ (§6.2). La fel, $k = -2$ este casuta $6$.
</note>

{{ps:cap6:p1_doua_cos.png?950|P1: lista si spectrul}}

**Ce vezi in desen:** in stanga cele 8 esantioane ale lui $x(n)$. In dreapta raspunsul: patru bete de inaltime 4, la $k = 1, 2, 6, 7$. Sub fiecare $k$ scrie frecventa reala (pentru punctul c).

<note tip>
**Raspuns b):** $X(k) = 4\,(\delta(k-1) + \delta(k+1)) + 4\,(\delta(k-2) + \delta(k+2))$. Pe desen: **$|X(k)| = 4$ la $k = 1, 2, 6, 7$** si 0 la $k = 0, 3, 4, 5$.
</note>

<note>
**In notitele de curs desenul are 8 bete**, la $k = \pm1, \pm2, \pm6, \pm7$, pentru ca axa e desenata de la $-7$ la $7$. Este acelasi spectru, vazut pe mai mult de o perioada (§6.5): bata de la $k = -1$ este aceeasi cu cea de la $k = 7$, cea de la $k = -7$ aceeasi cu cea de la $k = 1$ si asa mai departe. Intr-o fereastra de $N = 8$ casute la rand sunt doar 4 bete.
</note>

**PUNCTUL c)**

**Ce se cere:** frecventa in Hz pentru fiecare bata.

**Ce stim:** betele sunt la $k = 1, 2, 6, 7$; $f_s = 8000$ Hz, $N = 8$.

**Pasi:**
  - Pasul dintre casute: $f_s/N = 8000/8 = 1000$ Hz.
  - $k = 1$ → $1\cdot 1000 = 1000$ Hz. $k = 2$ → $2000$ Hz.
  - $k = 6$ este in jumatatea de sus, deci frecventa adevarata e cea a casutei $6 - 8 = -2$: $-2000$ Hz.
  - $k = 7$ → casuta $7 - 8 = -1$: $-1000$ Hz.

<note tip>
**Raspuns c):** betele sunt la $\pm 1000$ Hz si $\pm 2000$ Hz. Sunt exact frecventele $f_1$ si $f_2$ din enunt, fiecare cu perechea ei negativa.
</note>

----

==== P2 — testul din Cursul 13: N = 16 ====

<note important>
Fie $x(n) = 10\cos\left(2\pi\frac{3}{16}n\right) + 20\cos\left(2\pi\frac{5}{16}n\right)$. Daca folosim DFT/FFT cu $N = 16$, cum arata spectrul $|X(k)|$?
  - **a)** Pe ce casute cad cosinusurile si ce amplitudini au?
  - **b)** Ce inaltime au betele?
  - **c)** Deseneaza $|X(k)|$.
  - **d)** (in plus) Daca semnalul a fost esantionat cu $f_s = 16$ kHz, ce frecvente reale are?
</note>

**PUNCTUL a)**

**Ce se cere:** $m$ si $A$ pentru fiecare cosinus.

**Ce stim:** semnalul este deja scris cu frecvente normalizate; $N = 16$.

**Pasi:**
  - Comparam cu forma $A\cos\left(2\pi\frac{m}{N}n\right)$, cu $N = 16$.
  - Primul termen: $10\cos\left(2\pi\frac{3}{16}n\right)$ → $A_1 = 10$, $m_1 = 3$.
  - Al doilea termen: $20\cos\left(2\pi\frac{5}{16}n\right)$ → $A_2 = 20$, $m_2 = 5$.

<note tip>
**Raspuns a):** primul cosinus: amplitudine 10, casuta 3. Al doilea: amplitudine 20, casuta 5. Amandoua cad exact pe casute (numitorul fractiei este chiar $N = 16$).
</note>

**PUNCTUL b)**

**Ce se cere:** inaltimea fiecarei bete.

**Ce stim:** $N = 16$, $A_1 = 10$, $A_2 = 20$.

**Pasi:**
  - Regula: inaltimea este $N\cdot\frac{A}{2}$.
  - Primul cosinus: $16\cdot\frac{10}{2} = 16\cdot 5 = 80$.
  - Al doilea cosinus: $16\cdot\frac{20}{2} = 16\cdot 10 = 160$.

<note tip>
**Raspuns b):** **80** pentru cosinusul de amplitudine 10 si **160** pentru cel de amplitudine 20.
</note>

<note warning>
**Atentie: $N\cdot A/2$, nu $N\cdot A$.** In notitele colegilor (p. 29) pe grafic sunt trecute valorile 160 si 320. Dar calculul de pe aceeasi pagina este $S(k) = 5\cdot 16\,(\dots) + 10\cdot 16\,(\dots)$, adica 80 si 160. Am verificat si cu calculatorul: valorile corecte sunt **80 si 160**. Cel mai probabil pe grafic s-a uitat impartirea la 2.
</note>

**PUNCTUL c)**

**Ce se cere:** desenul $|X(k)|$, cu axele etichetate.

**Ce stim:** bete de 80 pentru $m = 3$ si de 160 pentru $m = 5$; $N = 16$.

**Pasi:**
  - Cosinusul cu $m = 3$: bete la $k = 3$ si la $k = N - 3 = 13$.
  - Cosinusul cu $m = 5$: bete la $k = 5$ si la $k = N - 5 = 11$.
  - Restul casutelor: 0.
  - Cu delta: $X(k) = 80\,(\delta(k-3) + \delta(k+3)) + 160\,(\delta(k-5) + \delta(k+5))$.

{{ps:cap6:p2_n16.png?950|P2: spectrul pentru N = 16}}

**Ce vezi in desen:** acelasi raspuns in doua feluri. Sus, cum iese din DFT: $k$ de la 0 la 15, cu betele la $k = 3, 5, 11, 13$. Jos, cu 0 la mijloc (cum e desenat la curs): $k$ de la $-8$ la 7, cu betele la $k = \pm 3$ si $k = \pm 5$. Oricare dintre ele e un raspuns corect.

<note tip>
**Raspuns c):** $|X(k)| = 80$ la $k = 3$ si $k = 13$ (adica $k = \pm 3$); $|X(k)| = 160$ la $k = 5$ si $k = 11$ (adica $k = \pm 5$); 0 in rest.
</note>

**PUNCTUL d)**

**Ce se cere:** frecventele in Hz, daca $f_s = 16$ kHz.

**Ce stim:** betele sunt la $k = \pm 3$ si $k = \pm 5$; $N = 16$; $f_s = 16000$ Hz.

**Pasi:**
  - Pasul dintre casute: $f_s/N = 16000/16 = 1000$ Hz.
  - $k = 3$ → $3\cdot 1000 = 3000$ Hz. $k = 5$ → $5000$ Hz.

<note tip>
**Raspuns d):** un cosinus de 3 kHz cu amplitudinea 10 si unul de 5 kHz cu amplitudinea 20. Amandoua sunt sub $f_s/2 = 8$ kHz, deci nu e aliasing.
</note>

----

==== P3 — citirea inversa: din spectru in semnal ====

<note important>
Un semnal real a fost esantionat cu $f_s = 2000$ Hz. S-au luat $N = 20$ esantioane si s-a calculat DFT. Modulul $|X(k)|$ este cel din desen: 40 la $k = 0$; 30 la $k = 3$ si $k = 17$; 10 la $k = 5$ si $k = 15$; 0 in rest.
  - **a)** Ce frecventa reala are fiecare bata?
  - **b)** Ce amplitudine are fiecare componenta?
  - **c)** Scrie semnalul $x(n)$ si semnalul analog $x(t)$ din care provine.
</note>

{{ps:cap6:p3_citire.png?900|P3: spectrul dat}}

**Ce vezi in desen:** enuntul. Pe orizontala indicele casutei $k$ (de la 0 la 19), pe verticala $|X(k)|$. Sunt cinci bete.

**PUNCTUL a)**

**Ce se cere:** frecventa in Hz pentru fiecare bata.

**Ce stim:** $f_s = 2000$ Hz, $N = 20$; bete la $k = 0, 3, 5, 15, 17$.

**Pasi:**
  - Pasul dintre casute: $f_s/N = 2000/20 = 100$ Hz.
  - $k = 0$ → 0 Hz. Este partea constanta a semnalului.
  - $k = 3$ → $3\cdot 100 = 300$ Hz. $k = 5$ → $500$ Hz.
  - $k = 17$ este in jumatatea de sus ($17 > N/2 = 10$): casuta $17 - 20 = -3$ → $-300$ Hz. Este perechea betei de la $k = 3$.
  - $k = 15$ → casuta $15 - 20 = -5$ → $-500$ Hz. Este perechea betei de la $k = 5$.

<note tip>
**Raspuns a):** 0 Hz (constanta), $\pm 300$ Hz, $\pm 500$ Hz. Deci in semnal sunt: o constanta, un cosinus de 300 Hz si un cosinus de 500 Hz. **Betele de la $k = 15$ si $k = 17$ nu sunt cosinusuri in plus**: sunt jumatatile negative ale celor doua cosinusuri.
</note>

**PUNCTUL b)**

**Ce se cere:** valoarea constantei si amplitudinile cosinusurilor.

**Ce stim:** inaltimile betelor: 40, 30, 10; $N = 20$.

**Pasi:**
  - Constanta: bata de la $k = 0$ are inaltimea $N\cdot c$ (§7.4). Deci $c = \frac{40}{20} = 2$.
  - Cosinusul de 300 Hz: bata are inaltimea $N\cdot\frac{A}{2}$. Deci $A = \frac{2\cdot 30}{20} = 3$.
  - Cosinusul de 500 Hz: $A = \frac{2\cdot 10}{20} = 1$.

<note tip>
**De ce la constanta impart doar la $N$, iar la cosinus inmultesc si cu 2?** Constanta are o singura bata, care contine tot. Cosinusul isi imparte amplitudinea in doua bete egale (la $+f$ si la $-f$), fiecare cu jumatate.
</note>

<note tip>
**Raspuns b):** constanta 2; amplitudinea 3 la 300 Hz; amplitudinea 1 la 500 Hz.
</note>

**PUNCTUL c)**

**Ce se cere:** formula lui $x(n)$ si a lui $x(t)$.

**Ce stim:** de la a) si b): constanta 2; $A = 3$ pe casuta 3 (300 Hz); $A = 1$ pe casuta 5 (500 Hz).

**Pasi:**
  - In casute: $x(n) = 2 + 3\cos\left(2\pi\frac{3}{20}n\right) + \cos\left(2\pi\frac{5}{20}n\right)$.
  - In Hz, inlocuind $\frac{m}{N}n$ cu $f_c\cdot t$: $x(t) = 2 + 3\cos(2\pi\cdot 300\,t) + \cos(2\pi\cdot 500\,t)$.
  - Verificare (cu calculatorul): DFT pentru aceasta lista da exact 40, 30, 10, 10, 30 in casutele 0, 3, 5, 15, 17.

<note tip>
**Raspuns c):** $x(t) = 2 + 3\cos(2\pi\cdot 300\,t) + \cos(2\pi\cdot 500\,t)$. Observatie: din **modul** nu se vede faza. In loc de cosinus putea fi sinus sau un cosinus intarziat; desenul $|X(k)|$ ar fi fost acelasi (§4.7). Daca nu se da faza, scrii cu cosinus si mentionezi asta.
</note>

===== 10. Ce trebuie sa stii din Cap 6 (fisa de 1 minut) =====

  * Dupa ADC avem o lista de $N$ numere $x(n)$, $n = 0 \dots N-1$. **DFT** ii calculeaza spectrul: $N$ numere $X(k)$, $k = 0 \dots N-1$.
  * **Frecventa normalizata:** $f = f_c/f_s$, fara unitate ("cicluri pe esantion"). Conteaza doar $f \in [-1/2, 1/2]$, adica $[-f_s/2, f_s/2]$; spectrul se repeta la fiecare 1 (la fiecare $f_s$).
  * **DTFT:** $X(f) = \sum_{n=-\infty}^{\infty} x(n)e^{-j2\pi fn}$. Buna pentru teorie; nu se poate calcula pe calculator (o infinitate de esantioane, $f$ continuu).
  * **DFT:** $X(k) = \sum_{n=0}^{N-1} x(n)\,e^{-j2\pi\frac{k}{N}n}$. **IDFT:** $x(n) = \frac1N\sum_{k=0}^{N-1} X(k)\,e^{\,j2\pi\frac{k}{N}n}$.
  * **$k$ → Hz:** $f_k = k\cdot f_s/N$. **Rezolutia** (pasul dintre casute): $f_s/N$. Se imbunatateste marind $N$.
  * **Jumatatea de sus** ($k > N/2$) = frecventele negative: casuta $k$ este casuta $k - N$. $X(k+N) = X(k)$ (periodic cu $N$).
  * **Semnal real:** $|X(N-k)| = |X(k)|$ (betele vin in perechi).
  * **Cosinus pe casuta $m$:** $A\cos(2\pi\frac{m}{N}n)$ → doua bete $N\cdot A/2$ la $k = m$ si $k = N - m$. Cu delta: $\frac{NA}{2}(\delta(k-m) + \delta(k+m))$. Invers: $A = 2|X(m)|/N$.
  * **Constanta $c$:** o bata $N\cdot c$ la $k = 0$. **Sinus:** acelasi modul ca la cosinus.
  * $m = N\cdot f_c/f_s$ trebuie sa fie intreg; altfel apare leakage ([[ps:cap8-leakage-ferestre|Cap 8]]).
  * DFT si FFT dau aceleasi valori; FFT e doar mai rapida ([[ps:cap11-fft|Cap 11]]).

===== 11. Grile de verificare =====

**G1.** Un semnal este esantionat cu $f_s = 6400$ Hz si se calculeaza DFT pe $N = 64$ esantioane. Casuta $k = 5$ corespunde frecventei:
  - A. 5 Hz
  - B. 500 Hz
  - C. 320 Hz
  - D. 6400 Hz

**G2.** $x(n) = 4\cos\left(2\pi\cdot 300\cdot\frac{n}{1200}\right)$, cu $N = 12$ esantioane. $|X(k)|$ este diferit de zero:
  - A. doar la $k = 3$, cu inaltimea 4
  - B. la $k = 3$ si $k = 9$, cu inaltimea 24
  - C. la $k = 3$ si $k = 9$, cu inaltimea 48
  - D. la $k = 300$, cu inaltimea 2

**G3.** Vrei ca DFT sa deosebeasca doua frecvente foarte apropiate (rezolutie mai fina). Ce faci?
  - A. maresti $f_s$ si pastrezi $N$
  - B. maresti $N$ si pastrezi $f_s$
  - C. maresti amplitudinea semnalului
  - D. aplici ''fftshift''

**G4.** $N = 8$, $f_s = 8000$ Hz, semnal real. In spectru apare o bata la $k = 7$. Ea reprezinta:
  - A. o componenta de 7000 Hz, separata de restul
  - B. componenta de $-1000$ Hz, perechea betei de la $k = 1$
  - C. zgomot de cuantizare
  - D. o eroare de calcul

**G5.** De ce nu putem calcula DTFT pe calculator?
  - A. pentru ca foloseste numere complexe
  - B. pentru ca cere o infinitate de esantioane si da rezultat pentru o infinitate de frecvente
  - C. pentru ca merge doar la semnale periodice
  - D. pentru ca este prea lenta; de aceea folosim FFT

**G6.** DFT a listei constante $x = [5, 5, 5, 5]$ este:
  - A. $[5, 0, 0, 0]$
  - B. $[20, 0, 0, 0]$
  - C. $[10, 0, 0, 10]$
  - D. $[0, 20, 0, 20]$

**G7.** Avem lista unui cosinus si lista aceluiasi cosinus intarziat cu un esantion. Modulele $|X(k)|$ ale celor doua liste sunt:
  - A. identice
  - B. deplasate cu o casuta una fata de alta
  - C. a doua are betele pe jumatate
  - D. a doua este zero peste tot

**G8.** In spectrul DFT al unui semnal real, cu $N = 100$, apare o bata de inaltime 250 la $k = 10$ (si perechea ei la $k = 90$). Amplitudinea cosinusului este:
  - A. 250
  - B. 2.5
  - C. 5
  - D. 125

(Raspunsurile sunt in sectiunea 13.)

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

Raspunsurile sunt scrise asa cum le-ai pune pe foaie: scurt, cu formula si cu un exemplu.

**T1. (examen 2023 A, 2026) Despre DFT: ce interval de frecvente analizeaza, care e legatura dintre $k$ si frecventele reale, ce proprietati are?**

<note>
  * **Interval:** DFT pe $N$ esantioane da $N$ valori $X(k)$, $k = 0 \dots N-1$, care acopera frecventele de la 0 pana la $f_s$ (fara $f_s$), in pasi de $f_s/N$. Echivalent, intervalul $[-f_s/2, f_s/2]$: casutele cu $k > N/2$ sunt frecventele negative ($k - N$).
  * **Legatura $k$ ↔ Hz:** $f_k = k\cdot f_s/N$. Exemplu: $N = 8$, $f_s = 8000$ Hz, $k = 3$ → 3000 Hz. Rezolutia este $f_s/N$.
  * **Proprietati:** liniaritate; spectru periodic cu perioada $N$, $X(k+N) = X(k)$; simetrie pentru semnale reale, $|X(N-k)| = |X(k)|$; intarzierea in timp schimba doar faza; inmultirea cu $e^{j2\pi mn/N}$ deplaseaza spectrul cu $m$ casute.
</note>

**T2. De ce folosim DFT si nu DTFT?**

<note>
DTFT, $X(f) = \sum_{n=-\infty}^{\infty} x(n)e^{-j2\pi fn}$, cere o infinitate de esantioane si da un spectru continuu (o infinitate de valori ale lui $f$). Niciuna nu se poate face pe calculator. DFT foloseste un numar finit $N$ de esantioane si calculeaza spectrul doar la $N$ frecvente, $f = k/N$. De aceea DFT (calculata rapid cu FFT) este varianta practica.
</note>

**T3. Ce este frecventa normalizata si in ce interval ia valori?**

<note>
Este raportul dintre frecventa semnalului si frecventa de esantionare: $f = f_c/f_s$. Nu are unitate de masura. Apare cand inlocuim $t = nT_s$: $\cos(2\pi f_c nT_s) = \cos(2\pi fn)$. Pentru ca $e^{j2\pi(f+1)n} = e^{j2\pi fn}$, spectrul se repeta la fiecare 1, deci ne intereseaza doar $f \in [-1/2, 1/2]$ (sau $[0, 1]$), adica $f_c \in [-f_s/2, f_s/2]$.
</note>

**T4. Cum arata spectrul DFT al semnalului $A\cos(2\pi\frac{m}{N}n)$? Dar al unei constante?**

<note>
Cosinusul se scrie $\frac{A}{2}(e^{j2\pi mn/N} + e^{-j2\pi mn/N})$. Fiecare exponentiala da $N$ in casuta ei si 0 in rest (ortogonalitate). Rezulta $X(k) = \frac{NA}{2}(\delta(k-m) + \delta(k+m))$: doua bete de inaltime $NA/2$, la $k = m$ si $k = N - m$. O constanta $c$ da o singura bata, $X(0) = Nc$.
</note>

**T5. Ce este rezolutia in frecventa a DFT si cum o putem imbunatati?**

<note>
Este distanta dintre doua casute vecine: $f_s/N$ (in Hz), adica 1 impartit la durata inregistrarii. O imbunatatim marind numarul de esantioane $N$ (inregistram mai mult timp) la acelasi $f_s$. Daca marim doar $f_s$, rezolutia se inrautateste.
</note>

**T6. (examen 2023 A, 2026) Ce diferenta este intre DFT si FFT?**

<note>
Calculeaza aceleasi valori $X(k)$. DFT aplicata direct are nevoie de aproximativ $N^2$ operatii (pentru fiecare din cele $N$ casute, o suma cu $N$ termeni). FFT este un algoritm rapid care obtine acelasi rezultat in aproximativ $N\log_2 N$ operatii. Detalii in [[ps:cap11-fft|Cap 11]].
</note>

**T7. Scrie formulele DFT si IDFT si explica termenii.**

<note>
$X(k) = \sum_{n=0}^{N-1} x(n)e^{-j2\pi kn/N}$ si $x(n) = \frac1N\sum_{k=0}^{N-1} X(k)e^{j2\pi kn/N}$. $x(n)$ = esantioanele semnalului; $N$ = numarul lor; $k$ = indicele componentei de frecventa (corespunde frecventei $k f_s/N$); $X(k)$ = numar complex al carui modul arata cat din acea frecventa este in semnal, iar faza arata intarzierea ei. IDFT reface exact semnalul din spectru.
</note>

===== 13. Raspunsuri la grile =====

^ Grila ^ Raspuns ^ De ce e corect ^ De ce sunt gresite celelalte ^
| G1 | **B** | $f_k = k\cdot f_s/N = 5\cdot 6400/64 = 5\cdot 100 = 500$ Hz | A: $k$ nu este direct in Hz. C: 320 ar fi $f_s/20$, fara legatura. D: $f_s$ ar fi casuta $k = 64$, care nici nu exista ($k$ merge pana la 63) |
| G2 | **B** | $f = 300/1200 = 3/12$, deci $m = 3$; bete la $k = 3$ si $k = 12 - 3 = 9$, de inaltime $N\cdot A/2 = 12\cdot 4/2 = 24$ | A: un cosinus are doua bete, iar inaltimea nu este $A$. C: 48 ar fi $N\cdot A$, fara impartirea la 2. D: $k$ merge doar pana la 11 |
| G3 | **B** | rezolutia este $f_s/N$; cu $N$ mai mare, pasul e mai mic | A: face $f_s/N$ mai mare, deci mai rau. C: amplitudinea schimba doar inaltimea betelor. D: ''fftshift'' doar rearanjeaza |
| G4 | **B** | casuta 7 este casuta $7 - 8 = -1$, adica $-1000$ Hz; la un semnal real betele vin in perechi, $\lvert X(7)\rvert = \lvert X(1)\rvert$ | A: 7000 Hz e peste $f_s/2 = 4000$ Hz, nu poate fi reprezentata separat. C, D: bata apare la orice cosinus de 1000 Hz, este normala |
| G5 | **B** | suma e peste o infinitate de esantioane, iar $f$ e continuu | A: si DFT foloseste numere complexe. C: DTFT e pentru orice lista. D: nu e "lenta", e imposibila; FFT este varianta rapida a DFT, nu a DTFT |
| G6 | **B** | o constanta $c$ da o singura bata $N\cdot c = 4\cdot 5 = 20$ la $k = 0$ (suma esantioanelor) | A: lipseste inmultirea cu $N$. C: constanta nu se imparte in doua bete; are una singura, la $k = 0$. D: betele la $k = 1, 3$ apar la un cosinus cu un ciclu in 4 esantioane |
| G7 | **A** | intarzierea schimba doar fazele; modulele raman aceleasi (§4.7) | B: deplasarea cu casute apare la inmultirea cu o exponentiala, nu la intarziere. C, D: intarzierea nu schimba cat din frecventa este in semnal |
| G8 | **C** | $A = 2\cdot\lvert X(m)\rvert/N = 2\cdot 250/100 = 5$ | A: inaltimea betei nu este amplitudinea. B: 2.5 ar fi $\lvert X\rvert/N$, fara inmultirea cu 2. D: 125 este jumatate din bata, nu amplitudinea |

----
**Urmatorul capitol:** [[ps:cap7-convolutie|Cap 7 — Convolutia si teorema convolutiei]]. Apoi: [[ps:cap8-leakage-ferestre|Cap 8 — ce se intampla cand cosinusul nu cade pe o casuta (leakage)]].