Cap 8 — DFT leakage (scurgerea spectrala), zero-padding si ferestre

← inapoi la cuprins · Materie pentru EXAMEN (dupa partial) · Carte: cap. 6.4 · Inainte: Cap 6 — DFT si Cap 7 — Convolutia

Luam exemplul din curs: avem $N = 32$ esantioane.

Ca sa avem si Hz, alegem $f_s = 3200$ Hz (3200 de esantioane pe secunda). Atunci distanta dintre doua cutii vecine este

$$ \frac{f_s}{N} = \frac{3200}{32} = 100 \text{ Hz} $$

Deci cutiile sunt din 100 in 100 Hz:

Exista cutie la 800 Hz. Exista cutie la 900 Hz. NU exista cutie la 850 Hz. De aici vine toata problema.

$$ x_A(n) = \cos\left(2\pi \cdot \frac{8}{32} \cdot n\right) $$

Ce inseamna $8/32$: cosinusul face 8 perioade complete in cele 32 de esantioane. Frecventa lui in Hz este $8 \cdot f_s/32 = 8 \cdot 100 = 800$ Hz. Cade exact pe cutia $k = 8$.

Rezultatul DFT (regula din Cap 6, cu $N = 32$, $A = 1$): o linie de inaltime $N \cdot A/2 = 32 \cdot 1/2 = 16$ la $k = 8$, oglinda ei la $k = 32 - 8 = 24$, si zero in toate celelalte cutii.

$$ x_B(n) = \cos\left(2\pi \cdot \frac{8.5}{32} \cdot n\right) $$

Acum cosinusul face 8 perioade si jumatate in cele 32 de esantioane. Frecventa: $8.5 \cdot 100 = 850$ Hz. Ar trebui sa stea in “cutia 8.5”, dar o asemenea cutie nu exista.

Am calculat DFT-ul (cu calculatorul). Iata cateva valori, puse langa cele ale semnalului A:

Ce vezi in desen: pe orizontala e numarul cutiei $k$ (de la 0 la 31), pe verticala e $|X(k)|$. Sus (semnalul A): doua linii curate. Jos (semnalul B): nicio cutie nu mai e goala.

Trei lucruri de observat la semnalul B:

1. Nu mai avem o singura linie. Cele mai inalte sunt cutiile 8 si 9 (vecinele lui 8.5), cu inaltimi aproape egale: 10.25 si 10.15.
2. Niciuna nu ajunge la 16. Inaltimea “s-a impartit”.
3. Toate cutiile au ceva in ele, pana si cutia 0 si cutia 16, care sunt departe de 850 Hz.

Definitie in cuvinte simple. DFT leakage (scurgerea spectrala) = fenomenul prin care o frecventa care nu cade exact pe o cutie a DFT-ului apare imprastiata in toate cutiile: mult in cele doua cutii vecine, din ce in ce mai putin in cele indepartate. Semnalul are o singura frecventa, dar spectrul calculat arata de parca ar avea multe.

Analogie. Gandeste-te la o tava pentru cuburi de gheata, cu 32 de compartimente in sir. Torni apa dintr-o cana.

• Daca torni exact deasupra unui compartiment, toata apa ajunge in el. Celelalte raman goale. (= semnalul A)
• Daca torni deasupra peretelui dintre doua compartimente, apa se imparte intre cele doua si mai stropeste si in celelalte. (= semnalul B)

Apa e aceeasi. Doar locul unde ai turnat-o fata de compartimente e altul.

De ce e o problema (3 neplaceri):

1. Frecventa citita gresit. Din spectru vezi doar “undeva intre 800 si 900 Hz”, nu 850.
2. Amplitudinea citita gresit. Cea mai inalta linie are 10.25, nu 16. Daca ai calcula amplitudinea din ea, ai obtine $10.25 / 16 = 0.64$ in loc de 1.
3. Ascunde semnalele mici. Scurgerea unui semnal mare poate acoperi un semnal mic aflat la alta frecventa. Exemplul din curs e in sectiunea 6.4.

Sunt doua explicatii. Spun acelasi lucru, o data privit in timp si o data privit in frecventa. La examen se cere de obicei a doua (cea cu fereastra), dar prima se intelege mai usor.

Pasul 1 — ce “crede” DFT-ul despre semnal. Cutia $k$ corespunde unui cosinus care face exact $k$ perioade intregi in cele $N$ esantioane (cutia 1: o perioada, cutia 2: doua perioade, …). Un asemenea cosinus, dupa $N$ esantioane, o ia de la capat identic. Orice suma de asemenea cosinusuri face la fel. Deci DFT-ul poate descrie doar semnale care se repeta identic la fiecare $N$ esantioane. Cu alte cuvinte: DFT-ul se poarta ca si cum cele $N$ esantioane ale tale ar fi puse cap la cap, la nesfarsit.

