Esercizio 2codice di Huffman a 8 livelli e verifica di Kraft-McMillan (tema d'esame gennaio 2025)

---

Teoria usata: 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 →, 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 →, 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 →.

(4) Codice ottimo: Huffman

Le probabilità date sommano $0{,}25\cdot3+0{,}1+0{,}05\cdot2+0{,}04=0{,}99$: l'ottava (non scritta nel testo) è $p_8=1-0{,}99=0{,}01$.

Costruzione. Si uniscono sempre i due nodi meno probabili (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 →):

Etichettando con $0$ il ramo superiore e $1$ l'inferiore ad ogni unione, una possibile assegnazione è

Lunghezza media (somma pesata, e controllo con la somma dei nodi interni): $$L_y=3\cdot0{,}25\cdot2+(0{,}10+0{,}05+0{,}05)\cdot4+(0{,}04+0{,}01)\cdot5=1{,}5+0{,}8+0{,}25=2{,}55\ \text{bit},$$ $$0{,}05+0{,}10+0{,}15+0{,}25+0{,}50+0{,}50+1=2{,}55\ \checkmark.$$ Entropia: $H=3\cdot0{,}25\log_2 4+0{,}1\log_2 10+2\cdot0{,}05\log_2 20+0{,}04\log_2 25+0{,}01\log_2 100=2{,}517$ bit. Efficienza $\eta=\frac{H}{L_y}=\frac{2{,}517}{2{,}55}=0{,}987$, contro $\eta=\frac{2{,}517}3=0{,}84$ della lunghezza fissa a $3$ bit; la lunghezza media rispetta $H\le L_y<H+1$ (Shannon). Altre scelte a parità di probabilità danno lunghezze diverse (per esempio $3$ bit anziché $4$ per qualche simbolo), ma sempre lo stesso $L_y=2{,}55$.

(5) Le lunghezze $2,2,3,3,3,3,4,4$

Si applica la disuguaglianza di Kraft-McMillan per un codice binario ($M_y=2$): un codice decodificabile con queste lunghezze richiede $$\sum_{i=1}^8\frac1{2^{\ell_i}}=2\cdot\frac14+4\cdot\frac18+2\cdot\frac1{16}=\frac12+\frac12+\frac18=\frac98=1{,}125>1.$$ La condizione non è soddisfatta, quindi non esiste nessun codice decodificabile (a maggior ragione a prefisso) con quelle lunghezze. Si vede anche sull'albero: le due parole da $2$ bit occupano $\frac12$ delle foglie possibili, le quattro da $3$ bit occupano l'altro $\frac12$, e non resta posto per le due da $4$ bit (che ne chiederebbero $\frac18$). Con queste lunghezze la lunghezza media sarebbe $2{,}55$ bit (assegnandole in ordine di probabilità), che non contraddice Shannon ($\ge H=2{,}517$): è solo Kraft a escluderlo.

(Verificato con Python: Huffman $[2,2,2,4,4,4,5,5]$, $L_y=2{,}55$, $H=2{,}5166$; Kraft $=1{,}125$.)

Errori comuni

• Dimenticare di ricavare $p_8=1-\sum p_i$ ($0{,}01$).
• Unire i nodi più probabili, o non riordinare dopo una fusione.
• Concludere che un codice con Kraft $\le1$ sia automaticamente decodificabile, o dire che con Kraft $>1$ si può "aggiustare": se la somma supera $1$ la risposta è netta, no.
• Calcolare $L_y$ con le parole del codice senza pesarle per $p_i$.