Esercizio - Entropia, codici di Huffman e Exp-Golomb (domande ed esercizi del corso)

Teoria: Codifica lossless - entropia, Huffman e codifiche a dizionarioLa codifica lossless rappresenta i simboli di una sorgente con parole di codice a lunghezza variabile in modo invertibile; si usano codici a prefisso (istantanei). L'entropia $H(X)=\sum p_i\log_2\frac1{p_i}$ è il limite: $H(X)\le\mathcal L^*<H(X)+1$ (Shannon), con uguaglianza se le probabilità sono potenze di 1/2. Il codice di Huffman è ottimo ma lascia fino a 1 bit di overhead per simbolo; raggruppando $K$ simboli (codifica a blocchi) si tende al tasso entropico $\mathcal H(X)\le H(X)$, ma la complessità cresce come $M^K$; la codifica aritmetica ($\mathcal L<H+2$ per messaggio) ha complessità lineare. Altre tecniche: dizionario (LZ, DEFLATE di ZIP e PNG, ANS in Zstandard), Exp-Golomb e categoria/ampiezza (usati in JPEG e nei codec video) per interi con probabilità decrescente col modulo, codifica predittiva (si codifica l'errore di predizione, che ha entropia molto più bassa).Codifica lossless - entropia, Huffman e codifiche a dizionario → (entropia, teorema di Shannon, algoritmo di Huffman, codifica a blocchi, Exp-Golomb). Fonte: domande a risposta multipla ed esempi di preparazione del corso di Reti di Calcolatori, Ing. Informatica UniPD 2025-26, e slide del corso. Tutti i conti sono verificati in Python.

Formule di riferimento: $H(X)=\sum p_i\log_2\frac1{p_i}$; lunghezza media $\mathcal L=\sum p_i\ell_i$; teorema di Shannon $H\le\mathcal L^*<H+1$ (uguaglianza solo per probabilità potenze di $\frac12$).

1. Entropia

Domanda 1. Una sorgente emette $A$ con probabilità $0{,}5$ e $B$ con probabilità $0{,}5$. Entropia? (a) 1 bit, (b) 0,5 bit, (c) 2 bit, (d) 0 bit.

$H=0{,}5\log_22+0{,}5\log_22=0{,}5\cdot1+0{,}5\cdot1=1$ bit: (a). (b) è la probabilità, non l'entropia; (c) sarebbe l'entropia di 4 simboli equiprobabili ($\log_24$); (d) è l'entropia di una sorgente deterministica (un simbolo con probabilità 1). Per due simboli equiprobabili si ha il massimo possibile, $\log_2M=1$.

Domanda 2. Quale affermazione è vera? (a) la lunghezza media del codice è sempre $\ge$ all'entropia, (b) sempre $\le$, (c) sempre uguale, (d) sempre intera.

(a): per il teorema di Shannon $\mathcal L\ge H$. (b) è falsa (si violerebbe il teorema: nessun codice decodificabile può scendere sotto l'entropia); (c) vale solo per probabilità diadiche; (d) falsa: $\mathcal L$ è una media pesata di interi e in generale non è intera (1,75 nell'esempio $\frac12,\frac14,\frac18,\frac18$).

Domanda 3 (teorica). Il minimo tasso di codifica senza perdite per un codice a prefisso (a) è maggiore o uguale all'entropia della sorgente, (b) minore o uguale, (c) è sempre un numero intero di bit. (a): è l'enunciato del teorema di Shannon sulla codifica di sorgente (per il codice ottimo, inoltre $\mathcal L^*<H+1$).

2. Codici di Huffman

Domanda 4 (sorgente a 4 simboli). $A:0{,}4,\ B:0{,}3,\ C:0{,}2,\ D:0{,}1$. Quale affermazione è corretta? (a) $H\approx1{,}85$ bit e $\mathcal L\approx2$ (Huffman), (b) $H\approx1{,}85$ bit e $\mathcal L\approx1{,}5$ (Huffman), (c) $H\approx2{,}5$ bit, (d) il codice ottimo non esiste.