Pasul 2 — ne uitam cum arata semnalul pus cap la cap. In desen am folosit un cosinus mai lent (2 si 2.5 perioade in loc de 8 si 8.5), ca sa se vada forma. Fenomenul e acelasi.

Ce vezi in desen: pe orizontala e numarul esantionului $n$, pe verticala valoarea $x(n)$. Bucata albastra din mijloc = cele 32 de esantioane pe care le avem. Bucatile gri = copiile pe care “le vede” DFT-ul in stanga si in dreapta. Liniile punctate = locurile de lipire.

• Sus (2 perioade intregi): bucata se termina exact unde incepe urmatoarea. Semnalul lipit e un cosinus perfect, fara sfarsit.
• Jos (2.5 perioade): bucata se termina la $-0.88$, iar copia urmatoare incepe la $+1$. La lipire apare un salt.

La exemplul nostru cu 8.5 perioade e la fel: ultimul esantion este $x(31) = 0.10$. Un cosinus adevarat ar continua cu $-1$. In schimb, copia incepe cu $x(0) = +1$. Salt.

Pasul 3 — de ce saltul strica spectrul. Un salt este o schimbare brusca. Ca sa construiesti o schimbare brusca din cosinusuri ai nevoie de foarte multe frecvente (la fel ca la unda patrata din Cap 2, care are armonici la nesfarsit din cauza muchiilor). De aceea DFT-ul pune cate ceva in toate cutiile.

Pasul 1 — de unde vin cele $N$ esantioane. Semnalul adevarat e lung (cosinusul nu se termina niciodata). Il notam $s^{\infty}(n)$. Noi pastram doar $N$ esantioane din el. “A pastra doar $N$ esantioane” este acelasi lucru cu a inmulti semnalul lung cu

$$ r(n) = \begin{cases} 1, & 0 \le n \le N-1 \quad \text{(esantioanele pastrate)} \\ 0, & \text{in rest} \end{cases} $$

Asta se numeste fereastra dreptunghiulara: te uiti la semnal ca printr-o fereastra si vezi doar o bucata din el.

$$ s(n) = s^{\infty}(n) \cdot r(n) $$

Pasul 2 — ce face inmultirea in frecventa. Teorema convolutiei (Cap 7) spune: inmultire in timp ⇔ convolutie in frecventa. Deci spectrul a ceea ce avem este

$$ S(k) = (S^{\infty} \ast R)(k) $$

adica spectrul semnalului adevarat, convolutionat cu spectrul ferestrei.

Pasul 3 — ce inseamna asta concret. Spectrul adevarat al cosinusului are doar 2 linii subtiri (la $+f$ si la $-f$). Convolutia cu o linie subtire face un singur lucru: pune o copie a celuilalt semnal in locul liniei (tot din Cap 7). Rezultatul:

fiecare linie din spectrul adevarat este inlocuita cu o copie a spectrului ferestrei, asezata pe frecventa liniei.

Ce vezi in desen: randul de sus e in timp (pe orizontala $n$, pe verticala valoarea esantionului): cosinus fara sfarsit × fereastra = cele $N$ esantioane ale noastre. Randul de jos e in frecventa (pe orizontala frecventa, pe verticala inaltimea spectrului): 2 linii ∗ spectrul ferestrei = doua “dealuri cu valuri” in locul celor 2 linii.

Deci forma pe care o vedem in jurul fiecarei frecvente este, de fapt, spectrul ferestrei. Ramane sa vedem cum arata el.

Luam o fereastra mica: 8 valori de 1.

$$ r = [1, 1, 1, 1, 1, 1, 1, 1] $$

DFT-ul ei cu $N = 8$:

$$ |R(k)| = [8, 0, 0, 0, 0, 0, 0, 0] $$

• $R(0) = 8$: cutia 0 este pur si simplu suma esantioanelor: $1 + 1 + \dots + 1 = 8$.
• $R(k) = 0$ pentru $k \ne 0$: acolo aduni 8 sageti de lungime 1 raspandite egal pe cerc; se anuleaza intre ele (Cap 6).

Pare ca spectrul ferestrei e o singura linie. Dar noi am citit doar valorile din cutii. Ce e intre cutii? Ca sa vedem, calculam DFT-ul in de doua ori mai multe puncte (punem dupa cei 8 de 1 inca 8 zerouri, deci $N = 16$; de ce merge asa: sectiunea 5):

