Esercizio - Huffman, codice di Shannon, funzione deterministica di una sorgente e informazione mutua di un canale (secondo compitino del 9 gennaio 2026, es. 196)

---

Teoria usata: 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 → (punti 1 e 2), Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza mediaLa codifica di sorgente senza perdite associa a ogni parola emessa dalla sorgente una parola di codice binaria (o $M_y$-aria) di lunghezza variabile, in modo invertibile; la qualità si misura con la lunghezza media $L_y=\sum p_{\underline x}(\underline a),l(\underline a)$. In un codice a prefisso nessuna parola è l'inizio di un'altra, quindi la decodifica è istantanea. Kraft-McMillan: ogni codice decodificabile ha $\sum M_y^{-l_i}\le1$, e se interi $l_i$ la soddisfano esiste un codice a prefisso con quelle lunghezze. Shannon: $\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1$ per il codice a prefisso ottimo, con $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze di $\frac1{M_y}$.Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media → (punto 3), 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 → (punti 4 e 5), Tasso d'informazione, capacità di canale e teorema di ShannonUna sorgente che emette un simbolo ogni $T$ secondi ha tasso d'informazione $R=\frac{H_s}T$ [bit/s] ($H_s$ entropia per simbolo); un canale ha tasso $R(g)=\frac{I_s(x;y)}T\le R(x)$. La capacità è il massimo del tasso del canale su tutte le statistiche d'ingresso, $C=\max_{p_x}\frac{I(x;y)}T$ per un canale senza memoria. Teorema di Shannon: se il tasso nominale della sorgente è $R\le C$ esiste un codice di canale con probabilità d'errore piccola a piacere, se $R>C$ no. Capacità: BSC $C=\frac1T[1-h(P_{bit})]$, canale a cancellazione $C=\frac{1-\alpha}T$, AWGN reale $C=\frac1{2T}\log_2\left(1+\frac{E_s}{\sigma^2}\right)$; canali in parallelo sommano le capacità.Tasso d'informazione, capacità di canale e teorema di Shannon →.

(1) Codice di Huffman

Probabilità ordinate: $0{,}39\,(s_6);\ 0{,}21\,(s_5);\ 0{,}18\,(s_4);\ 0{,}12\,(s_3);\ 0{,}05\,(s_1);\ 0{,}05\,(s_2)$ (somma $1$ ✓). A ogni passo si uniscono i due nodi meno probabili.

Al passo 4 c'è un pareggio ($s_6$ e $C$ valgono entrambi $0{,}39$): si può unire $B$ con l'uno o con l'altro. Scegliendo $C$ si ottiene il codice sotto; scegliendo $s_6$ si otterrebbe un altro codice (con $s_6$ di $2$ bit), ma con la stessa lunghezza media. Etichettando con $1$ il ramo di $s_6$ alla radice, con $0$ quello di $D$, poi $D\to C=0,\ B=1$, $C\to s_5=0,\ s_4=1$, $B\to A=0,\ s_3=1$, $A\to s_1=0,\ s_2=1$:

Le parole dei simboli $1$ e $2$ sono $0100$ e $0101$ (le due parole più lunghe, che differiscono solo nell'ultimo bit, come deve essere in un codice ottimo). Lunghezza media e controllo con i nodi interni: $$L_y=0{,}39\cdot1+(0{,}21+0{,}18+0{,}12)\cdot3+(0{,}05+0{,}05)\cdot4=0{,}39+1{,}53+0{,}40=2{,}32\ \text{bit},$$ $$0{,}10+0{,}22+0{,}39+0{,}61+1=2{,}32\ \checkmark.$$ Con l'altra scelta del pareggio le lunghezze sarebbero $4,4,3,2,2,2$ per $s_1,s_2,s_3,s_4,s_5,s_6$ e $L_y=0{,}4+0{,}36+0{,}18\cdot2+0{,}21\cdot2+0{,}39\cdot2=2{,}32$ bit: la stessa. L'entropia è $H(s)=2{,}247$ bit, quindi $2{,}247\le2{,}32<3{,}247$ ✓.

(2) Codice di Shannon

Le lunghezze sono $l_i=\lceil-\log_2p_i\rceil$:

Controllo di Kraft: $2\cdot\frac1{32}+\frac1{16}+2\cdot\frac18+\frac14=0{,}625\le1$ ✓. La lunghezza media è $$L_y=\sum p_il_i=0{,}05\cdot5\cdot2+0{,}12\cdot4+0{,}18\cdot3+0{,}21\cdot3+0{,}39\cdot2=0{,}50+0{,}48+0{,}54+0{,}63+0{,}78=2{,}93\ \text{bit}.$$ Peggiore del codice ottimo ($2{,}32$), come ci si aspetta, ma dentro il limite $H\le L_y<H+1=3{,}247$.

(3) Limite di Shannon per $z_n$

La variabile $z_n$ accorpa i simboli $1,2,3$ nel valore $1$ e lascia gli altri: ha alfabeto $\{1,4,5,6\}$ e probabilità $$p_z(1)=p_s(1)+p_s(2)+p_s(3)=0{,}05+0{,}05+0{,}12=0{,}22,\quad p_z(4)=0{,}18,\ p_z(5)=0{,}21,\ p_z(6)=0{,}39$$ (somma $0{,}22+0{,}18+0{,}21+0{,}39=1$ ✓). Per il teorema di Shannon la lunghezza media di un codice binario è almeno l'entropia (Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza mediaLa codifica di sorgente senza perdite associa a ogni parola emessa dalla sorgente una parola di codice binaria (o $M_y$-aria) di lunghezza variabile, in modo invertibile; la qualità si misura con la lunghezza media $L_y=\sum p_{\underline x}(\underline a),l(\underline a)$. In un codice a prefisso nessuna parola è l'inizio di un'altra, quindi la decodifica è istantanea. Kraft-McMillan: ogni codice decodificabile ha $\sum M_y^{-l_i}\le1$, e se interi $l_i$ la soddisfano esiste un codice a prefisso con quelle lunghezze. Shannon: $\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1$ per il codice a prefisso ottimo, con $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze di $\frac1{M_y}$.Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media →): $$H(z)=0{,}22\log_2\tfrac1{0{,}22}+0{,}18\log_2\tfrac1{0{,}18}+0{,}21\log_2\tfrac1{0{,}21}+0{,}39\log_2\tfrac1{0{,}39}=0{,}4806+0{,}4453+0{,}4728+0{,}5298=1{,}9285\ \text{bit}.$$ Il limite inferiore è $1{,}93$ bit per simbolo $z_n$ (minore di $H(s)=2{,}247$: l'accorpamento fa perdere informazione).