• Entropia: $0{,}4\log_2\frac1{0{,}4}+0{,}3\log_2\frac1{0{,}3}+0{,}2\log_2\frac1{0{,}2}+0{,}1\log_2\frac1{0{,}1}=0{,}4\cdot1{,}322+0{,}3\cdot1{,}737+0{,}2\cdot2{,}322+0{,}1\cdot3{,}322=1{,}846$ bit.
• Huffman: si fondono i due meno probabili, $D+C=0{,}3$; ora i nodi sono $A:0{,}4$, $B:0{,}3$, $(CD):0{,}3$; si fondono $B$ e $(CD)$: $0{,}6$; infine $A+0{,}6=1$. Lunghezze: $A:1$, $B:2$, $C:3$, $D:3$; $\mathcal L=0{,}4\cdot1+0{,}3\cdot2+0{,}2\cdot3+0{,}1\cdot3=1{,}9$ bit, cioè $\approx2$.
• (a) è giusta. (b) è impossibile: $\mathcal L=1{,}5<H=1{,}85$ violerebbe Shannon (la risposta si può scartare senza fare conti). (c) l'entropia di 4 simboli non può superare $\log_24=2$. (d) il codice ottimo esiste sempre ed è dato dall'algoritmo di Huffman.

Domanda 5 (sorgente a 6 simboli: limite inferiore). Probabilità $A:0{,}5,\ B:0{,}15,\ C:0{,}10,\ D:0{,}20,\ E:0{,}04,\ F:0{,}01$. Quale affermazione è esatta? (a) la lunghezza media di un codice senza perdite non può essere inferiore a 1,959 bit, (b) il codice ottimo per questa distribuzione non può essere determinato, (c) il codice ottimo ammette due codeword di lunghezza un bit.

Entropia: $0{,}5\cdot1+0{,}15\cdot2{,}737+0{,}10\cdot3{,}322+0{,}20\cdot2{,}322+0{,}04\cdot4{,}644+0{,}01\cdot6{,}644\approx1{,}9593$ bit. (a) vera: nessun codice istantaneo può scendere sotto $H$. (b) falsa: il codice ottimo si determina con Huffman. (c) falsa: due codeword da 1 bit ($0$ e $1$) esauriscono tutto lo spazio dei prefissi, e con più di due simboli non resterebbe nessuna parola disponibile per gli altri.

Domanda 6 (stessa sorgente: lunghezza media di Huffman). (a) 2 bit/simbolo, (b) 1,959 bit/simbolo, (c) non determinabile, (d) 3 bit/simbolo.

Costruzione: i due meno probabili sono $F:0{,}01$ ed $E:0{,}04$, $\to0{,}05$. Poi i due meno probabili sono $0{,}05$ e $C:0{,}10$, $\to0{,}15$. Poi $B:0{,}15$ e il nodo $0{,}15$, $\to0{,}30$ (a pari probabilità se ne sceglie uno qualunque: la lunghezza media non cambia). Poi $D:0{,}20$ e $0{,}30$, $\to0{,}50$. Infine $A:0{,}5$ e $0{,}50\to1$.

$\mathcal L=1\cdot0{,}5+2\cdot0{,}20+3\cdot0{,}15+4\cdot0{,}10+5\cdot(0{,}04+0{,}01)=0{,}5+0{,}4+0{,}45+0{,}4+0{,}25=2{,}0$ bit: (a). (b) 1,959 è l'entropia: $\mathcal L=H$ solo per probabilità diadiche, qui non lo sono, quindi $\mathcal L>H$. (c) falsa. (d) 3 bit è la lunghezza del codice a lunghezza fissa per 6 simboli ($\lceil\log_26\rceil$): Huffman fa meglio (2,0).

Domanda 7 (altra sorgente a 6 simboli). $A:0{,}07,\ B:0{,}25,\ C:0{,}11,\ D:0{,}12,\ E:0{,}31,\ F:0{,}14$. (a) un codice ottimo ha lunghezza media 2,44 bit, (b) 2,61 bit, (c) la lunghezza media di un codice a prefisso può essere inferiore a 2,40 bit, (d) il codice ottimo non può essere determinato.