Cutiile pare (0, 2, 4, …) sunt cutiile vechi: 8, apoi zerouri. Cutiile impare sunt punctele dintre ele, si acolo nu e zero. Intre cutii era ascunsa o curba: un deal mare, apoi dealuri din ce in ce mai mici, cu zerouri intre ele.

Aceeasi curba, scrisa cu litere. Notam cu $M$ numarul de valori de 1 din fereastra si cu $N$ numarul total de puncte ale DFT-ului. Atunci:

$$ R(k) = e^{-j\pi k \frac{M-1}{N}} \cdot \mathrm{dsinc}_M\left(\frac{\pi k}{N}\right), \qquad \mathrm{dsinc}_M\left(\frac{\pi k}{N}\right) = \frac{\sin\left(\frac{\pi k M}{N}\right)}{\sin\left(\frac{\pi k}{N}\right)} $$

• Primul factor ($e^{-j\dots}$) are modulul 1. El schimba doar faza, nu inaltimea. Pentru desenul $|R(k)|$ il ignoram.
• Al doilea factor se numeste dsinc (“sinc digital”). El da inaltimea: $|R(k)| = \left|\sin(\pi k M/N) / \sin(\pi k/N)\right|$.
• La $k = 0$ formula da $0/0$; valoarea corecta este $M$ (suma celor $M$ de 1).

Verificare cu numerele de mai sus ($M = 8$, $N = 16$):

• $k = 1$: $\sin(\pi \cdot 8/16) / \sin(\pi/16) = 1 / 0.195 = 5.13$ ✓
• $k = 2$: $\sin(\pi \cdot 16/16) = \sin(\pi) = 0$ → $0$ ✓
• $k = 3$: $\sin(3\pi/2) / \sin(3\pi/16) = -1 / 0.556 = -1.80$ → modulul 1.80 ✓

• Lobul principal = dealul mare din mijloc. Varful lui e exact pe frecventa reala a semnalului.
• Lobii laterali = dealurile mici de pe margini. Ei sunt “scurgerea”. Primul lob lateral are cam 22% din inaltimea varfului (3.5 din 16 in exemplul nostru). Urmatorii scad incet.
• Zerourile = punctele dintre lobi unde curba atinge 0. Sunt acolo unde $\sin(\pi k M/N) = 0$, adica unde $k M / N$ este numar intreg:

$$ k = l \cdot \frac{N}{M}, \qquad l = \pm 1, \pm 2, \dots $$

Cazul obisnuit: $M = N$ (fara zero-padding: toate cele $N$ puncte sunt esantioane reale). Atunci $N/M = 1$, deci zerourile sunt la $k = \pm 1, \pm 2, \pm 3, \dots$ fata de varf — adica la fiecare cutie. Lobul principal se intinde de la $-1$ la $+1$: e lat de 2 cutii.

Aici e cheia intregului capitol. Curba (spectrul ferestrei) este mereu acolo, in jurul frecventei semnalului. Dar DFT-ul nu vede curba intreaga. El citeste curba doar la $k$ intreg.

Ce vezi in desen: pe orizontala e cutia $k$, pe verticala $|X(k)|$. Portocaliu = curba (spectrul ferestrei, mutat pe frecventa reala; linia rosie punctata arata frecventa reala). Albastru = ce scoate DFT-ul: valoarea curbei doar in dreptul numerelor intregi.

• Sus (frecventa pe cutia 8): cutia 8 citeste varful (16). Cutiile 7, 9, 6, 10, … cad exact pe zerourile curbei. Citesc 0. Scurgerea exista, dar nu se vede.
• Jos (frecventa la 8.5): curba s-a mutat cu o jumatate de cutie. Acum cutiile cad pe lobi: cutiile 8 si 9 pe coastele lobului principal (10.3 si 10.2), cutiile 7 si 10 pe primii lobi laterali (3.5 si 3.4), si asa mai departe.

Verificare cu formula. Cutia 8 e la distanta de 0.5 cutii de frecventa reala (8.5). Cosinusul de amplitudine 1 inseamna doua linii de inaltime $1/2$ (Cap 0), deci curba din jurul lui 8.5 este $\frac{1}{2} \cdot$ dsinc. La distanta 0.5, cu $M = N = 32$:

$$ \frac{1}{2} \cdot \left| \frac{\sin(\pi \cdot 0.5)}{\sin(\pi \cdot 0.5 / 32)} \right| = \frac{1}{2} \cdot \frac{1}{0.0491} = 10.19 $$

