Esercizio - quantizzatore per densità esponenziale limitata tra -1 e 1, codice di Shannon e Huffman (esame del 23 gennaio 2024, es. 173)

---

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 →, 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 →, Quantizzazione non uniforme, companding e conversione A-DIn un quantizzatore non uniforme gli intervalli I_i hanno larghezze diverse (stretti dove la densità è alta) e la potenza dell'errore è M_e = Σ M_{e_i} P(x ∈ I_i), con M_{e_i} = E[(x − a_qi)² | x ∈ I_i]. Si realizza con il companding (compressore μ(x), quantizzatore uniforme, espansore) o raggruppando gli intervalli di un quantizzatore uniforme fine. Nella conversione A-D con campionamento ogni T_s e b bit per campione, T_b = T_s/b e R_b = b/T_s bit/s. Esempio completo con densità esponenziale a due lati: v_sat, b, bit rate e periodo di simbolo della 16-QAM.Quantizzazione non uniforme, companding e conversione A-D →.

La densità. È una campana a punta (esponenziale a due lati) limitata a $[-1,1]$, con valore massimo $\frac1{1{,}7}=0{,}588$ in $0$ e $\frac{e^{-1/3}}{1{,}7}=0{,}42$ ai bordi. La costante $1{,}7$ è un'approssimazione di $2\cdot3\,(1-e^{-1/3})=1{,}6992$ (normalizzazione: $\int_{-1}^1e^{-|a|/3}da=6\,(1-e^{-1/3})$), quindi l'area vale $1{,}0005$; la potenza data, $0{,}3$, è l'approssimazione di $\int a^2p_X=0{,}306$.

(1) Quantizzatore uniforme

Saturazione. I campioni stanno in $[-1,1]$ con certezza: $v_{sat}=1$ e $P_{sat}=0$.

Numero di bit. Con potenza $M_X=0{,}3$ (media nulla per simmetria, quindi $\sigma_X^2=0{,}3$) e $v_{sat}=1$: $$20\log_{10}\frac{\sigma_X}{v_{sat}}=20\log_{10}\sqrt{0{,}3}=-5{,}23\ \text{dB},\qquad c=-5{,}23+4{,}77=-0{,}46.$$ Si impone $c+6{,}02\,b\ge10$, cioè $$b\ge\frac{10-4{,}77+5{,}23}{6{,}02}=\frac{10{,}46}{6{,}02}=1{,}74\ \Longrightarrow\ b=2.$$ Con $b=1$ l'SNR sarebbe $-0{,}46+6{,}02=5{,}56$ dB (non basta), con $b=2$ $11{,}58$ dB. I livelli sono $L=2^2=4$, con passo $\Delta=\frac{2v_{sat}}L=0{,}5$, intervalli $[-1,-0{,}5]$, $[-0{,}5,0]$, $[0,0{,}5]$, $[0{,}5,1]$ e livelli $\pm0{,}25$, $\pm0{,}75$.

(2) Codice di Shannon

Probabilità dei livelli. Si integra la densità su ciascun intervallo (per simmetria bastano $[0,0{,}5]$ e $[0{,}5,1]$): $$P\big([0{,}5,1]\big)=\int_{0{,}5}^1\frac{e^{-a/3}}{1{,}7}da=\frac{3}{1{,}7}\Big(e^{-1/6}-e^{-1/3}\Big)=1{,}7647\,(0{,}8465-0{,}7165)=0{,}229,$$ $$P\big([0,0{,}5]\big)=\frac{3}{1{,}7}\Big(1-e^{-1/6}\Big)=1{,}7647\cdot0{,}1535=0{,}271.$$ Si arrotonda a $p_1=p_4=0{,}23$ (livelli esterni) e $p_2=p_3=0{,}27$ (livelli interni): somma $2(0{,}23+0{,}27)=1$.

