Esercizio - quantizzatore a due livelli, canale a quattro uscite e codice di Huffman delle coppie (esame del 30 agosto 2024, es. 182)

---

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 →, Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimoL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit (zero per l'evento certo, additiva per eventi indipendenti). L'entropia di una variabile aleatoria discreta è l'informazione media, $H(x)=E[i_x(x)]=\sum_aP_x(a)\log_2\frac1{P_x(a)}$; vale $0\le H(x)\le\log_2M$ con $M$ cardinalità dell'alfabeto, e il massimo $\log_2M$ si raggiunge se e solo se i simboli sono equiprobabili (dimostrazione con la disuguaglianza di Jensen, perché il logaritmo è strettamente concavo).Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimo →, Entropia congiunta e condizionata e informazione mutuaPer due variabili aleatorie discrete $x,y$ l'entropia congiunta è $H(x,y)=E\left[\log_2\frac1{P_{x,y}(x,y)}\right]$ e vale $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, con l'uguaglianza a destra se e solo se $x$ e $y$ sono indipendenti e $H(x,y)=H(x)$ se $y=f(x)$. L'entropia condizionata $H(x|y)=E_y[H(x|y=y)]$ soddisfa la regola della catena $H(x,y)=H(x|y)+H(y)=H(y|x)+H(x)$. L'informazione mutua $I(x;y)=H(x)+H(y)-H(x,y)=H(x)-H(x|y)=H(y)-H(y|x)$ è simmetrica, $0\le I\le\min{H(x),H(y)}$, nulla per variabili indipendenti.Entropia congiunta e condizionata e informazione mutua →, 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 →, Probabilità per le telecomunicazioni - eventi e variabili aleatorie discreteGli eventi hanno probabilità tra 0 e 1 e P(x∪y) = P(x) + P(y) − P(x∩y). Una variabile aleatoria discreta ha un alfabeto A_x e una densità p_x(a) = P(x = a) con somma 1. Si definiscono probabilità condizionata, indipendenza (p_{x,y}(a,b) = p_x(a)p_y(b)), valore atteso E(x) = m_x, potenza M_x = E(x²), varianza σ_x² con M_x = m_x² + σ_x²; l'aspettazione è lineare e per variabili indipendenti E(xy) = E(x)E(y).Probabilità per le telecomunicazioni - eventi e variabili aleatorie discrete →.

Notazione. Nella matrice $\mathbf Q$ l'indice $i$ della riga è il valore quantizzato di $x$ (il canale ha come ingresso l'uscita del quantizzatore, che ha due livelli): la riga $1$ corrisponde al livello più basso $-2{,}9$ e la riga $2$ al livello più alto $+2{,}9$ (livelli in ordine crescente; è l'ordine usato dalla soluzione del corso). Ogni riga è una densità su $y$ e somma a $1$ ($0{,}1+0{,}2+0{,}3+0{,}4$ e $4\cdot0{,}25$).

(1) Probabilità di saturazione e entropia dei valori quantizzati

Probabilità di saturazione. $P_{sat}=P(x\notin[-5{,}8,\,5{,}8])$. La densità è $\frac1{10}$ su $[-6,4]$ e $0$ altrove. A destra il segnale non supera $4<5{,}8$, quindi non c'è saturazione. A sinistra va in saturazione l'intervallo $[-6,-5{,}8]$, di larghezza $0{,}2$: $$P_{sat}=\int_{-6}^{-5{,}8}\frac1{10}\,da=\frac{0{,}2}{10}=0{,}02.$$

Entropia dei valori quantizzati. Con $L=2$ livelli $\Delta=\frac{2v_{sat}}{L}=5{,}8$, l'unica soglia è in $0$ e i livelli sono $\pm\frac\Delta2=\pm2{,}9$. Un campione va al livello $-2{,}9$ se $x<0$ (compresa la saturazione) e a $+2{,}9$ se $x>0$: $$P(x_q=-2{,}9)=P(x<0)=\frac{6}{10}=0{,}6,\qquad P(x_q=+2{,}9)=P(x>0)=\frac4{10}=0{,}4.$$ L'entropia, in bit, è $$H(x_q)=-0{,}6\log_20{,}6-0{,}4\log_20{,}4=0{,}6\cdot0{,}737+0{,}4\cdot1{,}322=0{,}442+0{,}529=0{,}971\ \text{bit.}$$

(2) Entropia di $y$

Per le probabilità totali sull'ingresso $i$ del canale, con $P(i=1)=0{,}6$ e $P(i=2)=0{,}4$: $$P(y=j)=0{,}6\,Q_{1,j}+0{,}4\,Q_{2,j}.$$

La somma è $1$. L'entropia è $$H(y)=-\sum_jP(y=j)\log_2P(y=j)=0{,}16\cdot2{,}644+0{,}22\cdot2{,}184+0{,}28\cdot1{,}837+0{,}34\cdot1{,}556=0{,}423+0{,}480+0{,}514+0{,}529=1{,}947\ \text{bit.}$$

(3) Codice ottimo (Huffman) per le coppie $(x_q,y)$

Le coppie $(i,j)$ hanno probabilità $P(i,j)=P(i)\,Q_{i,j}$, che sono i numeri della tabella sopra: riga $1$: $0{,}06;\ 0{,}12;\ 0{,}18;\ 0{,}24$; riga $2$: $0{,}10$ per tutte e quattro. Ci sono $8$ coppie, e $x_q$ e $y$ sono dipendenti (le righe di $\mathbf Q$ sono diverse): non si possono trattare come due sorgenti separate. Il codice ottimo è quello di Huffman applicato alle $8$ probabilità (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 →): $$0{,}24,\ 0{,}18,\ 0{,}12,\ 0{,}10,\ 0{,}10,\ 0{,}10,\ 0{,}10,\ 0{,}06.$$ Ad ogni passo si uniscono i due simboli meno probabili:

1. $0{,}06+0{,}10=0{,}16$ $\to$ $0{,}24;\ 0{,}18;\ 0{,}16;\ 0{,}12;\ 0{,}10;\ 0{,}10;\ 0{,}10$;
2. $0{,}10+0{,}10=0{,}20$ $\to$ $0{,}24;\ 0{,}20;\ 0{,}18;\ 0{,}16;\ 0{,}12;\ 0{,}10$;
3. $0{,}12+0{,}10=0{,}22$ $\to$ $0{,}24;\ 0{,}22;\ 0{,}20;\ 0{,}18;\ 0{,}16$;
4. $0{,}18+0{,}16=0{,}34$ $\to$ $0{,}34;\ 0{,}24;\ 0{,}22;\ 0{,}20$;
5. $0{,}22+0{,}20=0{,}42$ $\to$ $0{,}42;\ 0{,}34;\ 0{,}24$;
6. $0{,}34+0{,}24=0{,}58$ $\to$ $0{,}58;\ 0{,}42$; infine $0{,}58+0{,}42=1$.

Leggendo l'albero dalla radice (ramo $0$ verso $0{,}58$, ramo $1$ verso $0{,}42$) si ottiene, per esempio:

La lunghezza media è la somma di probabilità per lunghezza: $2\cdot0{,}24=0{,}48$; $3\cdot0{,}18=0{,}54$; $3\cdot0{,}12=0{,}36$; $3\cdot(3\cdot0{,}10)=0{,}90$ (tre coppie da $0{,}10$ con parola di $3$ bit); $4\cdot0{,}10=0{,}40$; $4\cdot0{,}06=0{,}24$. Somma: $$\bar L=0{,}48+0{,}54+0{,}36+0{,}90+0{,}40+0{,}24=2{,}92\ \text{bit per coppia.}$$ Verifica con la teoria: l'entropia congiunta delle coppie è $H(x_q,y)=2{,}879$ bit e il codice ottimo soddisfa $H\le\bar L<H+1$: $2{,}879\le2{,}92<3{,}879$, e il codice è molto vicino al limite. (La soluzione del corso riporta lo stesso valore, $2{,}92$ bit, con un altro codice di uguale lunghezza media.)

Se si numerano i livelli in modo diverso

Se invece la riga $1$ di $\mathbf Q$ fosse associata al livello positivo (probabilità $0{,}4$), si avrebbe $P(y)=(0{,}19;\,0{,}23;\,0{,}27;\,0{,}31)$, $H(y)=1{,}977$ e il codice di Huffman delle coppie avrebbe $\bar L=2{,}96$: l'assegnazione dei livelli alle righe conta, e il testo non la dichiara. Qui si segue quella della soluzione del corso (livelli in ordine crescente, prima riga $\leftrightarrow$ livello negativo, probabilità $0{,}6$).

(Verifica con Python: $P_{sat}=0{,}02$, $H(x_q)=0{,}9710$, $P(y)=(0{,}16;\,0{,}22;\,0{,}28;\,0{,}34)$, $H(y)=1{,}9470$, Huffman $\bar L=2{,}92$ ed $H(x_q,y)=2{,}8788$; per la numerazione opposta $1{,}9767$ e $2{,}96$.)

Errori comuni

• Calcolare $P_{sat}$ con due code: la densità finisce in $4<5{,}8$, quindi la coda destra è nulla.
• Assegnare a $x_q$ probabilità $\frac12,\frac12$ perché i livelli sono due: l'intervallo $[-6,0]$ è più largo di $[0,4]$.
• Dare a $y$ la densità della riga di $\mathbf Q$ senza pesare con $P(i)$.
• Codificare separatamente $x_q$ e $y$: sono dipendenti, il codice ottimo va costruito sulla congiunta.
• Sbagliare l'ordine dei passi di Huffman: ad ogni passo si fondono sempre i due meno probabili.