Esercizio - sorgente a sette simboli e codici di Shannon, Shannon-Fano e Huffman

Testo. Una sorgente senza memoria emette simboli presi da $\{A,B,C,D,E,F,G\}$. È noto che, in media, ogni $100$ simboli $40$ sono $A$, $16$ sono $B$, $15$ sono $C$, $10$ sono $D$, $8$ sono $E$, $6$ sono $F$ e $5$ sono $G$. Si calcoli l'entropia della sorgente. Che cosa dice il teorema di Shannon? Quale lunghezza media si ottiene con la codifica di Shannon? E con Shannon-Fano? E con Huffman? Si può migliorare l'efficienza dell'ultimo risultato?

Teoria usata: Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente →, Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua →.

Entropia e limiti di Shannon

Le probabilità sono $0{,}40;\ 0{,}16;\ 0{,}15;\ 0{,}10;\ 0{,}08;\ 0{,}06;\ 0{,}05$ (somma $1$). L'informazione di ciascun simbolo $\log_2\frac1p$ è: $1{,}322;\ 2{,}644;\ 2{,}737;\ 3{,}322;\ 3{,}644;\ 4{,}059;\ 4{,}322$ bit. Quindi $$H=0{,}4\cdot1{,}322+0{,}16\cdot2{,}644+0{,}15\cdot2{,}737+0{,}1\cdot3{,}322+0{,}08\cdot3{,}644+0{,}06\cdot4{,}059+0{,}05\cdot4{,}322=2{,}4457\ \text{bit}.$$ Il massimo possibile con $M=7$ è $\log_27=2{,}807$ bit; la sorgente non è equiprobabile e si può comprimere. Con una codifica a lunghezza fissa servono $\lceil\log_27\rceil=3$ bit per simbolo ($\eta=\frac{2{,}4457}3=0{,}815$). Per il teorema di Shannon, per un codice binario ($M_y=2$): $$2{,}4457\le\tilde L<3{,}4457.$$

Codifica di Shannon

Lunghezze $l_i=\lceil\log_2\frac1{p_i}\rceil$: $A\ 2$; $B\ 3$; $C\ 3$; $D\ 4$; $E\ 4$; $F\ 5$; $G\ 5$ (infatti $1{,}32\to2$, $2{,}64\to3$, $2{,}74\to3$, $3{,}32\to4$, $3{,}64\to4$, $4{,}06\to5$, $4{,}32\to5$). Kraft: $\frac14+2\cdot\frac18+2\cdot\frac1{16}+2\cdot\frac1{32}=\frac{11}{16}=0{,}6875\le1$: un codice a prefisso esiste. Si costruisce scendendo sull'albero un livello alla volta, assegnando a ogni simbolo il primo nodo libero che non sia discendente di una parola già scelta; una possibile scelta è $A=00$, $B=010$, $C=011$, $D=1000$, $E=1001$, $F=10100$, $G=10101$ (un'altra: $A=00$, $B=100$, $C=101$, $D=1100$, $E=1101$, $F=11100$, $G=11101$). La lunghezza media non dipende dalla scelta: $$\tilde L=0{,}4\cdot2+(0{,}16+0{,}15)\cdot3+(0{,}10+0{,}08)\cdot4+(0{,}06+0{,}05)\cdot5=0{,}8+0{,}93+0{,}72+0{,}55=3{,}00\ \text{bit},\qquad\eta=\frac{2{,}4457}{3{,}00}=0{,}815.$$ Rispetta i limiti, ma non migliora la codifica a lunghezza fissa (3 bit): la codifica di Shannon è subottima.

Codifica di Shannon-Fano

Ordine già decrescente. Primo taglio: $\{A,B\}$ ($0{,}56$) contro $\{C,D,E,F,G\}$ ($0{,}44$): differenza $0{,}12$ (l'alternativa $\{A\}$ contro il resto darebbe $0{,}40$ contro $0{,}60$, differenza $0{,}20$). Secondo: $\{A\},\{B\}$; e $\{C,D\}$ ($0{,}25$) contro $\{E,F,G\}$ ($0{,}19$), differenza $0{,}06$ (meglio di $\{C\}$ contro il resto: $0{,}15$ e $0{,}29$). Terzo: $\{C\},\{D\}$; $\{E\}$ ($0{,}08$) contro $\{F,G\}$ ($0{,}11$). Quarto: $\{F\},\{G\}$. Con $0$ a sinistra e $1$ a destra: $$A=00,\ B=01,\ C=100,\ D=101,\ E=110,\ F=1110,\ G=1111.$$ $$\tilde L=0{,}4\cdot2+0{,}16\cdot2+(0{,}15+0{,}10+0{,}08)\cdot3+(0{,}06+0{,}05)\cdot4=0{,}8+0{,}32+0{,}99+0{,}44=2{,}55\ \text{bit},\qquad\eta=\frac{2{,}4457}{2{,}55}=0{,}959.$$

Codifica di Huffman

Si uniscono sempre i due nodi meno probabili (Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente →, §7):

Una possibile assegnazione è $A=0$, $B=110$, $C=100$, $D=1110$, $E=1111$, $F=1010$, $G=1011$ (lunghezze $1,3,3,4,4,4,4$). Lunghezza media come somma dei nodi interni: $0{,}11+0{,}18+0{,}26+0{,}34+0{,}60+1=2{,}49$ bit; e pesando: $0{,}4\cdot1+(0{,}16+0{,}15)\cdot3+(0{,}10+0{,}08+0{,}06+0{,}05)\cdot4=0{,}4+0{,}93+1{,}16=2{,}49$ ✓. Efficienza $\eta=\frac{2{,}4457}{2{,}49}=0{,}982$. È il codice ottimo tra quelli con parole di lunghezza intera per singolo simbolo.

(Nota: il libro di testo a volte chiama "Shannon" quello che è Shannon-Fano, e viceversa: conviene fare riferimento alle procedure.)

Si può migliorare l'efficienza?

Sì, raggruppando i simboli: si applica Huffman a parole di $N$ simboli, di probabilità $p_ip_j$ (sorgente senza memoria). La lunghezza per simbolo $\frac{\tilde L}N$ soddisfa $H\le\frac{\tilde L}N<H+\frac1N$:

• $N=2$ ($49$ parole): $\frac{\tilde L}N=2{,}459$ bit/simbolo, $\eta=0{,}9946$;
• $N=3$ ($343$ parole): $2{,}4555$ bit/simbolo, $\eta=0{,}9960$.

Il prezzo è un dizionario che cresce come $7^N$ e un ritardo di codifica (si aspetta di avere $N$ simboli). In alternativa si può usare la codifica aritmetica, che si avvicina a $H$ senza costruire il dizionario.