DFT-ul a dat 10.25. (Diferenta mica vine de la copia din oglinda, cea din jurul lui 23.5, care ajunge cu coada ei pana aici.) La distanta 1.5 (cutia 7 sau 10): $\frac{1}{2} \cdot 1/\sin(\pi \cdot 1.5/32) = 3.41$ ✓.

Zero-padding = adaugi esantioane cu valoarea 0 la sfarsitul semnalului si faci DFT-ul pe semnalul lungit.

Semnal mic: un cosinus care face 2 perioade in 8 esantioane.

$$ x = [1, 0, -1, 0, 1, 0, -1, 0] \qquad (N = 8) $$

$$ |X(k)| = [0, 0, \mathbf{4}, 0, 0, 0, \mathbf{4}, 0] $$

Doua linii curate: la $k = 2$ si la oglinda $k = 6$, de inaltime $N \cdot A/2 = 8 \cdot 1/2 = 4$.

Acum adaugam 8 zerouri:

$$ x' = [1, 0, -1, 0, 1, 0, -1, 0, \; 0, 0, 0, 0, 0, 0, 0, 0] \qquad (N' = 16) $$

(Cutiile 9…15 sunt oglinda: 1.08, 0, 2.61, 4, 2.61, 0, 1.08.)

Patru lucruri de observat:

1. Varful s-a mutat de la $k = 2$ la $k = 4$. Frecventa e aceeasi! Inainte: $2 \cdot f_s/8 = f_s/4$. Acum: $4 \cdot f_s/16 = f_s/4$. S-a schimbat doar numerotarea, pentru ca acum cutiile sunt de doua ori mai dese ($f_s/16$ in loc de $f_s/8$).
2. Inaltimea varfului a ramas 4, nu a devenit 8. Zerourile adaugate nu aduna nimic la suma. Varful este $M \cdot A/2$, unde $M$ = numarul de esantioane reale (8), nu lungimea DFT-ului (16).
3. Cutiile pare (0, 2, 4, 6, 8) sunt exact cutiile vechi (0, 1, 2, 3, 4). Au aceleasi valori ca inainte: 0, 0, 4, 0, 0.
4. Cutiile impare sunt noi. Ele cad intre cutiile vechi, adica pe lobii curbei din sectiunea 4. De aceea nu sunt zero.

Revenim la $N = 32$, $f_s = 3200$ Hz, cosinus la 800 Hz (pe cutie).

Ce vezi in desen: pe orizontala frecventa in Hz (de la 0 la $f_s/2 = 1600$), pe verticala $|X(k)|$. Portocaliu = curba (aceeasi in toate cele trei desene). Albastru = punctele DFT-ului.

• Sus, fara zero-padding (32 de puncte): cutii din 100 in 100 Hz. Toate cad pe varf sau pe zerouri → o singura linie.
• Mijloc, zero-padding la 64: cutii din 50 in 50 Hz. Apar punctele dintre cutiile vechi: 10.2 langa varf, 3.4, 2.1, …
• Jos, zero-padding la 256: cutii din 12.5 in 12.5 Hz. Punctele sunt atat de dese ca se vede toata curba.

In limbajul din curs: semnalul are $M$ esantioane reale si $N'$ puncte in total. Zerourile dsinc-ului sunt la fiecare $N'/M$ cutii (sectiunea 4.3). Cu $N' = 2M$, doar una din doua cutii mai cade pe un zero. Celelalte arata curba.

La ce foloseste:

• vezi forma spectrului (lobul principal, lobii laterali), nu doar cateva puncte;
• gasesti mai precis unde e varful cand frecventa e intre doua cutii (punctele dese ajung mai aproape de varful lobului).

Exemplu cu numere. $f_s = 3200$ Hz. Semnalul are doua cosinusuri apropiate: 800 Hz si 850 Hz (la 50 Hz distanta).

Ce vezi in desen: pe orizontala frecventa in Hz, pe verticala $|X(k)|$ impartit la $N/2$ (ca un cosinus de amplitudine 1 pe cutie sa dea inaltimea 1). Liniile mov punctate = cele doua frecvente reale.

• Sus (32 de esantioane reale): lobul principal e lat de $2 \cdot 3200/32 = 200$ Hz. Cele doua frecvente sunt la doar 50 Hz una de alta → se vede un singur deal.
• Mijloc (aceleasi 32 de esantioane + zero-padding la 256): curba e desenata mai fin, dar e tot un singur deal. Nu poti spune ca sunt doua frecvente.
• Jos (256 de esantioane REALE): lobul principal e lat de $2 \cdot 3200/256 = 25$ Hz → doua linii separate, la 800 si la 850 Hz.