(4) $H(z_n|s_n)$

$z_n$ è una funzione deterministica di $s_n$: noto $s_n$ il valore di $z_n$ è fissato. Quindi per ogni $b$ la densità $P_{z|s}(\cdot|b)$ ha un solo valore con probabilità $1$ e $H(z|s=b)=0$; mediando, $$H(z_n|s_n)=\sum_bP_s(b)\,H(z|s=b)=0.$$ Equivalentemente, per la regola della catena, $H(z|s)=H(s,z)-H(s)=H(s)-H(s)=0$ perché $H(s,z)=H(s)$ (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 →).

(5) Informazione mutua del canale

Si usa $I(X;Y)=H(Y)-H(Y|X)$ con $X$ uniforme: $P_X(i)=\frac16$.

1. Uscita. Per $j=1,\dots,4$: $P_Y(j)=\frac16\cdot1=\frac16$. Per $j=5$: $P_Y(5)=\frac16\cdot0{,}8+\frac16\cdot0{,}2=\frac16$ (arriva da $5$ con $0{,}8$ e da $6$ con $0{,}2$), e allo stesso modo $P_Y(6)=\frac16$. L'uscita è uniforme su $6$ simboli: $$H(Y)=\log_26=2{,}585\ \text{bit}.$$
2. $H(Y|X)$. Per $X=i\le4$ l'uscita è deterministica: $H(Y|X=i)=0$. Per $X=5$ e $X=6$ l'uscita vale uno dei due simboli con probabilità $0{,}8$ e $0{,}2$: $H(Y|X=5)=H(Y|X=6)=h(0{,}2)=0{,}2\log_25+0{,}8\log_2\frac54=0{,}4644+0{,}2575=0{,}7219$ bit. La media sui sei ingressi equiprobabili: $$H(Y|X)=\frac46\cdot0+\frac26\cdot0{,}7219=0{,}2406\ \text{bit}.$$
3. Informazione mutua. $$I(X;Y)=2{,}585-0{,}2406=2{,}344\ \text{bit per uso del canale}.$$

Osservazione. L'ingresso uniforme non è l'ingresso ottimo: massimizzando numericamente $I(X;Y)$ su tutte le densità d'ingresso (algoritmo di Blahut-Arimoto) si ottiene la capacità $C=2{,}382$ bit per uso, con $P_X=0{,}192$ per ciascuno dei simboli $1,\dots,4$ e $0{,}116$ per i simboli $5$ e $6$: conviene usare meno i due simboli che si confondono (Tasso d'informazione, capacità di canale e teorema di ShannonUna sorgente che emette un simbolo ogni $T$ secondi ha tasso d'informazione $R=\frac{H_s}T$ [bit/s] ($H_s$ entropia per simbolo); un canale ha tasso $R(g)=\frac{I_s(x;y)}T\le R(x)$. La capacità è il massimo del tasso del canale su tutte le statistiche d'ingresso, $C=\max_{p_x}\frac{I(x;y)}T$ per un canale senza memoria. Teorema di Shannon: se il tasso nominale della sorgente è $R\le C$ esiste un codice di canale con probabilità d'errore piccola a piacere, se $R>C$ no. Capacità: BSC $C=\frac1T[1-h(P_{bit})]$, canale a cancellazione $C=\frac{1-\alpha}T$, AWGN reale $C=\frac1{2T}\log_2\left(1+\frac{E_s}{\sigma^2}\right)$; canali in parallelo sommano le capacità.Tasso d'informazione, capacità di canale e teorema di Shannon →). La differenza ($2{,}382$ contro $2{,}344$) è piccola. La domanda chiede però solo $I$ con ingresso equiprobabile.

(Verificato con Python: Huffman $L_y=2{,}32$ con tutti e due i pareggi, Shannon $L_y=2{,}93$, $H(z)=1{,}9285$, $I=2{,}3443$, $C=2{,}3820$. Il corso riporta gli stessi valori.)

Errori comuni

• Al passo del pareggio in Huffman pensare che il codice sia sbagliato se non coincide con quello della soluzione: quello che conta è $L_y$, che è uguale.
• Per il codice di Shannon, usare $\lfloor\cdot\rfloor$ o l'arrotondamento al più vicino invece di $\lceil\cdot\rceil$.
• Per $z_n$, mettere nel limite inferiore l'entropia di $s_n$ invece di quella di $z_n$.
• Dire che $H(z|s)=H(z)$ o $H(s)$: per una funzione deterministica è nulla.
• Nel punto 5, calcolare $H(Y|X)$ con una media semplice senza pesare con le probabilità d'ingresso.