Codici di Shannon-Fano e di Huffman

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 →) dà solo i limiti $\frac{H}{\log_2M_y}\le L_y\le\frac{H}{\log_2M_y}+1$. Questi due algoritmi costruiscono codici a prefisso concreti.

Come deve essere un codice ottimo

Un codice è ottimo se ha la minima lunghezza media $L_y$ tra i codici decodificabili per la stessa sorgente. Due proprietà (codici binari):

• Proposizione 1. Se $\mathcal C$ è ottimo e $P(b_1)\le P(b_2)$, allora $L(b_1)\ge L(b_2)$. Dimostrazione per assurdo: se fosse $P(b_1)\le P(b_2)$ con $L(b_1)<L(b_2)$, scambiando le due parole la nuova lunghezza media è $L_y'=L_y-\left(P(b_1)-P(b_2)\right)\left(L(b_1)-L(b_2)\right)$, e il prodotto dei due fattori (entrambi $\le0$) è $\ge0$, quindi $L_y'\le L_y$: il codice non era ottimo se vale la disuguaglianza stretta.
• Proposizione 2. In un codice ottimo esistono due parole di lunghezza massima identiche tranne l'ultimo simbolo (se non fosse così, si potrebbe accorciare l'ultima parola togliendole l'ultimo bit).

Codifica di Shannon-Fano