Problema, in cele doua feluri de a o privi (sectiunea 3):

• in timp: capetele bucatii nu se potrivesc → salt la lipire;
• in frecventa: fereastra dreptunghiulara are lobi laterali mari (primul: 22% din varf).

Solutia: nu mai folosim fereastra dreptunghiulara. Inmultim noi esantioanele cu alta fereastra, $w(n)$, care este 1 (sau aproape 1) la mijloc si coboara lin spre 0 la capete:

$$ s_w(n) = s(n) \cdot w(n) $$

Ce vezi in desen:

• Stanga: cele patru ferestre. Pe orizontala e numarul esantionului $n$, pe verticala numarul cu care inmultim esantionul respectiv. Dreptunghiulara e 1 peste tot. Hann, Hamming si Blackman sunt “cocoase”: 1 la mijloc, spre 0 la capete.
• Mijloc: un semnal cu 2.5 perioade. Incepe la $+1$, se termina la $-0.88$ → capetele nu se potrivesc.
• Dreapta: acelasi semnal inmultit cu fereastra Hann (linia portocalie punctata arata fereastra). Ambele capete au ajuns la 0 → la lipire nu mai e salt.

Exemplu cu numere: fereastra Hann cu 8 puncte.

$$ w = [0, \; 0.19, \; 0.61, \; 0.95, \; 0.95, \; 0.61, \; 0.19, \; 0] $$

Daca semnalul este $s = [2, 2, 2, 2, 2, 2, 2, 2]$, dupa fereastra devine $s_w = [0, \; 0.38, \; 1.22, \; 1.90, \; 1.90, \; 1.22, \; 0.38, \; 0]$: fiecare esantion inmultit cu numarul de pe aceeasi pozitie din $w$.

(Formula ferestrei Hann, daca te intreaba cineva: $w(n) = 0.5 - 0.5\cos\left(\frac{2\pi n}{N-1}\right)$. Nu se cere pe de rost. Trebuie sa stii numele ferestrelor, forma lor si ce fac.)

Ce vezi in desen: pe orizontala cutia $k$ (doar 0…16), pe verticala $|X(k)|$. Sus fara fereastra: toate cutiile au cel putin 1. Jos cu fereastra Hann: mai raman vizibile doar cutiile 7, 8, 9, 10; restul sunt aproape 0.

Ce ai castigat: departe de varf, scurgerea a scazut enorm. In cutia 0: de la 1.00 la 0.004, adica de 250 de ori mai putin. In cutia 12: de la 1.53 la 0.07.

Ce ai pierdut (nimic nu e gratis):

1. Varful e mai scund: 6.65 in loc de 10.25. Fereastra micsoreaza esantioanele de la capete, deci “ia” din semnal. (Cu Hann, un cosinus aflat exact pe cutie da cam 8 in loc de 16: jumatate.)
2. Varful e mai lat: lobul principal al ferestrei Hann are 4 cutii in loc de 2. Chiar si un cosinus aflat exact pe cutia 8 nu mai da o singura linie, ci trei: cam 4 la $k = 7$, 8 la $k = 8$, 4 la $k = 9$. Doua frecvente apropiate se deosebesc mai greu.

Ce vezi in desen: spectrul fiecarei ferestre. Pe orizontala: distanta fata de frecventa reala, in cutii. Pe verticala: inaltimea fata de varf, in decibeli (Cap 5): 0 dB = varful, $-20$ dB = de 10 ori mai mic, $-40$ dB = de 100 de ori mai mic, $-60$ dB = de 1000 de ori mai mic. Sageata neagra = latimea lobului principal. Linia rosie = cel mai inalt lob lateral.

Regula: cu cat cobori pe tabel, lobii laterali sunt mai mici (bine), dar lobul principal e mai lat (rau).

$f_s = 8000$ Hz, $N = 256$. Distanta dintre cutii: $8000/256 = 31.25$ Hz. Semnalul are doua cosinusuri: unul mare la $f_1$ si unul foarte mic (de 500 de ori mai mic) la $f_2 = 2000$ Hz.

Verificam cine e pe cutie, cu regula $k = f \cdot N / f_s$:

• $f_2 = 2000$: $2000 \cdot 256/8000 = 64$ → pe cutie
• $f_1 = 1000$: $1000 \cdot 256/8000 = 32$ → pe cutie
• $f_1 = 1150$: $1150 \cdot 256/8000 = 36.8$ → intre cutii → leakage

