Esercizio - sensori di temperatura, codice di Huffman, porta seriale e informazione mutua (esercizi del corso, cap. 5, es. 56)

---

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 → (punto 1), 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 → (punti 2 e 4), 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 3 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) Codice di Huffman

Le probabilità ordinate sono $T_4=0{,}4$, $T_3=0{,}27$, $T_2=0{,}25$, $T_1=0{,}08$ (somma $1$ ✓). Si uniscono a ogni passo i due nodi meno probabili:

Si assegna $0$ al ramo di probabilità maggiore a ogni unione e si legge dalla radice alle foglie. Alla radice $T_4$ prende $0$ e il nodo $B$ prende $1$; sotto $B$, $T_3$ prende $0$ e il nodo $A$ prende $1$; sotto $A$, $T_2$ prende $0$ e $T_1$ prende $1$. Si ottiene

(La soluzione del corso riporta $T_1\to000$, $T_2\to001$, $T_3\to01$, $T_4\to1$: è lo stesso codice con $0$ e $1$ scambiati e i rami in altro ordine; le lunghezze sono quelle di sopra.)

Lunghezza media, pesando ogni lunghezza con la probabilità, e controllo con la somma dei nodi interni (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 →): $$L_y=0{,}4\cdot1+0{,}27\cdot2+0{,}25\cdot3+0{,}08\cdot3=0{,}4+0{,}54+0{,}75+0{,}24=1{,}93\ \text{bit},$$ $$0{,}33+0{,}60+1=1{,}93\ \checkmark.$$ L'entropia di un valore è $H=0{,}4\log_2\tfrac1{0{,}4}+0{,}27\log_2\tfrac1{0{,}27}+0{,}25\log_2\tfrac1{0{,}25}+0{,}08\log_2\tfrac1{0{,}08}=0{,}5288+0{,}5100+0{,}5+0{,}2915=1{,}830$ bit, quindi $H\le L_y<H+1$ ✓ ed efficienza $\eta=\frac{1{,}830}{1{,}93}=0{,}948$.

(2) Quanti sensori sulla porta seriale

Ogni sensore emette un valore ogni $1$ ms e il codice usa in media $1{,}93$ bit per valore: il suo flusso medio di bit è $$R=\frac{1{,}93\ \text{bit}}{10^{-3}\ \text{s}}=1930\ \text{bit/s}.$$ Il flusso aggregato di $N$ sensori è $N\cdot1930$ bit/s e deve essere al più $4200$ bit/s: $$N\le\frac{4200}{1930}=2{,}176\ \Rightarrow\ N_{\max}=2.$$ Con $N=2$ il flusso è $3860$ bit/s $\le4200$ ✓; con $N=3$ sarebbe $5790>4200$. Senza codifica (lunghezza fissa di $2$ bit per valore) ogni sensore farebbe $2000$ bit/s e la porta ne reggerebbe solo $2$ ($4000$ bit/s): il codice migliora l'efficienza ma, con questi numeri, non fa guadagnare un sensore ($4200/1930=2{,}18$). Il limite teorico dato dall'entropia sarebbe $1830$ bit/s per sensore, cioè $4200/1830=2{,}29$, ancora $N=2$.

(3) Entropia di una coppia di sensori

Siano $X_1,X_2$ i valori dei due sensori, ciascuno con la densità data, $H(X_i)=1{,}830$ bit.

• a) Indipendenti. $H(X_1,X_2)=H(X_1)+H(X_2)=2\cdot1{,}830=3{,}661$ bit (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 →).
• b) Dipendenti (con le stesse marginali): $H(X_1,X_2)<H(X_1)+H(X_2)$, strettamente minore: la coppia è meno incerta perché il valore di un sensore dà informazione sull'altro. Inoltre $H(X_1,X_2)\ge\max\{H(X_1),H(X_2)\}=1{,}830$ bit: nel caso estremo in cui un sensore ripete l'altro ($X_2=X_1$) l'entropia è esattamente $1{,}830$ bit.

Quindi la dipendenza diminuisce l'entropia, e con essa la lunghezza minima media delle parole per coppia.

(4) Limite inferiore per le coppie

La coppia $(X_1,X_2)$ ha solo quattro valori possibili, con probabilità $0{,}1;\ 0{,}2;\ 0{,}3;\ 0{,}4$ (somma $1$ ✓; le altre coppie hanno probabilità $0$). Il limite inferiore di Shannon alla lunghezza media di un codice binario per le coppie è la loro 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 →), e il "più grande possibile" è appunto $H(X_1,X_2)$: $$H(X_1,X_2)=0{,}1\log_2\tfrac1{0{,}1}+0{,}2\log_2\tfrac1{0{,}2}+0{,}3\log_2\tfrac1{0{,}3}+0{,}4\log_2\tfrac1{0{,}4}=0{,}3322+0{,}4644+0{,}5211+0{,}5288=1{,}846\ \text{bit}.$$ Le marginali di questa coppia ($X_2$: $0{,}1;0{,}2;0{,}3;0{,}4$) sono diverse da quelle del punto 1: è un altro scenario, in cui i due sensori sono fortemente dipendenti (il valore di $X_2$ determina quello di $X_1$), e per questo l'entropia della coppia è solo $1{,}846$ bit, quanto basta per una variabile con quelle quattro probabilità.

(5) Informazione mutua tra i due sensori

Ogni coppia ha $X_1\in\{T_1,T_3\}$ e $X_2\in\{T_1,T_2,T_3,T_4\}$. Dalle quattro coppie:

Conoscendo $X_2$ si conosce $X_1$ ($T_1,T_2\Rightarrow X_1=T_1$; $T_3,T_4\Rightarrow X_1=T_3$): $X_1$ è funzione deterministica di $X_2$, quindi $H(X_1|X_2)=0$. L'informazione mutua è $$I(X_1;X_2)=H(X_1)-H(X_1|X_2)=H(X_1)=0{,}3\log_2\tfrac1{0{,}3}+0{,}7\log_2\tfrac1{0{,}7}=0{,}5211+0{,}3602=0{,}881\ \text{bit}.$$ Controllo con la formula simmetrica: $H(X_1)+H(X_2)-H(X_1,X_2)=0{,}881+1{,}846-1{,}846=0{,}881$ ✓ (infatti $H(X_1,X_2)=H(X_2)$, perché la coppia è determinata da $X_2$, e vale $1{,}846$).

(Verificato con Python: Huffman $L_y=1{,}93$, $H=1{,}8303$, $N_{\max}=\lfloor2{,}176\rfloor=2$, $H(X_1,X_2)=1{,}8464$, $I=0{,}8813$.)

Errori comuni

• Dimenticare che $N$ è un intero: $2{,}18$ sensori sono $2$.
• Calcolare il flusso con la lunghezza dei codici al posto della lunghezza media (pesata con le probabilità).
• Per il punto 4, usare le probabilità dei singoli sensori ($0{,}08;0{,}25;\dots$) invece di quelle delle coppie.
• Scrivere $H(X_1,X_2)=H(X_1)+H(X_2)$ per variabili dipendenti.
• Per il punto 5, calcolare $H(X_1)$ con le probabilità dei singoli sensori invece che con le marginali della tabella delle coppie ($0{,}3;\ 0{,}7$).