Lunghezze. $\lceil-\log_2p\rceil$: per $0{,}23$, $-\log_20{,}23=2{,}12\Rightarrow3$ bit; per $0{,}27$, $-\log_20{,}27=1{,}89\Rightarrow2$ bit (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\cdot0{,}23\cdot3+2\cdot0{,}27\cdot2=1{,}38+1{,}08=2{,}46\ \text{bit.}$$ Il codice di Shannon spreca: la lunghezza fissa ($b=2$ bit) è già migliore ($2<2{,}46$). Un codice di Huffman su queste probabilità ($0{,}23;\ 0{,}27;\ 0{,}27;\ 0{,}23$) fonderebbe $0{,}23+0{,}23$ e $0{,}27+0{,}27$ e darebbe lunghezza $2$ a tutti i simboli, cioè $\bar L=2$ bit, appena sopra l'entropia ($1{,}995$ bit, punto 3).

(3) Un codice per $300$ valori con lunghezza media $300$ bit?

L'entropia di un campione quantizzato è $$H=-2\cdot0{,}23\log_20{,}23-2\cdot0{,}27\log_20{,}27=0{,}975+1{,}020=1{,}995\ \text{bit}.$$ I campioni sono indipendenti, quindi $300$ valori hanno entropia $300\,H=598{,}6$ bit (l'entropia di variabili indipendenti è la somma). Per il teorema di Shannon sulla codifica di sorgente ogni codice binario univocamente decodificabile ha lunghezza media non inferiore all'entropia: per $300$ valori almeno $598{,}6$ bit. Il codice proposto, con $300$ bit in media, richiederebbe una media di $1$ bit per valore, meno dei $1{,}995$ bit di informazione che ogni valore contiene. Non esiste. (La soluzione del corso riporta $598{,}5$ bit con l'entropia arrotondata a $1{,}995$.)

(4) Quantizzatore non uniforme e codice ottimo (Huffman)

Le probabilità sono $0{,}1;\ 0{,}14;\ 0{,}2;\ 0{,}24;\ 0{,}32$ (somma $1$). Il codice binario ottimo è quello di Huffman: si uniscono ripetutamente i due meno probabili.

1. $0{,}10+0{,}14=0{,}24$: restano $0{,}20;\ 0{,}24;\ 0{,}24;\ 0{,}32$;
2. $0{,}20+0{,}24=0{,}44$: restano $0{,}24;\ 0{,}32;\ 0{,}44$;
3. $0{,}24+0{,}32=0{,}56$: restano $0{,}44;\ 0{,}56$;
4. $0{,}44+0{,}56=1$.

Le parole risultanti (per esempio) sono $011$ ($0{,}1$), $010$ ($0{,}14$), $11$ ($0{,}2$), $10$ ($0{,}24$), $00$ ($0{,}32$): lunghezze $3,3,2,2,2$. Lunghezza media $$\bar L=0{,}1\cdot3+0{,}14\cdot3+0{,}2\cdot2+0{,}24\cdot2+0{,}32\cdot2=0{,}30+0{,}42+0{,}40+0{,}48+0{,}64=2{,}24\ \text{bit/campione}.$$ (Scegliendo diversamente il simbolo da unire a parità di probabilità, per esempio con la $0{,}24$ originale invece di quella fusa, si ottengono parole diverse ma la stessa lunghezza media $2{,}24$.) Poiché esce un campione ogni $10$ ms, il numero medio di bit al secondo in uscita dal codificatore è $$R=\frac{2{,}24\ \text{bit}}{10\cdot10^{-3}\ \text{s}}=224\ \text{bit/s}.$$ Controllo: l'entropia di queste probabilità è $2{,}214$ bit, quindi $2{,}214\le2{,}24<3{,}214$ e il minimo teorico sarebbe $221{,}4$ bit/s: Huffman è a $1{,}2\%$ dal limite.

(Tutti i risultati ricalcolati con Python: $b=1{,}74\to2$ con $11{,}58$ dB, $P=(0{,}2293;\,0{,}2709)$, $\bar L=2{,}46$, $H=1{,}9953$, $300H=598{,}6$, Huffman $2{,}24$, $H'=2{,}2139$, $224$ bit/s. Coincidono con le soluzioni del corso.)

Errori comuni

• Usare $v_{sat}>1$: il segnale non esce da $[-1,1]$, quindi basta $v_{sat}=1$.
• Fermarsi a $b=1{,}74$ senza arrotondare per eccesso, o dire $b=1$ perché "quasi basta".
• Nel punto 3, confrontare $300$ bit con $300\cdot2$ (lunghezza fissa) invece che con $300H$: la risposta si ottiene con il teorema di Shannon.
• Calcolare i bit al secondo moltiplicando per $10$ ms invece di dividere: $\frac{2{,}24}{0{,}01}=224$ bit/s.
• Considerare il codice di Shannon ottimo: l'ottimo è Huffman.