Ce vezi in desen: pe orizontala frecventa in Hz (0…4000), pe verticala $|X(k)|$ fata de varf, in dB (ca sa se vada si lucrurile foarte mici). Linia mov punctata = 2000 Hz, unde e semnalul mic.

• Sus ($f_1 = 1000$ Hz, pe cutie): doua linii curate. Cea mica se vede fara probleme, pentru ca in jurul ei nu e nimic.
• Mijloc ($f_1 = 1150$ Hz, intre cutii, fara fereastra): scurgerea semnalului mare umple tot spectrul la un nivel cam cat semnalul mic. Linia de la 2000 Hz nu se mai deosebeste de vecinele ei.
• Jos ($f_1 = 1150$ Hz, cu fereastra Hann): scurgerea scade repede pe masura ce te departezi de 1150 Hz. La 2000 Hz a ajuns mult sub semnalul mic → acesta se vede din nou.

Asta e situatia obisnuita in practica: semnalul care te intereseaza e mai mic decat ce e in jurul lui. In curs, pentru acest exemplu, fereastra Hanning da cel mai bun rezultat dintre cele trei.

Acum semnalul nostru este $s^{\infty}(n) \cdot w(n)$ in loc de $s^{\infty}(n) \cdot r(n)$. Teorema convolutiei da $S^{\infty} \ast W$ in loc de $S^{\infty} \ast R$. Deci fiecare linie e inlocuita cu o copie a spectrului noii ferestre, $W(k)$, care are lobi laterali mult mai mici decat dsinc-ul. Atat.

Ferestrele mai apar o data, cu alt rol: la proiectarea filtrelor FIR → Cap 9.

Enunt. Fie semnalul

$$ s(n) = \cos\left(2\pi \frac{1}{8} n\right) + \cos\left(2\pi \frac{1}{4} n\right) + \cos\left(2\pi \frac{3}{8} n\right) $$

adica o suma de trei cosinusuri de amplitudine 1, la frecventele $f_s/8$, $f_s/4$ si $3f_s/8$.

• a) Desenati spectrul $|S(k)|$ obtinut cu o DFT de $N = 64$ puncte.
• b) Adaugam zerouri pana la 128 de esantioane (zero-padding) si refacem DFT-ul. Ce se schimba?

Ce se cere: in ce cutii apar linii si ce inaltime au.

Ce stim: $N = 64$; trei cosinusuri de amplitudine $A = 1$ la $f_s/8$, $f_s/4$, $3f_s/8$.

Pas 1 — in ce cutie cade fiecare frecventa. Regula: $k = f \cdot N / f_s$.

• $f_s/8$: $k = \frac{f_s}{8} \cdot \frac{64}{f_s} = \frac{64}{8} = 8$
• $f_s/4$: $k = \frac{64}{4} = 16$
• $3f_s/8$: $k = \frac{3 \cdot 64}{8} = 24$

Pas 2 — apare leakage? Toate trei numerele (8, 16, 24) sunt intregi → toate frecventele cad exact pe cutii → nu se vede leakage. (Altfel spus: in cele 64 de esantioane incap exact 8, 16 si 24 de perioade.)

Pas 3 — inaltimea liniilor. Cosinus de amplitudine $A$ pe cutie → $N \cdot A / 2 = 64 \cdot 1/2 = 32$.

Pas 4 — oglinda. Fiecare linie de la $k$ are perechea la $N - k$: $64 - 8 = 56$, $64 - 16 = 48$, $64 - 24 = 40$.

Raspuns a): 6 linii de inaltime 32, la $k = 8, 16, 24$ si la $k = 40, 48, 56$. Toate celelalte cutii sunt 0. (Desenul de sus, mai jos.)

Ce se cere: cum arata spectrul cand DFT-ul are 128 de puncte, din care doar primele 64 sunt esantioane reale.

Ce stim: $M = 64$ esantioane reale, $N' = 128$ puncte in total.

Pas 1 — unde ajung varfurile. Cutiile sunt acum de doua ori mai dese ($f_s/128$). Aceeasi regula, cu $N' = 128$:

• $f_s/8$: $k' = 128/8 = 16$
• $f_s/4$: $k' = 128/4 = 32$
• $3f_s/8$: $k' = 3 \cdot 128/8 = 48$
• oglinzile: $128 - 16 = 112$, $128 - 32 = 96$, $128 - 48 = 80$

Numerele cutiilor s-au dublat. Frecventele sunt aceleasi.

Pas 2 — inaltimea varfurilor. Ramane 32, nu devine 64. Varful este $M \cdot A/2$ cu $M$ = numarul de esantioane reale: $64 \cdot 1/2 = 32$. Zerourile nu aduna nimic.

