Esercizio - codice di Elias, Huffman sulla coppia di sorgenti e informazione mutua (compito del 22 gennaio 2019, es. 92)

---

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-3), 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), 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) Codice di Elias per $X(n)$

Si ordinano i simboli come numeri naturali ($0,1,2$) e si divide $[0,1)$ in tre intervalli di ampiezza $p_X(0),p_X(1),p_X(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 →). Per ogni simbolo si calcolano il punto medio $m$ e la lunghezza $l=\lceil-\log_2p\rceil+1$.

Le rappresentazioni binarie: $\frac14=0{,}01_2$; $\frac58=\frac12+\frac18=0{,}101_2$ (pesi $2^{-1}$ e $2^{-3}$); $\frac78=\frac12+\frac14+\frac18=0{,}111_2$. Hanno già esattamente $l$ cifre: non c'è nulla da troncare. Il codice $\{01,\ 101,\ 111\}$ è a prefisso ✓. La lunghezza media è $$L_y=\frac12\cdot2+\frac14\cdot3+\frac14\cdot3=1+0{,}75+0{,}75=2{,}5\ \text{bit}.$$

(2) È il codice di Shannon? Raggiunge il limite inferiore?

Le lunghezze del codice di Elias sono $\lceil i_X(x)\rceil+1$, quelle del codice di Shannon sono $\lceil i_X(x)\rceil$ ($i_X=-\log_2p$). Il codice del punto 1 ha una cifra in più per ogni parola, quindi non è il codice di Shannon (quello avrebbe lunghezze $1,2,2$). Per lo stesso motivo la lunghezza media di Elias è sempre maggiore di quella di Shannon, che è a sua volta $\ge H(X)$ (limite inferiore del teorema di Shannon): quindi non raggiunge il limite inferiore. Il confronto numerico: $H(X)=\frac12\cdot1+\frac14\cdot2+\frac14\cdot2=1{,}5$ bit contro $L_y=2{,}5$ bit (la differenza è esattamente $1$ bit, perché le probabilità sono potenze di $\frac12$ e $\lceil i\rceil=i$). Il codice di Shannon, con lunghezze $1,2,2$, avrebbe $L_y=1{,}5=H$ e raggiungerebbe il limite.

(3) Codice ottimo per le parole $[X(n),Y(n)]$

Per ogni $X$ si hanno due valori possibili di $Y$: $Y=X$ con probabilità $0{,}3$ e $Y=X+1\bmod3$ con probabilità $0{,}7$. Le coppie hanno probabilità $P(x,y)=p_X(x)P(y|x)$:

La somma è $0{,}15+0{,}35+0{,}075+0{,}175+0{,}075+0{,}175=1$ ✓ (le altre $3$ coppie hanno probabilità $0$ e non sono nel dizionario). Huffman:

Un codice risultante: $(1,2)\to00$, $(2,0)\to01$, $(0,0)\to100$, $(0,1)\to11$, $(1,1)\to1010$, $(2,2)\to1011$ (lunghezze $2,2,3,2,4,4$). Lunghezza media con controllo dei nodi interni: $$L_y=0{,}175\cdot2\cdot2+0{,}15\cdot3+0{,}35\cdot2+0{,}075\cdot4\cdot2=0{,}70+0{,}45+0{,}70+0{,}60=2{,}45\ \text{bit},$$ $$0{,}15+0{,}30+0{,}35+0{,}65+1=2{,}45\ \checkmark.$$ Un altro assegnamento delle etichette o dei pareggi (la soluzione del corso usa $(0,0)\to110$, $(0,1)\to0$, $(1,1)\to1110$, $(1,2)\to101$, $(2,2)\to1111$, $(2,0)\to100$) dà la stessa $L_y=2{,}45$ bit. Limite: $H(X,Y)=2{,}381\le2{,}45<3{,}381$ ✓ (per coppia di simboli).

(4) Entropie e confronto

