Esercizio - due sorgenti indipendenti, codice di Shannon, Huffman e informazione mutua con un prodotto (compito del 24 gennaio 2025, es. 189)

---

Teoria usata: 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 → (punto 1, tasso nominale), 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 2), 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 → (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), 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 →.

(1) Cardinalità dell'alfabeto di $X$

Il tasso nominale di una sorgente è quello che si avrebbe se tutti i $M$ simboli fossero equiprobabili, $\frac{\log_2M}{T_s}$ (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 →). Con $T_s=2$ ms e tasso nominale $2$ kbit/s: $$\frac{\log_2M}{2\cdot10^{-3}\ \text{s}}=2\cdot10^3\ \text{bit/s}\ \Rightarrow\ \log_2M=4\ \Rightarrow\ M=2^4=16.$$ Coerenza: l'entropia $H(X)=2{,}45$ bit non può superare $\log_2M=4$ ✓ (la soluzione del corso scrive $T=2\ \mu$s e $4$ kbit/s per questo punto: è un refuso (con quei numeri non verrebbe $16$), ma il risultato finale riportato, $M=16$, è quello giusto).

(2) Il codice di Shannon può avere lunghezza media $4$ bit?

Il codice di Shannon binario ha lunghezze $l_i=\lceil-\log_2p_i\rceil$ e per esso vale, dal teorema di Shannon (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 →), $$H(X)\le L_y<H(X)+1=2{,}45+1=3{,}45\ \text{bit}.$$ La lunghezza media è strettamente minore di $3{,}45$ bit, quindi non può essere $4$ bit: la risposta è no.

(3) Codice ottimo per $Y$ (Huffman)

Probabilità ordinate: $0{,}49\,(Y_4);\ 0{,}23\,(Y_3);\ 0{,}20\,(Y_2);\ 0{,}08\,(Y_1)$ (somma $1$ ✓).