Pas 3 — cutiile pare. Cutiile pare ($k' = 0, 2, 4, \dots$) sunt exact cutiile vechi ($k = 0, 1, 2, \dots$). Au aceleasi valori ca la punctul a): 32 in varfuri, 0 in rest.

Pas 4 — cutiile impare (ce e nou). Cutiile impare cad intre cutiile vechi. Acolo dsinc-ul nu e zero, deci apar valori nenule:

• langa fiecare varf (la o jumatate de cutie veche): cam $0.64 \cdot 32 \approx 20$. Valorile exacte: 21.4 la $k' = 15$, 19.4 la $k' = 17$, 20.4 la $k' = 31$ si $33$, 19.4 la $k' = 47$, 21.4 la $k' = 49$.
• mai departe de varfuri: intre 3 si 8.

Raspuns b):

• varfurile se muta la $k' = 16, 32, 48$ (si oglinzile $80, 96, 112$) — aceleasi frecvente, numerotate cu cutii de doua ori mai dese;
• inaltimea lor ramane 32;
• intre varfuri, in cutiile impare, apar valori nenule: se vede forma dsinc (lobii) din jurul fiecarei linii;
• nu s-a castigat informatie si nu s-a imbunatatit separarea frecventelor: avem tot 64 de esantioane reale. Spectrul e doar citit in de doua ori mai multe puncte.

Ce vezi in desen: pe orizontala cutia $k$, pe verticala $|S(k)|$. Sus (punctul a): 6 linii curate de inaltime 32. Jos (punctul b): varfurile sunt la cutii cu numar dublu, tot de inaltime 32; cutiile pare dintre ele sunt 0; cutiile impare arata lobii.

Enunt. Pentru fiecare caz, spune daca in spectrul DFT se vede leakage. Semnalul e un singur cosinus de frecventa $f$.

Ce se cere: da / nu, cu justificare.

Ce stim (regula din sectiunea 3.1): calculezi $k = f \cdot N / f_s$. Daca iese intreg → frecventa e pe cutie → nu se vede leakage. Daca nu → leakage.

Pasi (acelasi calcul de 5 ori):

• a) $1000 \cdot 256 / 8000 = 32$ → intreg → fara leakage. Linia e in cutia 32.
• b) $1150 \cdot 256 / 8000 = 36.8$ → nu e intreg → leakage. Cele mai inalte cutii: 36 si 37 (37 e mai inalta, fiind mai aproape de 36.8).
• c) $50 \cdot 100 / 1000 = 5$ → intreg → fara leakage.
• d) $50 \cdot 128 / 1000 = 6.4$ → nu e intreg → leakage. Cele mai inalte cutii: 6 si 7 (6 e mai inalta).
• e) $440 \cdot 1024 / 44100 = 10.22$ → nu e intreg → leakage.

Raspuns: a) nu, b) da, c) nu, d) da, e) da.

Enunt. Un cosinus de amplitudine 1 a fost esantionat cu $f_s = 3200$ Hz. S-au luat $N = 32$ esantioane. Spectrul DFT (jumatatea pozitiva) e cel din desen. Aproximativ la ce frecventa este cosinusul?

Ce se cere: frecventa cosinusului, aproximativ.

Ce stim: cutiile sunt din $3200/32 = 100$ in 100 Hz. Pe axa orizontala sunt trecute direct frecventele cutiilor.

Pas 1 — e pe cutie sau intre cutii? Daca ar fi pe cutie, am vedea o singura linie de inaltime $N/2 = 16$ si zero in rest. Aici toate cutiile au ceva, iar cea mai inalta are doar 14.2 → e intre cutii (leakage).

Pas 2 — intre care cutii? Cea mai inalta linie: 1200 Hz (14.2). Ne uitam la cele doua vecine ale ei: 1100 Hz (3.7) si 1300 Hz (5.3). Vecina mai inalta e cea de la 1300 Hz → frecventa reala e intre 1200 si 1300 Hz.

Pas 3 — mai aproape de care? Linia de la 1200 (14.2) e mult mai inalta decat cea de la 1300 (5.3) → frecventa reala e mult mai aproape de 1200.

Raspuns: intre 1200 si 1300 Hz, aproape de 1200 — cam 1230 Hz. (Semnalul din desen chiar a fost generat la 1230 Hz, adica “cutia 12.3”.)

