Esercizio - quantizzatore con densità a gradini, codice di Shannon e segnalazione quaternaria (esame dell'8 febbraio 2024, es. 176)

---

Teoria usata: Quantizzazione uniforme - saturazione, errore granulare e SNR di quantizzazioneUn quantizzatore uniforme a L = 2^b livelli e range [−v_sat, v_sat] ha passo Δ = 2v_sat/L. L'errore e = x − x^(q) è di saturazione fuori range (illimitato, da rendere raro con P_sat piccola) e granulare dentro (|e| ≤ Δ/2, uniforme con potenza Δ²/12). L'SNR di quantizzazione Λ_q = E[x²]/E[e²] vale in decibel 20log₁₀(σ_x/v_sat) + 4,77 + 6,02·b: ogni bit in più dà 6 dB. Per b minimo che garantisce una specifica: ⌈(specifica − c)/6,02⌉ con c = 20log₁₀(σ_x/v_sat) + 4,77.Quantizzazione uniforme - saturazione, errore granulare e SNR di quantizzazione →, Codici di Shannon, Huffman ed Elias e codifica aritmeticaIl codice di Shannon(-Fano) assegna alla parola $i$ lunghezza $l_i=\lceil-\log_{M_y}p_i\rceil$, soddisfa Kraft-McMillan e ha $H\le L_y<H+1$; è ottimo solo se le probabilità sono potenze di $\frac1{M_y}$. Il codice ottimo (lunghezza media minima) dà parole più lunghe ai simboli meno probabili e ha almeno due parole di lunghezza massima che differiscono solo nell'ultimo simbolo: lo costruisce la procedura di Huffman, che unisce a ogni passo i due nodi meno probabili. Il codice di Elias prende le prime $l_i=\lceil-\log_2p_i\rceil+1$ cifre del punto medio dell'intervallo di ampiezza $p_i$ in $[0,1)$: è a prefisso ma subottimo ($H+1\le L_y<H+2$), e si adatta alla codifica aritmetica adattativa.Codici di Shannon, Huffman ed Elias e codifica aritmetica →, Spazio dei segnali - base ortonormale, coordinate e Gram-SchmidtI segnali a energia finita formano uno spazio vettoriale con prodotto interno $\langle x,y\rangle=\int x(t)y(t),dt$, norma $\lVert x\rVert=\sqrt{E_x}$ e distanza $d(x,y)=\lVert x-y\rVert$. Le $M$ forme d'onda di una segnalazione generano un sottospazio, di cui si costruisce una base ortonormale ${\phi_1,\dots,\phi_I}$ con $I\le M$ (procedura di Gram-Schmidt). Ogni segnale diventa il vettore delle coordinate $s_i=\langle s,\phi_i\rangle$: somme, prodotti per scalari, energie ($E_s=\sum s_i^2$) e distanze si calcolano uguali sui vettori. L'insieme dei vettori ${\mathbf s_1,\dots,\mathbf s_M}$ è la costellazione.Spazio dei segnali - base ortonormale, coordinate e Gram-Schmidt →, Probabilità d'errore delle modulazioni binarie - funzione Q e coefficiente di correlazioneIn una modulazione binaria con rumore AWGN e decisione a minima distanza l'errore avviene solo se la componente di rumore lungo la congiungente dei due punti supera metà distanza: $P[E]=Q\left(\frac{d}{2\sigma_I}\right)$ con $d=\lVert\underline s_1-\underline s_2\rVert$. A parità di energia $E_s$ si ha $d^2=2E_s(1-\rho)$, quindi $P[E]=Q\left(\sqrt{\frac{E_s}{\sigma_I^2}}\sqrt{\frac{1-\rho}{2}}\right)$, con $\rho=\frac{\langle s_1,s_2\rangle}{\sqrt{E_{s_1}E_{s_2}}}$ coefficiente di correlazione. Antipodali ($\rho=-1$, BPSK): $Q\left(\sqrt{E_s/\sigma_I^2}\right)$; ortogonali ($\rho=0$): $Q\left(\sqrt{E_s/(2\sigma_I^2)}\right)$, 3 dB peggio; $\rho=1$: $P[E]=\frac12$. Per qualunque modulazione binaria basta un solo ramo del ricevitore, lungo $\phi_1'\propto s_1-s_2$.Probabilità d'errore delle modulazioni binarie - funzione Q e coefficiente di correlazione →, Modulazione QAM - costellazioni, energia e probabilità d'erroreLa QAM trasmette due PAM indipendenti su due portanti in quadratura: $s_m(t)=\alpha_{m,I}h_{Tx}(t)\cos(2\pi f_0t)-\alpha_{m,Q}h_{Tx}(t)\sin(2\pi f_0t)$ con $\alpha\in{\pm1,\pm3,\dots}$ e $M=2^{2b}$ ($2b$ bit per simbolo). La base è $\phi_{1,2}\propto h_{Tx}\cos,,-h_{Tx}\sin$ con energia $\frac{E_h}2$, i punti stanno su una griglia $\sqrt M\times\sqrt M$ con $d_{\min}=\sqrt{2E_h}$ ed $E_s=\frac{M-1}{3}E_h$. Con $q=Q\left(\sqrt{\frac{E_h}{2\sigma_I^2}}\right)$: $P[E]=4\left(1-\frac1{\sqrt M}\right)q-4\left(1-\frac1{\sqrt M}\right)^2q^2$, con $\frac{E_h}{2\sigma_I^2}=\frac{E_s}{\sigma_I^2}\frac{3}{2(M-1)}$. Con Gray su ogni asse $P_{bit}\simeq\frac{P[E]}{\log_2M}$.Modulazione QAM - costellazioni, energia e probabilità d'errore →.

Normalizzazione. L'area è $2\,(4K+3K+2K+K)\cdot1=20K=1$, quindi $K=\frac1{20}=0{,}05$ (ogni gradino ha larghezza $1$). I valori dei gradini sono $0{,}2;\ 0{,}15;\ 0{,}1;\ 0{,}05$.

(Il grafico è la somma di quattro rettangoli di altezza $K$ e larghezze $8,6,4,2$.)

(1) $v_{sat}$, varianza dell'errore e bit rate

Saturazione nulla. La densità si annulla fuori da $[-4,4]$, quindi il minimo valore che dà $P_{sat}=0$ è $v_{sat}=4$. Con $L=8$ livelli il passo è $$\Delta=\frac{2v_{sat}}{L}=\frac{8}8=1,$$ e gli intervalli di quantizzazione $[-4,-3],\dots,[3,4]$ coincidono con i gradini della densità. (Il valore massimo dell'SNR si ottiene con $v_{sat}$ minimo, perché $\Delta$ è il più piccolo possibile.)

Varianza dell'errore senza approssimazioni. In ogni intervallo la densità è esattamente costante, quindi, condizionato all'intervallo, $x$ è uniforme e l'errore $e=x-x^{(q)}$ è uniforme in $\big[-\frac\Delta2,\frac\Delta2\big]$ senza alcuna approssimazione (di solito il passo piccolo è un'ipotesi, qui il risultato è esatto): $$E[e^2]=\frac{\Delta^2}{12}=\frac1{12}=0{,}0833\ \text{V}^2.$$

Bit rate. $8=2^3$ livelli, parola di $3$ bit in modulo e segno (un bit di segno e due di modulo). Con $1$ milione di campioni al secondo $$R_b=3\cdot10^6=3\ \text{Mbit/s.}$$

(Come bonus: la potenza del segnale è $\sigma_a^2=2K\,\big[4\cdot\frac13+3\cdot\frac73+2\cdot\frac{19}3+\frac{37}3\big]=\frac{10}3$, quindi $\Lambda_q=\frac{10/3}{1/12}=40$, cioè $16{,}0$ dB; la formula $20\log_{10}\frac{\sigma_a}{v_{sat}}+4{,}77+6{,}02\cdot3=-6{,}81+4{,}77+18{,}06=16{,}02$ dB dà lo stesso valore, perché qui $\frac{\Delta^2}{12}$ è esatto.)

(2) Codice di Shannon sui simboli quantizzati

Le probabilità degli $8$ livelli sono le aree dei gradini (larghezza $1$): $4K=0{,}2$ (per i due intervalli centrali $[0,1]$ e $[-1,0]$), $3K=0{,}15$, $2K=0{,}1$ e $K=0{,}05$ (due intervalli ciascuno): $$P=\big(0{,}05;\ 0{,}1;\ 0{,}15;\ 0{,}2;\ 0{,}2;\ 0{,}15;\ 0{,}1;\ 0{,}05\big).$$ Somma $2\cdot0{,}5=1$. Il codice di Shannon dà al simbolo di probabilità $p$ la lunghezza $\lceil-\log_2p\rceil$ (Codici di Shannon, Huffman ed Elias e codifica aritmeticaIl codice di Shannon(-Fano) assegna alla parola $i$ lunghezza $l_i=\lceil-\log_{M_y}p_i\rceil$, soddisfa Kraft-McMillan e ha $H\le L_y<H+1$; è ottimo solo se le probabilità sono potenze di $\frac1{M_y}$. Il codice ottimo (lunghezza media minima) dà parole più lunghe ai simboli meno probabili e ha almeno due parole di lunghezza massima che differiscono solo nell'ultimo simbolo: lo costruisce la procedura di Huffman, che unisce a ogni passo i due nodi meno probabili. Il codice di Elias prende le prime $l_i=\lceil-\log_2p_i\rceil+1$ cifre del punto medio dell'intervallo di ampiezza $p_i$ in $[0,1)$: è a prefisso ma subottimo ($H+1\le L_y<H+2$), e si adatta alla codifica aritmetica adattativa.Codici di Shannon, Huffman ed Elias e codifica aritmetica →):

$$\bar L=2\,\big(0{,}2\cdot3+0{,}15\cdot3+0{,}1\cdot4+0{,}05\cdot5\big)=2\,(0{,}6+0{,}45+0{,}4+0{,}25)=3{,}4\ \text{bit.}$$ (La soluzione del corso scrive $\frac1{20}\lceil\log_220\rceil+\dots$, cioè gli stessi termini.) Entropia $H=2{,}846$ bit: $H\le\bar L<H+1$ è verificata ($2{,}846\le3{,}4<3{,}846$) ma il codice di Shannon, con $3{,}4$ bit, è peggiore della codifica a lunghezza fissa ($3$ bit): le probabilità sono vicine all'uniforme e l'arrotondamento per eccesso delle lunghezze costa troppo.

(3) Spazio delle forme d'onda e distanza minima

Si controllano le relazioni tra i quattro segnali, con $f_0=500$ MHz molto maggiore di $\frac1T$ ($T$ è il periodo di simbolo, dell'ordine del microsecondo, quindi $f_0T\gg1$ e i prodotti $\int h^2(t)\cos(2\pi f_0t)\,dt$ sono trascurabili, dell'ordine di $\frac1{\pi f_0T}\sim10^{-3}$ rispetto all'energia):

• $s_3=-s_1$: linearmente dipendente da $s_1$ (stessa direzione, verso opposto);
• $s_1=h\cos(2\pi f_0t)$ e $s_2=h\sin(2\pi f_0t)$ sono ortogonali: $\int h^2\cos\sin\,dt=\frac12\int h^2\sin(4\pi f_0t)dt\simeq0$;
• $s_0=h$ è ortogonale a $s_1$ e $s_2$: $\int h^2\cos(2\pi f_0t)\,dt\simeq0$ e $\int h^2\sin(2\pi f_0t)\,dt\simeq0$ (oscillazioni veloci).

Le energie: $E_0=E_h$; $E_1=E_2=E_3=\int h^2\cos^2=\frac{E_h}2$ (il coseno al quadrato ha valor medio $\frac12$). Poiché $s_0,s_1,s_2$ sono ortogonali tra loro e $s_3$ dipende da $s_1$, lo spazio ha dimensione $3$, con base ortonormale $$\varphi_0=\frac{s_0}{\sqrt{E_h}},\qquad\varphi_1=\frac{s_1}{\sqrt{E_h/2}},\qquad\varphi_2=\frac{s_2}{\sqrt{E_h/2}}$$ e costellazione $$s_0=\big(\sqrt{E_h},0,0\big),\quad s_1=\Big(0,\sqrt{\tfrac{E_h}2},0\Big),\quad s_2=\Big(0,0,\sqrt{\tfrac{E_h}2}\Big),\quad s_3=\Big(0,-\sqrt{\tfrac{E_h}2},0\Big).$$ Distanze (radice della somma dei quadrati delle differenze):

Il minimo è $d_{min}=\sqrt{E_h}=\sqrt{10^{-14}}=10^{-7}\ \text{V}\sqrt{\text{s}}$ (coppie $s_1,s_2$ e $s_2,s_3$).

(4) Probabilità d'errore sul bit con $-s_2$ al posto di $s_0$

I quattro segnali sono ora $s_1,\ s_2,\ s_3=-s_1,\ -s_2$: sono tutti in un piano (base $\varphi_1,\varphi_2$), con punti sui quattro semiassi a distanza $\sqrt{E_h/2}$ dall'origine: una costellazione $4$-PSK (o $4$-QAM ruotata di $45^\circ$) con energia per simbolo $E_s=\frac{E_h}2$ e distanza tra punti adiacenti $d_{min}=\sqrt{2\cdot\frac{E_h}2}=\sqrt{E_h}$. Con la mappatura di Gray la probabilità d'errore sul bit è $$P_{bit}=Q\Big(\frac{d_{min}}{2\sigma_I}\Big)=Q\Big(\sqrt{\frac{E_h}{4\sigma_I^2}}\Big)$$ (Modulazione QAM - costellazioni, energia e probabilità d'erroreLa QAM trasmette due PAM indipendenti su due portanti in quadratura: $s_m(t)=\alpha_{m,I}h_{Tx}(t)\cos(2\pi f_0t)-\alpha_{m,Q}h_{Tx}(t)\sin(2\pi f_0t)$ con $\alpha\in{\pm1,\pm3,\dots}$ e $M=2^{2b}$ ($2b$ bit per simbolo). La base è $\phi_{1,2}\propto h_{Tx}\cos,,-h_{Tx}\sin$ con energia $\frac{E_h}2$, i punti stanno su una griglia $\sqrt M\times\sqrt M$ con $d_{\min}=\sqrt{2E_h}$ ed $E_s=\frac{M-1}{3}E_h$. Con $q=Q\left(\sqrt{\frac{E_h}{2\sigma_I^2}}\right)$: $P[E]=4\left(1-\frac1{\sqrt M}\right)q-4\left(1-\frac1{\sqrt M}\right)^2q^2$, con $\frac{E_h}{2\sigma_I^2}=\frac{E_s}{\sigma_I^2}\frac{3}{2(M-1)}$. Con Gray su ogni asse $P_{bit}\simeq\frac{P[E]}{\log_2M}$.Modulazione QAM - costellazioni, energia e probabilità d'errore →). La varianza del rumore è $12$ dB sotto l'energia: $\sigma_I^2=E_h\cdot10^{-1{,}2}=\frac{E_h}{15{,}85}$, quindi $$\frac{E_h}{4\sigma_I^2}=\frac{15{,}85}4=3{,}96,\qquad\sqrt{3{,}96}=1{,}99,\qquad P_{bit}=Q(1{,}99)=0{,}0233.$$ La soluzione del corso riporta $Q(2)=0{,}023$, arrotondando $1{,}99$ a $2$ ($Q(2)=0{,}0228$ contro $Q(1{,}99)=0{,}0233$).

(Tutti i risultati ricalcolati con Python: $K=0{,}05$, $E[e^2]=0{,}08333$, $\bar L=3{,}4$, $H=2{,}8464$, $\sigma_a^2=3{,}333$, $d_{min}=10^{-7}$, $Q(1{,}9905)=0{,}02327$.)

Errori comuni

• Prendere $v_{sat}$ maggiore di $4$: oltre il supporto non serve e aumenta $\Delta$.
• Calcolare la varianza dell'errore con la formula "approssimata" cercando un integrale: con densità costante a tratti sugli intervalli $\frac{\Delta^2}{12}$ è già esatta.
• Dimenticare che $\cos^2$ ha valor medio $\frac12$: i segnali $s_1,s_2,s_3$ hanno energia $\frac{E_h}2$, non $E_h$.
• Dire che la dimensione dello spazio è $4$ (quattro segnali): $s_3$ è dipendente da $s_1$, la dimensione è $3$.
• Nel punto 4, usare l'energia $E_h$ (di $s_0$) come energia per simbolo: con $-s_2$ al posto di $s_0$ tutti i simboli hanno energia $\frac{E_h}2$.