Esercizio 26entropia ed efficienza di una sorgente quaternaria e trasformazioni dei simboli (tema d'esame gennaio 2021)

---

Teoria usata: Informazione ed entropiaL'informazione di un evento di probabilità $p$ è $\log_2\frac1p$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza della sorgente: $0\le H\le\log_2M$, con il massimo quando i simboli sono equiprobabili. Per più simboli: $H(x,y)\le H(x)+H(y)$ (uguaglianza se indipendenti), $H(x|y)=H(x,y)-H(y)$. Per una sorgente con $F_s$ simboli al secondo il rate di informazione è $F_sH_s$, il rate nominale $F_s\log_2M$ e l'efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione ed entropia →, Codifica di sorgente - codici a prefisso e teorema di ShannonLa codifica di sorgente riduce il numero di bit mappando le parole della sorgente in parole di lunghezza variabile (più corte per le più probabili), senza perdere informazione. Il codice deve essere decodificabile; i codici a prefisso (nessuna parola è prefisso di un'altra) lo sono. Kraft-McMillan: se il codice è decodificabile $\sum M_y^{-L(b)}\le1$. Teorema di Shannon: $L_y\ge\frac{H(x)}{\log_2M_y}$ e esiste un codice a prefisso con $L_y\le\frac{H(x)}{\log_2M_y}+1$; l'efficienza è $\eta=\frac{H(x)}{L_y\log_2M_y}$.Codifica di sorgente - codici a prefisso e teorema di Shannon →, Codici di Shannon-Fano e di HuffmanIn un codice ottimo le parole più probabili non sono più lunghe di quelle meno probabili e le due parole più lunghe differiscono solo per l'ultimo simbolo. Shannon-Fano costruisce l'albero dall'alto dividendo ripetutamente i simboli in due gruppi di probabilità quasi uguali; Huffman lo costruisce dal basso unendo ogni volta i due simboli meno probabili ed è sempre ottimo tra i codici a prefisso. La lunghezza media $L_y$ è la somma delle probabilità dei nodi uniti, l'efficienza è $\eta=\frac{H}{L_y}$.Codici di Shannon-Fano e di Huffman →.

Dati

La probabilità mancante è $p(2)=1-0{,}2-0{,}3-0{,}4=0{,}1$ (le probabilità devono sommare $1$).

(1) Entropia ed efficienza

$$H(a)=0{,}2\log_2\frac1{0{,}2}+0{,}3\log_2\frac1{0{,}3}+0{,}4\log_2\frac1{0{,}4}+0{,}1\log_2\frac1{0{,}1}=0{,}464+0{,}521+0{,}529+0{,}332=1{,}846\ \text{bit}.$$ L'alfabeto ha $M=4$ simboli, quindi il massimo è $\log_24=2$ bit (simboli equiprobabili) e l'efficienza è $$\eta=\frac{H(a)}{\log_2M}=\frac{1{,}846}2=0{,}923.$$

(2) Trasformazione $b=2a-1$

La trasformazione è biunivoca (a ogni $a$ corrisponde un solo $b$ e viceversa): $a\in\{-2,-1,1,2\}\mapsto b=2a-1\in\{-5,-3,1,3\}$. L'alfabeto è $\mathcal B=\{-5,-3,1,3\}$ e le probabilità restano $0{,}2,\ 0{,}3,\ 0{,}4,\ 0{,}1$ (rispettivamente per $-5,-3,1,3$). L'entropia dipende solo dalle probabilità, non dai valori dei simboli: $$H(b)=H(a)=1{,}846\ \text{bit}.$$

(3) Trasformazione $c=a^2+1$

La trasformazione non è biunivoca: $a=\pm1$ danno $c=2$ e $a=\pm2$ danno $c=5$. L'alfabeto è $\mathcal C=\{2,5\}$ con probabilità $$p(c=2)=p(a=-1)+p(a=1)=0{,}3+0{,}4=0{,}7,\qquad p(c=5)=p(a=-2)+p(a=2)=0{,}2+0{,}1=0{,}3.$$ $$H(c)=0{,}7\log_2\frac1{0{,}7}+0{,}3\log_2\frac1{0{,}3}=0{,}360+0{,}521=0{,}881\ \text{bit}.$$ Fondere simboli riduce l'entropia ($H(c)<H(a)$): si perde informazione (da $c$ non si risale ad $a$).

(4) Codifica per un canale a $1$ kbit/s

La sorgente emette un simbolo ogni $T=1$ ms, cioè $F_s=1000$ simboli/s, e il rate di informazione è $$R=F_sH(a)=1000\cdot1{,}846=1846\ \text{bit/s}>1000\ \text{bit/s}.$$ Per il teorema di Shannon (Codifica di sorgente - codici a prefisso e teorema di ShannonLa codifica di sorgente riduce il numero di bit mappando le parole della sorgente in parole di lunghezza variabile (più corte per le più probabili), senza perdere informazione. Il codice deve essere decodificabile; i codici a prefisso (nessuna parola è prefisso di un'altra) lo sono. Kraft-McMillan: se il codice è decodificabile $\sum M_y^{-L(b)}\le1$. Teorema di Shannon: $L_y\ge\frac{H(x)}{\log_2M_y}$ e esiste un codice a prefisso con $L_y\le\frac{H(x)}{\log_2M_y}+1$; l'efficienza è $\eta=\frac{H(x)}{L_y\log_2M_y}$.Codifica di sorgente - codici a prefisso e teorema di Shannon →) qualunque codice decodificabile ha una lunghezza media $L_y\ge H(a)=1{,}846$ bit per simbolo, cioè richiede almeno $1846$ bit/s: non è possibile trasmettere l'informazione su un canale binario da $1$ kbit/s, qualunque codice si usi (neppure quello di Huffman, che qui ha lunghezze $1,2,3,3$ per $p=0{,}4,0{,}3,0{,}2,0{,}1$ e $L_y=0{,}4+0{,}6+0{,}6+0{,}3=1{,}9$ bit, quindi $1900$ bit/s). Servirebbe un canale di almeno $1{,}85$ kbit/s.

(Verificato con Python: $H(a)=1{,}8464$ bit, $H(c)=0{,}8813$ bit, Huffman $L_y=1{,}9$.)

Errori comuni

• Credere che $b=2a-1$ cambi l'entropia: una trasformazione biunivoca la conserva (dipende solo dalle probabilità).
• Dimenticare di sommare le probabilità dei simboli che si fondono in $c=a^2+1$ ($0{,}3+0{,}4$ e $0{,}2+0{,}1$).
• Rispondere "sì, con una buona codifica": nessun codice scende sotto l'entropia ($1{,}846$ bit/simbolo, cioè $1{,}846$ kbit/s).
• Calcolare l'efficienza con $\log_2M$ senza controllare il numero di simboli ($M=4$, quindi $2$ bit).