• Leakage = o frecventa care nu cade exact pe o cutie DFT apare imprastiata in toate cutiile (mult in vecine, putin departe).
• Cand apare: cand $f \cdot N / f_s$ nu e intreg (in cele $N$ esantioane nu incape un numar intreg de perioade).
• De ce apare: cele $N$ esantioane = semnal infinit × fereastra dreptunghiulara. Inmultire in timp ⇔ convolutie in frecventa → fiecare linie devine o copie a spectrului ferestrei = dsinc (lob principal + lobi laterali).
• $\mathrm{dsinc}_M(\pi k/N) = \sin(\pi k M/N) / \sin(\pi k/N)$; zerouri la $k = l \cdot N/M$; cu $M = N$: zero la fiecare cutie, lob principal lat de 2 cutii, primul lob lateral ≈ 22% din varf ($-13$ dB).
• Pe cutie nu se vede leakage pentru ca celelalte cutii cad exact pe zerourile dsinc-ului. Scurgerea exista mereu; doar nu se vede.
• Zero-padding = adaugi zerouri → cutii mai dese → vezi mai multe puncte din aceeasi curba. Varful ramane $M \cdot A/2$ ($M$ = esantioane reale); pozitia lui devine $k' = f \cdot N'/f_s$. Nu adauga informatie, nu reduce leakage, nu separa frecvente apropiate.
• Ferestre (Hann/Hanning, Hamming, Blackman): $s(n) \cdot w(n)$, cu $w$ lin spre 0 la capete → lobi laterali mici; pret: lob principal mai lat, varf mai scund.
• Cum atenuam leakage: (1) fereastra, (2) mai multe esantioane reale, (3) $N$ ales ca sa incapa un numar intreg de perioade.

G1. DFT leakage apare atunci cand:

1. A. frecventa de esantionare e prea mica (sub Nyquist)
2. B. frecventa semnalului nu este un multiplu intreg de $f_s/N$
3. C. semnalul are prea multe esantioane
4. D. convertorul are prea putini biti

G2. Avem $N = 100$ esantioane, $f_s = 1000$ Hz. Care cosinus nu produce leakage?

1. A. 55 Hz
2. B. 125 Hz
3. C. 130 Hz
4. D. 99 Hz

G3. Avem 64 de esantioane si adaugam zerouri pana la 256. Ce obtinem?

1. A. leakage mai mic
2. B. mai multe puncte din acelasi spectru, fara informatie noua
3. C. putem deosebi doua frecvente de 4 ori mai apropiate
4. D. o frecventa de esantionare de 4 ori mai mare

G4. Fata de fereastra dreptunghiulara, fereastra Hann are:

1. A. lob principal mai ingust si lobi laterali mai mari
2. B. lob principal mai lat si lobi laterali mai mici
3. C. lob principal mai ingust si lobi laterali mai mici
4. D. acelasi spectru

G5. Un cosinus de amplitudine 1, aflat exact pe o cutie, da cu $N = 32$ o linie de inaltime 16. Adaugam 32 de zerouri (DFT de 64 de puncte). Inaltimea varfului devine:

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

G6. Explicatia din curs pentru leakage este:

1. A. replicile spectrului se suprapun (aliasing)
2. B. eroarea de rotunjire de la cuantizare
3. C. cele $N$ esantioane sunt un semnal infinit inmultit cu o fereastra dreptunghiulara, deci spectrul e convolutionat cu un dsinc
4. D. filtrul anti-aliasing nu e ideal

G7. Vrei sa deosebesti doua cosinusuri aflate la 10 Hz unul de altul. Ai $f_s = 1000$ Hz si 50 de esantioane. Ce te ajuta?

1. A. zero-padding pana la 1000 de puncte
2. B. sa iei mai multe esantioane reale (de exemplu 500)
3. C. fereastra Blackman pe cele 50 de esantioane
4. D. nimic, e imposibil

G8. De ce nu se vede leakage cand frecventa cade exact pe o cutie?

1. A. pentru ca fereastra dreptunghiulara dispare in acest caz
2. B. pentru ca celelalte cutii cad exact pe zerourile dsinc-ului
3. C. pentru ca DFT-ul face singur zero-padding
4. D. pentru ca semnalul nu mai e periodic

Raspunsuri:

T1 (examen 2023). Despre DFT Leakage: ce este, de ce apare, cum il atenuam?

T2. Ce este zero-padding? La ce foloseste si ce nu poate face?

T3. Ce este o fereastra? Dati exemple. Ce se castiga si ce se pierde?

T4. Fereastra dreptunghiulara exista intotdeauna. De ce exista totusi cazuri in care nu vedem leakage?

Capitolul anterior: Cap 7 — Convolutia si teorema convolutiei · Urmatorul capitol: Cap 9 — Filtre FIR (acolo ferestrele se folosesc la proiectarea filtrelor).