Esercizio - Huffman, Elias ed entropia con probabilità dipendenti dalla matricola (secondo compitino dell'8 gennaio 2021, es. 118)

---

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), 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 → e 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 → (punto 4), 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 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 5).

Il testo dipende dalla matricola: si risolve per ciascuno dei cinque valori di $N$. La probabilità del quarto simbolo si ricava dalla normalizzazione: $p(4)=1-2N-0{,}2=0{,}8-2N$.

(1) Codice di Huffman e lunghezza media

Per $N=0{,}05,\ 0{,}10,\ 0{,}15$ il simbolo $4$ è il più probabile e i simboli $1,2$ i meno probabili. Passi: (i) si uniscono $1$ e $2$ in un nodo da $2N$; (ii) si unisce $3$ ($0{,}2$) con quel nodo ($2N\le0{,}3$) in un nodo da $0{,}2+2N$; (iii) radice con il simbolo $4$. Le lunghezze sono $3,3,2,1$ per i simboli $1,2,3,4$ (per esempio $1\to000$, $2\to001$, $3\to01$, $4\to1$ per $N=0{,}05$) e $$L_y=3N+3N+2\cdot0{,}2+1\cdot(0{,}8-2N)=4N+1{,}2.$$ Controllo con i nodi interni: $2N+(0{,}2+2N)+1=4N+1{,}2$ ✓.

Per $N=0{,}20$ le probabilità sono $(0{,}2;0{,}2;0{,}2;0{,}4)$ e al primo passo c'è un pareggio tra tre simboli da $0{,}2$. Unendo $1+2=0{,}4$ si hanno i nodi $0{,}4;0{,}4;0{,}2$: si unisce $3$ ($0{,}2$) con il simbolo $4$ ($0{,}4$) in un nodo da $0{,}6$, poi la radice. Le lunghezze sono $2,2,2,2$ e $L_y=2{,}0$. Un'altra scelta dei pareggi dà le lunghezze $3,3,2,1$ e di nuovo $L_y=0{,}2\cdot3+0{,}2\cdot3+0{,}2\cdot2+0{,}4\cdot1=2{,}0$.

Per $N=0{,}25$ le probabilità sono $(0{,}25;0{,}25;0{,}2;0{,}3)$: si uniscono i due meno probabili, $3$ ($0{,}2$) e un simbolo da $0{,}25$, in $0{,}45$; poi l'altro $0{,}25$ con $0{,}3$ in $0{,}55$; poi la radice. Lunghezze $2,2,2,2$, $L_y=2$ bit.

In ogni caso $H(X)\le L_y<H(X)+1$ ✓ (la somma dei nodi interni coincide con $L_y$).

(2) È un codice di Shannon?

Il codice di Shannon ha lunghezze $l_i=\lceil-\log_2p(i)\rceil$. Si confrontano con quelle di Huffman del punto 1:

No, per nessun valore di $N$. Le probabilità non sono mai tutte potenze di $\frac12$ (condizione per cui il codice di Shannon è ottimo): $p(3)=0{,}2$ non lo è mai, e quindi il codice di Shannon ha almeno una parola più lunga di quella ottima, per esempio $\lceil-\log_20{,}2\rceil=3$ contro $2$.

(3) Parola di Elias per il simbolo $1$

Con l'ordine naturale il simbolo $1$ occupa il primo intervallo $[0,N)$, con punto medio $m=\frac N2$ e lunghezza $l=\lceil-\log_2N\rceil+1$. La parola è formata dalle prime $l$ cifre binarie di $m$ (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 →).

Esempio di conversione ($N=0{,}05$): $0{,}025\cdot2=0{,}05\to0$; $0{,}1\to0$; $0{,}2\to0$; $0{,}4\to0$; $0{,}8\to0$; $1{,}6\to1$, e le prime $6$ cifre sono $000001$. (La soluzione del corso riporta $0001$ anche per $N=0{,}25$, ma con $l=3$ la parola è $001$: la sua lunghezza deve essere $3$.)