• $H(X)$: $\frac12\log_22+\frac14\log_24+\frac14\log_24=0{,}5+0{,}5+0{,}5=1{,}5$ bit.
• $H(Y)$: la densità di $Y$ si ottiene sommando le coppie con lo stesso $y$: $P_Y(0)=P(0,0)+P(2,0)=0{,}15+0{,}175=0{,}325$; $P_Y(1)=P(0,1)+P(1,1)=0{,}35+0{,}075=0{,}425$; $P_Y(2)=P(1,2)+P(2,2)=0{,}175+0{,}075=0{,}25$ (somma $1$ ✓). Quindi $$H(Y)=0{,}325\log_2\tfrac1{0{,}325}+0{,}425\log_2\tfrac1{0{,}425}+0{,}25\log_2\tfrac1{0{,}25}=0{,}5270+0{,}5247+0{,}5=1{,}5516\ \text{bit}.$$
• Entropia della coppia: $Y$ non è funzione deterministica di $X$ (dato $X$, $Y$ ha due valori possibili), quindi $H(Y|X)>0$. Dalla regola della catena (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)=H(X)+H(Y|X)=1{,}5+h(0{,}3)=1{,}5+0{,}8813=2{,}3813\ \text{bit}$$ ($H(Y|X=x)=h(0{,}3)$ per ogni $x$). Controllo diretto: $H(X,Y)=0{,}15\log_2\frac1{0{,}15}+0{,}35\log_2\frac1{0{,}35}+2\cdot0{,}075\log_2\frac1{0{,}075}+2\cdot0{,}175\log_2\frac1{0{,}175}=0{,}4106+0{,}5301+0{,}5606+0{,}8801=2{,}3813$ ✓.

Confronto con $H(X)$. La risposta dipende da come si legge "entropia media per simbolo":

• l'entropia della parola $[X,Y]$ è $H(X,Y)=2{,}381$ bit, strettamente maggiore di $H(X)=1{,}5$ bit, perché $Y$ non è funzione deterministica di $X$ ed è non nulla $H(Y|X)=0{,}8813$ bit (è la risposta della soluzione del corso);
• l'entropia per simbolo, nel senso della definizione $H_s=\frac{H(\underline x)}{L(\underline x)}$ del corso (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 →), divide per la lunghezza della parola ($2$ simboli): $H_s=\frac{2{,}3813}2=1{,}1906$ bit, strettamente minore di $H(X)=1{,}5$ bit. Infatti $H_s\le\frac{H(X)+H(Y)}2=1{,}5258$ e qui la dipendenza tra $X$ e $Y$ lo porta anche sotto $H(X)$.

Se il testo chiede l'entropia per simbolo con la definizione del corso la risposta è "strettamente minore"; la soluzione del corso risponde "strettamente maggiore" confrontando l'entropia della parola (non divisa per $2$) con $H(X)$.

(5) Informazione mutua $I(X;Y)$

Per la regola della catena $I(X;Y)=H(Y)-H(Y|X)$ (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 →): $$I(X;Y)=H(Y)-H(Y|X)=1{,}5516-0{,}8813=0{,}6703\ \text{bit}.$$ Controllo con la formula simmetrica: $H(X)+H(Y)-H(X,Y)=1{,}5+1{,}5516-2{,}3813=0{,}6703$ ✓. (Nel testo della soluzione del corso c'è un refuso, "$(a+1)\bmod4$" al posto di $\bmod3$, ma il valore usato, $H(Y|X)=0{,}88$ e $I=0{,}67$, è quello giusto.)

(Verificato con Python: Elias $01,101,111$ con $L_y=2{,}5$, Huffman delle coppie $L_y=2{,}45$ con somma dei nodi uguale, $H(X)=1{,}5$, $H(Y)=1{,}55163$, $H(X,Y)=2{,}38129$, $I=0{,}67034$.)

Errori comuni

• Dimenticare di mettere in ordine i simboli nel codice di Elias: i punti medi dipendono dall'ordine (ma qualunque ordine fisso funziona).
• Usare $l=\lceil-\log_2p\rceil$ (Shannon) per Elias: serve il $+1$.
• Credere che un codice con probabilità diadiche sia ottimo anche se è di Elias: lo è solo quello di Shannon.
• Per le coppie, assegnare probabilità a tutte le $9$ combinazioni: solo $6$ hanno probabilità non nulla.
• Per $H(Y)$, calcolarla da $P(Y=X)$ e $P(Y=X+1)$ senza sommare le coppie con lo stesso $y$.
• Confrontare l'entropia della parola con quella del singolo simbolo senza dividere per la lunghezza (e viceversa).