Entropia: $H=2{,}4068$ bit. Huffman: $A+C=0{,}18$; $D+F=0{,}26$; $B+0{,}18=0{,}43$; $E+0{,}26=0{,}57$; $0{,}43+0{,}57=1$. Lunghezze: $E,B$ a 2 bit; $A,C,D,F$ a 3 bit. Un codice possibile: $A=111,\ B=10,\ C=110,\ D=011,\ E=00,\ F=010$. $\mathcal L=2(0{,}31+0{,}25)+3(0{,}07+0{,}11+0{,}12+0{,}14)=1{,}12+1{,}32=2{,}44$ bit: (a). (c) falsa perché $\mathcal L\ge H=2{,}4068>2{,}40$. (b) è troppo alta per un codice ottimo (sarebbe oltre il minimo); (d) falsa.

3. Decodifica, blocchi ed Exp-Golomb

Decodifica di Huffman (slide). Con il codice $A=0$, $B=10$, $C=110$, $D=111$ (probabilità $\frac12,\frac14,\frac18,\frac18$, $\mathcal L=1{,}75=H$) decodificare $00101101111010$. Si legge un bit alla volta: $0\to A$; $0\to A$; $1,0\to B$; $1,1,0\to C$; $1,1,1\to D$; $1,0\to B$; $1,0\to B$. Risultato: $AABCDBB$.

Codifica a blocchi (slide). Sorgente $a_1:0{,}8$, $a_2:0{,}02$, $a_3:0{,}18$. $H=0{,}8157$. Huffman sui singoli simboli: $a_1=0$, $a_3=10$, $a_2=11$; $\mathcal L=0{,}8+2\cdot0{,}18+2\cdot0{,}02=1{,}2$ bit/simbolo, $0{,}384$ sopra l'entropia. Sulle 9 coppie: $\mathcal L=1{,}723$ bit per coppia $=0{,}8614$ bit/simbolo, solo $0{,}046$ sopra l'entropia. Il codice a blocchi (grande alfabeto: $3^2=9$ simboli) ha quasi eliminato l'overhead di un bit per simbolo.

Exp-Golomb (slide): codificare 8.

• uEG: $n+1=9=1001_2$ (4 bit), quindi $3$ zeri iniziali: $c_U(8)=0001001$.
• sEG: $m(8)=2\cdot8-1=15$; $15+1=16=10000_2$ (5 bit), 4 zeri: $c_S(8)=000010000$.
• Categoria/ampiezza: categoria $k=\lceil\log_29\rceil=4$, codice della categoria 4: $101$; ampiezza: $8=1000_2$ su 4 bit; $c_{CA}(8)=1011000$. Lunghezze: 7, 9, 7 bit. Per un numero grande come 8 la codifica per categoria e ampiezza è la più corta.

Decodifica di Exp-Golomb (costruito). Decodificare il flusso unsigned $0001001\ 1\ 00110$. Si contano gli zeri iniziali, $z$, poi si leggono $z+1$ bit che rappresentano $n+1$: $000\,|\,1001$: $z=3$, $1001_2=9$, $n=8$. Poi $1$: nessuno zero, $n+1=1$, $n=0$. Poi $00\,|\,110$: $z=2$, $110_2=6$, $n=5$. Risultato: $8,\,0,\,5$ (verificato: $c_U(5)=00110$).

Distribuzione diadica (costruito). $A:\frac12,\ B:\frac14,\ C:\frac18,\ D:\frac1{16},\ E:\frac1{16}$. $H=\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+\frac1{16}\cdot4\cdot2=1{,}875$ bit. Huffman: lunghezze $1,2,3,4,4$, $\mathcal L=0{,}5+0{,}5+0{,}375+0{,}5=1{,}875$: $\mathcal L=H$ perché tutte le probabilità sono potenze di $\frac12$, e il codice assegna a ogni simbolo $\ell_i=\log_2\frac1{p_i}$.

Errori tipici

• Dimenticare di sommare tutte le codeword nella lunghezza media (e di pesarle con le probabilità, non con 1).
• Credere che $\mathcal L<H$ sia possibile: è la prima opzione da scartare nelle domande.
• Fondere a ogni passo i nodi sbagliati: si fondono sempre i due con probabilità minima (inclusi i nodi già fusi).
• Prendere come lunghezza del codice a lunghezza fissa $\log_2M$ senza arrotondare (6 simboli: 3 bit, non 2,58).
• Scrivere $n$ invece di $n+1$ nella scrittura binaria di uEG (si conta $n+1$).