Procedura top-downdall'alto verso il basso: si parte dalla radice dell'albero (dall'alto):

1. si ordinano i simboli $a_i$ per probabilità $P(a_i)$ decrescente;
2. si dividono in due sottoinsiemi (primi $k$ e restanti) con probabilità totali le più vicine possibile;
3. si ripete la divisione in ciascun sottoinsieme, fino ad avere un solo simbolo per gruppo;
4. a ogni ramo si associa 0 (gruppo di sinistra) o 1 (di destra); la parola di un simbolo è la sequenza di etichette dalla radice.

Esempio. $A=0{,}35,\ B=0{,}22,\ C=0{,}20,\ D=0{,}13,\ E=0{,}10$.

Parole: $A=00,\ B=01,\ C=10,\ D=110,\ E=111$. Lunghezza media $L_y=2(0{,}35+0{,}22+0{,}20)+3(0{,}13+0{,}10)=1{,}54+0{,}69=2{,}23$ bit.

La divisione "quasi uguale" non sempre è unica e l'algoritmo non garantisce l'ottimo (lo fa se le probabilità sono potenze di $\frac12$).

Codifica di Huffman

Procedura bottom-updal basso verso l'alto: si parte dalle foglie (dal basso):

1. si ordinano i simboli per probabilità decrescente;
2. si raggruppano i due simboli con probabilità minima in un nuovo nodo, con probabilità la somma;
3. si ripete (i nodi nuovi partecipano come simboli) finché resta un solo nodo (la radice);
4. si etichettano i due rami uscenti da ogni nodo con $0$ e $1$ e si leggono le parole dalla radice alle foglie.

È ottimo: ha la minima $L_y$ tra tutti i codici a prefisso e, per il teorema di Kraft-McMillan (ogni codice decodificabile ha lunghezze che ammettono anche un codice a prefisso), tra tutti i codici decodificabili.

Esempio (lo stesso di prima). Si uniscono $D+E$ ($0{,}13+0{,}10=0{,}23$), poi $B+C$ ($0{,}22+0{,}20=0{,}42$), poi $A+(DE)$ ($0{,}35+0{,}23=0{,}58$), infine $(BC)+(A\,DE)$ ($1$):

A 0,35 ─────────────────┐
D 0,13 ─┐               ├ 0,58 ─┐
E 0,10 ─┴ 0,23 ─────────┘       │
B 0,22 ─┐                       ├ 1
C 0,20 ─┴ 0,42 ─────────────────┘

Con $0$ al ramo di sopra e $1$ a quello di sotto in ogni unione una possibile scelta è $A=10,\ B=00,\ C=01,\ D=110,\ E=111$ (lo scambio degli 0/1 dà un altro codice equivalente).

Lunghezza media. Due modi equivalenti:

• $L_y=\sum P(b)L(b)=2(0{,}35+0{,}22+0{,}20)+3(0{,}13+0{,}10)=2{,}23$ bit;
• scorciatoia: $L_y$ è la somma delle probabilità dei nodi interni (le unioni): $0{,}23+0{,}42+0{,}58+1=2{,}23$ (ogni foglia contribuisce con la sua probabilità tante volte quanti sono i nodi che attraversa verso la radice, cioè la sua lunghezza).

Efficienza e rate. $H=2{,}19$ bit, quindi $\eta=\frac{2{,}19}{2{,}23}=0{,}98$. Senza codifica servono $\lceil\log_25\rceil=3$ bit per simbolo ($L_x=3$, $\eta=0{,}73$): con $F_s=100$ simboli/s il rate nominale scende da $300$ a $223$ bit/s, vicino al rate di informazione $F_sH=219$ bit/s.

Il codice di Huffman non è unico (le scelte a parità di probabilità danno alberi diversi e le etichette 0/1 si possono scambiare), ma $L_y$ è unica.

Esempio completo con otto simboli

Probabilità $0{,}25,\ 0{,}25,\ 0{,}25,\ 0{,}10,\ 0{,}05,\ 0{,}05,\ 0{,}04,\ 0{,}01$ (somma 1; l'ultima si ricava da $1-0{,}99$), tema d'esame gennaio 2025 (Esercizio 2 · codice di Huffman a 8 livelli e verifica di Kraft-McMillan (tema d'esame gennaio 2025)). Unioni successive:

1. $0{,}04+0{,}01=0{,}05$ (nodo $X$);
2. una coppia tra i tre da $0{,}05$ (per esempio $0{,}05+0{,}05=0{,}10$, nodo $Y$);
3. $X\,(0{,}05)+0{,}10\ (\text{simbolo})=0{,}15$ (nodo $Z$);
4. $Y\,(0{,}10)+Z\,(0{,}15)=0{,}25$ (nodo $W$);
5. i quattro nodi/simboli da $0{,}25$: due coppie ($0{,}50$ e $0{,}50$), poi la radice.

Lunghezze: tre simboli da $0{,}25$ a $2$ bit; quelli da $0{,}10$ e $0{,}05\,(\times2)$ a $4$ bit; quelli da $0{,}04$ e $0{,}01$ a $5$ bit. Somma dei nodi internii nodi ottenuti dalle fusioni, esclusi i simboli di partenza: $0{,}05+0{,}10+0{,}15+0{,}25+0{,}50+0{,}50+1=2{,}55$ bit. Con $H=2{,}517$ bit, $\eta=0{,}987$ (a lunghezza fissa 3 bit: $0{,}84$).

Codifica a lunghezza variabile e rate

Se $F_s$ è la frequenza dei simboli del quantizzatore, con Huffman si ha rate nominale $F_sL_y$ (bit/s) rispetto a $F_s\log_2L$ senza codifica. Un caso reale (quantizzatore a 8 livelli, probabilità $0{,}5,0{,}15,0{,}10,0{,}08,0{,}07,0{,}05,0{,}03,0{,}02$, tema d'esame febbraio 2026): $H=2{,}284$ bit, Huffman con lunghezze $1,3,3,4,4,4,5,5$ ha $L_y=2{,}30$ bit ($\eta=0{,}993$); a $F_s=8$ kHz il rate scende da $24$ a $18{,}4$ kbit/s, quasi il rate di informazione $18{,}27$ kbit/s.

Errori comuni

• Unire i due simboli più probabili invece dei due meno probabili.
• Dimenticare di rimettere in ordine i nodi nuovi con quelli rimasti prima di scegliere i due minimi.
• Calcolare $L_y$ senza pesare con le probabilità, o con la lunghezza di una singola parola.
• Pensare che il codice di Huffman sia unico, o che l'efficienzarapporto tra entropia e lunghezza media del codice possa superare 1.
• Confondere la lunghezza media (per parola) con il rate (per secondo): servono $F_s$ e il bit-rate.