Entropia e codifica di Huffman

Testo

Una sorgente emette le quattro lettere $a,b,c,d$ con probabilità $1/2,\ 1/4,\ 1/8,\ 1/8$. Calcolare l’entropia e confrontarla con la codifica $a=0,\ b=10,\ c=110,\ d=111$: la lunghezza media è $1{,}75$ bit; coincide con $H$ (codice ottimale di Huffman).

Soluzione

Entropia: $H = -\tfrac12\log_2\tfrac12 - \tfrac14\log_2\tfrac14 - \tfrac18\log_2\tfrac18 - \tfrac18\log_2\tfrac18.$ Con $\log_2\tfrac12=-1$, $\log_2\tfrac14=-2$, $\log_2\tfrac18=-3$: $H = \tfrac12\cdot 1 + \tfrac14\cdot 2 + \tfrac18\cdot 3 + \tfrac18\cdot 3 = 0{,}5 + 0{,}5 + 0{,}375 + 0{,}375 = \boxed{1{,}75 \text{ bit}}.$ Lunghezza media del codice (bit per lettera $\times$ probabilità): $\bar\ell = \tfrac12\cdot 1 + \tfrac14\cdot 2 + \tfrac18\cdot 3 + \tfrac18\cdot 3 = 1{,}75 \text{ bit}.$ I due valori coincidono: $\bar\ell = H$. Quando le probabilità sono potenze di $1/2$, il codice di Huffman raggiunge esattamente il limite di Shannon — è impossibile comprimere di più.

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Entropia
Competenze: Calcolare
Persone: Shannon
Tipo di esercizio: Calcolo espressioni