Codice: $Y_4\to0$, $Y_3\to10$, $Y_1\to110$, $Y_2\to111$ (qui $Y_1$ e $Y_2$ sono i due meno probabili, e restano fratelli in fondo all'albero).

$$L_y=0{,}49\cdot1+0{,}23\cdot2+0{,}20\cdot3+0{,}08\cdot3=0{,}49+0{,}46+0{,}60+0{,}24=1{,}79\ \text{bit},$$ controllo con i nodi interni: $0{,}28+0{,}51+1=1{,}79$ ✓. L'entropia è $H(Y)=1{,}7478$ bit, quindi $1{,}748\le1{,}79<2{,}748$ ✓ (efficienza $\eta=0{,}976$). Per confronto il codice di Shannon avrebbe lunghezze $\lceil-\log_2p\rceil=4,3,3,2$ per $Y_1,Y_2,Y_3,Y_4$ e $L_y=0{,}08\cdot4+0{,}2\cdot3+0{,}23\cdot3+0{,}49\cdot2=2{,}59$ bit, molto peggiore.

(4) Informazione mutua tra $Y$ e $W=Z\cdot Y$

Poiché $Y\in\{1,2,3,4\}$ non vale mai $0$, il prodotto $W=ZY$ vale $0$ se e solo se $Z=0$ e vale $Y$ se $Z=1$. $Z$ è indipendente da $Y$. Quindi:

• $P(W=0)=P(Z=0)=0{,}3$;
• per $y=1,\dots,4$: $P(W=y)=P(Z=1)P(Y=y)=0{,}7\,P(Y=y)$, cioè $P(W=1)=0{,}056$, $P(W=2)=0{,}14$, $P(W=3)=0{,}161$, $P(W=4)=0{,}343$ (con $0{,}3+0{,}056+0{,}14+0{,}161+0{,}343=1$ ✓).

Si usa $I(Y;W)=H(W)-H(W|Y)$ (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 →).

1. $H(W)$: $$H(W)=0{,}3\log_2\tfrac1{0{,}3}+0{,}056\log_2\tfrac1{0{,}056}+0{,}14\log_2\tfrac1{0{,}14}+0{,}161\log_2\tfrac1{0{,}161}+0{,}343\log_2\tfrac1{0{,}343}=0{,}5211+0{,}2329+0{,}3971+0{,}4242+0{,}5295=2{,}1048\ \text{bit}.$$
2. $H(W|Y)$: dato $Y=y$ (con $y\ne0$), $W$ vale $0$ con probabilità $0{,}3$ e $y$ con probabilità $0{,}7$ (dipende solo da $Z$, indipendente da $Y$): è una variabile binaria con entropia $h(0{,}3)=0{,}3\log_2\frac1{0{,}3}+0{,}7\log_2\frac1{0{,}7}=0{,}5211+0{,}3602=0{,}8813$ bit, uguale per ogni $y$. Mediando sui valori di $Y$ (pesi che sommano a $1$): $H(W|Y)=0{,}8813$ bit $=H(Z)$.
3. Informazione mutua: $$I(Y;W)=2{,}1048-0{,}8813=1{,}2235\ \text{bit}.$$

Controllo con la formula simmetrica. $W$ è funzione di $(Y,Z)$, e $Z$ è funzione di $(Y,W)$ ($Z=0$ se $W=0$, altrimenti $Z=1$): la coppia $(Y,W)$ ha quindi la stessa entropia di $(Y,Z)$, che per indipendenza è $H(Y,W)=H(Y)+H(Z)=1{,}7478+0{,}8813=2{,}6291$. Allora $I(Y;W)=H(Y)+H(W)-H(Y,W)=1{,}7478+2{,}1048-2{,}6291=1{,}2235$ ✓.

(5) Entropie dei vettori $[X,Y,Z]$ e $[Y,Z,W]$

• $[X,Y,Z]$: le tre sorgenti sono indipendenti, quindi l'entropia congiunta è la somma (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 →): $$H([X,Y,Z])=H(X)+H(Y)+H(Z)=2{,}45+1{,}7478+0{,}8813=5{,}0791\ \text{bit}.$$ (La soluzione del corso scrive $H(W)$ dove intende $H(Z)=h(0{,}3)=0{,}8813$ bit: è un refuso, il valore usato è questo.)
• $[Y,Z,W]$: $W=ZY$ è funzione deterministica di $(Y,Z)$, quindi $H([Y,Z,W])=H([Y,Z])=H(Y)+H(Z)=1{,}7478+0{,}8813=2{,}6291$ bit (con $Y$ e $Z$ indipendenti). Aggiungere $W$ non aumenta l'entropia.

(Verificato con Python: $H(Y)=1{,}74784$, $H(Z)=0{,}88129$, $H(W)=2{,}10478$, $I(Y;W)=1{,}22349$ anche calcolata dalla tabella congiunta $P(Y,W)$, Huffman $L_y=1{,}79$, Shannon $L_y=2{,}59$, $H([X,Y,Z])=5{,}0791$, $H([Y,Z,W])=2{,}6291$.)

Errori comuni

• Calcolare la cardinalità da $2^{H}$ (con $H=2{,}45$ viene $5{,}5$) invece che dal tasso nominale, che usa $\log_2M$.
• Rispondere al punto 2 con "sì perché $4\ge H$": il codice di Shannon ha $L_y<H+1$, un limite superiore.
• Scrivere $H(W)=H(Y)+H(Z)$: $W$ non ha come valori le coppie, ma i prodotti, e il valore $0$ ha probabilità $0{,}3$ per ogni $Y$.
• Scordare che $W=0$ solo per $Z=0$ (perché $Y\ne0$): è ciò che rende $Z$ funzione di $(Y,W)$.
• Al punto 5, usare l'additività per $[Y,Z,W]$: $W$ non è indipendente da $(Y,Z)$, ne è funzione.