Cap 6 — Semnale discrete, DTFT si DFT

← inapoi la cuprins · Materie pentru examenul final · Carte: cap. 6.1–6.2 · Notitele colegilor: Cursurile 10–11 (p. 22–25) · Inainte: Cap 5 · Urmeaza: Cap 7 — Convolutia

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

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:

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

• in Cap 0 §6: vedeam $3\cos(2\pi\cdot 2t)$ si desenam doua linii de $3/2$ la $\pm 2$ Hz;
• in Cap 2: pentru semnale periodice calculam coeficientii $c_k$;
• in 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:

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

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:

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.

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:

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

Asta e exact ce am vazut in 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.

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

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.

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

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

1. Cere o infinitate de esantioane. Suma merge de la $-\infty$ la $+\infty$. Noi avem o lista cu un numar finit de numere.
2. 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.

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

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

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.

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

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

Pentru fiecare casuta $k$:

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

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

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

• $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 (Cap 0 §6.1). Casuta 3 este frecventa negativa. Explicatia completa este in §6.

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

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

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.

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

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

1. 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).
2. De la frecventa normalizata la Hz inmultim cu $f_s$ (§2.2): $\frac38\cdot 8000 = 3000$ Hz.

La fel pentru toate casutele:

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

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

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 Cap 8.

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

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.

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 (Cap 4 §3).

Amandoua au aceeasi explicatie.

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

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

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.

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.

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

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.

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

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.

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

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.

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

Pas 1 — cosinusul este facut din doua ace. Din formula lui Euler (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.

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

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.

Cursul spune ca proprietatile transformatei Fourier din analog (Cap 2 §4, Cap 3 §2) raman valabile si pentru DFT. Iata-le, fiecare cu un exemplu verificat numeric.

Mai exista o proprietate importanta, care leaga DFT de filtrare: teorema convolutiei. Ea are capitolul ei: 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: Cap 11.

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:

1. Frecventa de esantionare: $f_s = 1/T_s = 8000$ Hz.
2. 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$.
3. 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$.
4. 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.

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:

1. Inaltimea betelor: $N\cdot\frac{A}{2} = 8\cdot\frac12 = 4$, pentru fiecare cosinus.
2. 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))$.
3. 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))$.
4. Le adunam (liniaritate): $X(k) = X_1(k) + X_2(k)$.

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

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:

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

PUNCTUL a)

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

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

Pasi:

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

PUNCTUL b)

Ce se cere: inaltimea fiecarei bete.

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

Pasi:

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

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:

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

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.

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:

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

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:

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

PUNCTUL b)

Ce se cere: valoarea constantei si amplitudinile cosinusurilor.

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

Pasi:

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

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:

1. In casute: $x(n) = 2 + 3\cos\left(2\pi\frac{3}{20}n\right) + \cos\left(2\pi\frac{5}{20}n\right)$.
2. 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)$.
3. Verificare (cu calculatorul): DFT pentru aceasta lista da exact 40, 30, 10, 10, 30 in casutele 0, 3, 5, 15, 17.

• 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 (Cap 8).
• DFT si FFT dau aceleasi valori; FFT e doar mai rapida (Cap 11).

G1. Un semnal este esantionat cu $f_s = 6400$ Hz si se calculeaza DFT pe $N = 64$ esantioane. Casuta $k = 5$ corespunde frecventei:

1. A. 5 Hz
2. B. 500 Hz
3. C. 320 Hz
4. 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:

1. A. doar la $k = 3$, cu inaltimea 4
2. B. la $k = 3$ si $k = 9$, cu inaltimea 24
3. C. la $k = 3$ si $k = 9$, cu inaltimea 48
4. D. la $k = 300$, cu inaltimea 2

G3. Vrei ca DFT sa deosebeasca doua frecvente foarte apropiate (rezolutie mai fina). Ce faci?

1. A. maresti $f_s$ si pastrezi $N$
2. B. maresti $N$ si pastrezi $f_s$
3. C. maresti amplitudinea semnalului
4. D. aplici fftshift

G4. $N = 8$, $f_s = 8000$ Hz, semnal real. In spectru apare o bata la $k = 7$. Ea reprezinta:

1. A. o componenta de 7000 Hz, separata de restul
2. B. componenta de $-1000$ Hz, perechea betei de la $k = 1$
3. C. zgomot de cuantizare
4. D. o eroare de calcul

G5. De ce nu putem calcula DTFT pe calculator?

1. A. pentru ca foloseste numere complexe
2. B. pentru ca cere o infinitate de esantioane si da rezultat pentru o infinitate de frecvente
3. C. pentru ca merge doar la semnale periodice
4. D. pentru ca este prea lenta; de aceea folosim FFT

G6. DFT a listei constante $x = [5, 5, 5, 5]$ este:

1. A. $[5, 0, 0, 0]$
2. B. $[20, 0, 0, 0]$
3. C. $[10, 0, 0, 10]$
4. 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:

1. A. identice
2. B. deplasate cu o casuta una fata de alta
3. C. a doua are betele pe jumatate
4. 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:

1. A. 250
2. B. 2.5
3. C. 5
4. D. 125

(Raspunsurile sunt in sectiunea 13.)

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?

T2. De ce folosim DFT si nu DTFT?

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

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

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

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

T7. Scrie formulele DFT si IDFT si explica termenii.

Urmatorul capitol: Cap 7 — Convolutia si teorema convolutiei. Apoi: Cap 8 — ce se intampla cand cosinusul nu cade pe o casuta (leakage).