(4) Entropia di $X$ con $p(1)=p(3)$ e $p(2)=p(4)$

Siano $p_1=p(1)=p(3)$ e $p_2=p(2)=p(4)$. La normalizzazione dà $2p_1+2p_2=1$, cioè $p_2=\frac12-p_1$. L'entropia condizionata $H(Z|X)$ è la media delle entropie condizionate ai valori di $X$, pesate con $p(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 →): $$H(Z|X)=p_1\cdot2N+p_2\cdot N+p_1\cdot2N+p_2\cdot N=4Np_1+2Np_2=4Np_1+2N\left(\tfrac12-p_1\right)=2Np_1+N.$$ Il testo dà $H(Z|X)=N+\frac32N^2$, quindi $2Np_1=\frac32N^2$, cioè $$p_1=\frac34N,\qquad p_2=\frac12-\frac34N.$$ L'entropia di $X$ è $$H(X)=2p_1\log_2\frac1{p_1}+2p_2\log_2\frac1{p_2}.$$

(Esempio per $N=0{,}05$: $2\cdot0{,}0375\log_2\frac1{0{,}0375}=0{,}075\cdot4{,}737=0{,}3553$ e $2\cdot0{,}4625\log_2\frac1{0{,}4625}=0{,}925\cdot1{,}1125=1{,}0290$; la somma è $1{,}384$. Si noti che sono tutti sotto $\log_24=2$ bit.)

(5) Esistono codici di sorgente e di canale con errore piccolo a piacere?

La velocità di prelievo dal buffer è $R=\frac{L_y}2$ bit/s, quella dei bit che entrano nel codificatore di canale. Per il teorema di Shannon sulla codifica di canale (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 →) una codifica con errore piccolo a piacere esiste se $R\le C$ ($R<C$ per sicurezza): $$\frac{L_y}2<0{,}6\ \text{bit/s}\ \Rightarrow\ L_y<1{,}2\ \text{bit}.$$ Per il teorema di Shannon sulla codifica di sorgente esiste un codice a prefisso con $L_y<H(X)+1=0{,}1+1=1{,}1$ bit (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 →), senza bisogno di conoscere cardinalità e densità. Poiché $1{,}1<1{,}2$, esiste un codice di sorgente con $L_y<1{,}1$, quindi con $R<0{,}55<0{,}6=C$: il codice di canale esiste per il teorema di Shannon. La risposta è sì.

(Nota: $L_y\ge H(X)=0{,}1$ per ogni codice di sorgente, quindi l'intervallo $[0{,}1;\ 1{,}1)$ è non vuoto; un'entropia così piccola indica una sorgente quasi deterministica, che si può comprimere molto raggruppando più simboli.)

(Verificato con Python: Huffman per i cinque valori di $N$, $L_y=1{,}4;\,1{,}6;\,1{,}8;\,2{,}0;\,2{,}0$ con somma dei nodi uguale; Shannon e Huffman mai uguali; punti medi di Elias e loro cifre; $p_1=\frac34N$ e $H(X)=1{,}3843;\,1{,}6098;\,1{,}7692;\,1{,}8813;\,1{,}9544$.)

Errori comuni

• Dimenticare di ricavare $p(4)$ dalla normalizzazione.
• Scrivere le lunghezze di Huffman senza controllare che i pareggi ($N=0{,}10$, $N=0{,}20$) non cambino $L_y$: cambiano il codice, non la lunghezza media.
• Per il punto 2, dire "è Shannon se le lunghezze sono uguali a quelle ottime": va verificato il confronto con $\lceil-\log_2p\rceil$ per ogni simbolo.
• In Elias, prendere $m=N$ (estremo) al posto del punto medio $\frac N2$, o dimenticare il $+1$.
• Al punto 4, mediare $H(Z|X=x)$ con pesi uguali invece che con $p(x)$.
• Al punto 5, usare $L_y\ge H$ come se fosse $L_y<H$: per l'esistenza serve il limite superiore $L_y<H+1$.