Codici di Shannon, Huffman ed Elias e codifica aritmetica

Il teorema di Shannon (Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza mediaLa codifica di sorgente senza perdite associa a ogni parola emessa dalla sorgente una parola di codice binaria (o $M_y$-aria) di lunghezza variabile, in modo invertibile; la qualità si misura con la lunghezza media $L_y=\sum p_{\underline x}(\underline a),l(\underline a)$. In un codice a prefisso nessuna parola è l'inizio di un'altra, quindi la decodifica è istantanea. Kraft-McMillan: ogni codice decodificabile ha $\sum M_y^{-l_i}\le1$, e se interi $l_i$ la soddisfano esiste un codice a prefisso con quelle lunghezze. Shannon: $\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1$ per il codice a prefisso ottimo, con $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze di $\frac1{M_y}$.Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media →) dice che esiste un codice a prefisso con lunghezza media tra $\frac{H}{\log_2M_y}$ e $\frac{H}{\log_2M_y}+1$. In questa nota si costruiscono tre codici concreti: Shannon, il codice ottimo di Huffman, e Elias (da cui la codifica aritmetica).

Versione per Ing. Elettronica: 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 →. Versione per Ing. delle Telecomunicazioni: 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 →. Entropia: Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimoL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit (zero per l'evento certo, additiva per eventi indipendenti). L'entropia di una variabile aleatoria discreta è l'informazione media, $H(x)=E[i_x(x)]=\sum_aP_x(a)\log_2\frac1{P_x(a)}$; vale $0\le H(x)\le\log_2M$ con $M$ cardinalità dell'alfabeto, e il massimo $\log_2M$ si raggiunge se e solo se i simboli sono equiprobabili (dimostrazione con la disuguaglianza di Jensen, perché il logaritmo è strettamente concavo).Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimo →.

Codice di Shannon(-Fano)

Definizione. Per una sorgente con parole $\underline a_i\in\mathcal D_x$ di probabilità $p_i$, il codice di Shannon ha lunghezze $$l_i=\left\lceil\log_{1/M_y}p_i\right\rceil=\left\lceil\log_{M_y}\frac1{p_i}\right\rceil,\qquad\text{per }M_y=2:\ l_i=\left\lceil-\log_2p_i\right\rceil=\left\lceil i(\underline a_i)\right\rceil.$$

La lunghezza è l'informazione dell'evento arrotondata per eccesso. Si è già dimostrato che soddisfa Kraft-McMillan (quindi esiste un codice a prefisso con queste lunghezze) e che $$H(\underline x)\le L_y<H(\underline x)+1\quad(M_y=2).$$ Le parole si ricavano dalle lunghezze: si ordinano per lunghezza crescente e si assegna a ciascuna le prime $l_i$ cifre binarie del numero $c_i=\sum_{j<i}2^{-l_j}$, oppure si disegna l'albero e si sceglie per ogni lunghezza un nodo non discendente di quelli già scelti. Sono possibili più assegnazioni equivalenti (scambiando $0$ e $1$ si ottiene un altro codice con le stesse lunghezze).

Se le probabilità sono potenze di $\frac12$ ($p_i=2^{-k_i}$), $l_i=k_i$ esatto e $L_y=\sum_ip_ik_i=H$: il codice di Shannon è ottimo.

Esempio. $p=\left(\frac12,\frac14,\frac18,\frac18\right)$, $M_y=2$: $l_1=\log_{1/2}\frac12=1$, $l_2=2$, $l_3=l_4=3$. Un codice a prefisso è $a_1\to0$, $a_2\to10$, $a_3\to110$, $a_4\to111$ (scambiando $0$ e $1$ in qualche nodo dell'albero si ottengono altri codici a prefisso con le stesse lunghezze). Lunghezza media $L_y=1\cdot\frac12+2\cdot\frac14+3\cdot\frac18+3\cdot\frac18=1{,}75$ bit $=H$.

Esempio con probabilità non diadiche. $p=(0{,}51;\ 0{,}27;\ 0{,}13;\ 0{,}09)$. Informazioni $0{,}971;\ 1{,}889;\ 2{,}943;\ 3{,}474$ bit, quindi $l=\lceil\cdot\rceil=1,2,3,4$ e $$L_y=0{,}51\cdot1+0{,}27\cdot2+0{,}13\cdot3+0{,}09\cdot4=0{,}51+0{,}54+0{,}39+0{,}36=1{,}80\ \text{bit}.$$ Kraft: $\frac12+\frac14+\frac18+\frac1{16}=\frac{15}{16}\le1$ ✓. Parole: $0,\ 10,\ 110,\ 1110$. Entropia $H=1{,}70$ bit, quindi $1{,}70\le1{,}80<2{,}70$ ✓, efficienza $\eta=\frac HL=0{,}945$.

Il codice di Shannon non è ottimo in generale (nell'esempio si vedrà Huffman con $1{,}71$ bit), perché arrotonda ogni simbolo separatamente.

Codici ottimi

Definizione. Un codice di sorgente è ottimo se ha la lunghezza media minima tra i codici a prefisso per quella sorgente.

Due proprietà di un codice a prefisso ottimo guidano la costruzione.

Teorema 1. In un codice a prefisso ottimo le parole di probabilità più bassa hanno lunghezza maggiore o uguale: se $p(x_1)<p(x_2)$ allora $l(y_1)\ge l(y_2)$.

Dimostrazione (per assurdo). Se fosse $p(x_1)<p(x_2)$ e $l(y_1)<l(y_2)$ in un codice ottimo, si scambiano le parole: $x_1\to y_2$, $x_2\to y_1$. Il nuovo codice è ancora a prefisso e la variazione della lunghezza media è $$\Delta L=p(x_1)\left[l(y_2)-l(y_1)\right]+p(x_2)\left[l(y_1)-l(y_2)\right]=\left[p(x_1)-p(x_2)\right]\left[l(y_2)-l(y_1)\right]<0,$$ perché il primo fattore è negativo e il secondo positivo: la lunghezza media scende, e il codice di partenza non era ottimo. Assurdo. $\blacksquare$

Teorema 2. Nel dizionario di un codice a prefisso ottimo ci sono almeno due parole di lunghezza massima $\underline b'$ e $\underline b''$ che differiscono solo nell'ultimo simbolo.

Dimostrazione (per assurdo). Si prende una parola $\underline b$ di lunghezza massima $l_{\max}$ e il suo "fratello", cioè la sequenza che differisce da $\underline b$ solo nell'ultimo simbolo (in un codice binario: $\dots0$ e $\dots1$ con lo stesso inizio). Se il fratello non fosse una parola di codice, nessuna parola del codice potrebbe stare sotto di lui (sarebbe più lunga di $l_{\max}$) né sopra di lui (sarebbe prefisso di $\underline b$ e il codice non sarebbe a prefisso). Allora si potrebbe accorciare $\underline b$ togliendo l'ultimo simbolo: il codice resterebbe a prefisso e la lunghezza media scenderebbe, contro l'ipotesi di ottimalità. Quindi il fratello è una parola di codice, e ha anch'esso lunghezza $l_{\max}$. $\blacksquare$

I due teoremi dicono che la coppia di simboli meno probabili può essere messa come "fratelli" in fondo all'albero: è il passo della procedura di Huffman.

Procedura di Huffman (codice binario)

Dati i simboli con probabilità $p_i$:

1. Ordinare le probabilità in ordine decrescente.
2. Unire i due simboli di probabilità più bassa in un unico simbolo "nodo" di probabilità la somma; ai due rami che partono dal nodo si assegnano le etichette $0$ e $1$ (una per ramo).
3. Ripetere da 1 sulla lista ridotta (un elemento in meno), finché resta un solo nodo (la radice, probabilità $1$).
4. Leggere le parole di codice sui rami, dalla radice a ciascuna foglia.

Il codice dipende dalle scelte (quale ramo è $0$, come si ordinano probabilità uguali) ma la lunghezza media è sempre la stessa, ed è la minima. Controllo utile: $L_y$ è anche la somma delle probabilità dei nodi interni (compresa la radice $=1$), perché ogni passaggio dall'albero aggiunge $1$ bit a tutte le parole sotto quel nodo.

Esempio 1 ($4$ simboli). $p=(0{,}4;\ 0{,}3;\ 0{,}2;\ 0{,}1)$ per $a_4,a_3,a_2,a_1$ (il simbolo $a_i$ ha $p=0{,}1\,i$).

• Passo 1: si uniscono $0{,}2$ e $0{,}1$ in un nodo da $0{,}3$.
• Passo 2: ora ci sono $0{,}4;\ 0{,}3;\ 0{,}3$; si uniscono i due $0{,}3$ in un nodo da $0{,}6$.
• Passo 3: si uniscono $0{,}4$ e $0{,}6$ nella radice. Con $0$ al ramo di probabilità maggiore a ogni unione: $a_4\to0$, $a_3\to10$, $a_2\to110$, $a_1\to111$. Lunghezza media $L_y=0{,}4\cdot1+0{,}3\cdot2+0{,}2\cdot3+0{,}1\cdot3=1{,}9$ bit; controllo con i nodi: $0{,}3+0{,}6+1=1{,}9$ ✓. L'entropia è $H=1{,}846$ bit, quindi $\eta=\frac{1{,}846}{1{,}9}=0{,}972$, contro il codice a lunghezza fissa con $2$ bit ($\eta=\frac{1{,}846}2=0{,}923$).

Esempio 2 ($5$ simboli). $p=(0{,}12;\ 0{,}22;\ 0{,}17;\ 0{,}11;\ 0{,}38)$ per $a_1,\dots,a_5$. Ordinati: $0{,}38\,(a_5);\ 0{,}22\,(a_2);\ 0{,}17\,(a_3);\ 0{,}12\,(a_1);\ 0{,}11\,(a_4)$.

1. Si uniscono i due più bassi $0{,}12$ e $0{,}11$: nodo $0{,}23$.
2. Lista $0{,}38;\ 0{,}23;\ 0{,}22;\ 0{,}17$: si uniscono $0{,}22$ e $0{,}17$: nodo $0{,}39$.
3. Lista $0{,}39;\ 0{,}38;\ 0{,}23$: i due più bassi sono $0{,}38$ e $0{,}23$: nodo $0{,}61$.
4. Rimangono $0{,}39$ e $0{,}61$: radice. Un codice risultante: $a_5\to00$, $a_2\to10$, $a_3\to11$, $a_1\to011$, $a_4\to010$ (lunghezze $2,2,2,3,3$ per $a_5,a_2,a_3,a_1,a_4$). $$L_y=0{,}12\cdot3+0{,}22\cdot2+0{,}17\cdot2+0{,}11\cdot3+0{,}38\cdot2=0{,}36+0{,}44+0{,}34+0{,}33+0{,}76=2{,}23\ \text{bit}.$$ Controllo con i nodi: $0{,}23+0{,}39+0{,}61+1=2{,}23$ ✓. L'entropia è $H=2{,}163$ bit ($2{,}163\le2{,}23<3{,}163$ ✓). Con il codice di Shannon le lunghezze sarebbero $4,3,3,4,2$ e $L_y=2{,}85$ bit: peggiore.

Esempio 3 (sorgente con $0{,}51;\ 0{,}27;\ 0{,}13;\ 0{,}09$). Si uniscono $0{,}13$ e $0{,}09$ (nodo $0{,}22$), poi $0{,}22$ e $0{,}27$ (nodo $0{,}49$), poi $0{,}49$ e $0{,}51$. Codice: $a_1\to0$, $a_2\to10$, $a_3\to110$, $a_4\to111$ (lunghezze $1,2,3,3$). $L_y=0{,}51+0{,}54+0{,}39+0{,}27=1{,}71$ bit; nodi: $0{,}22+0{,}49+1=1{,}71$ ✓. Rispetto al codice di Shannon ($1{,}80$ bit) l'ultimo simbolo perde un bit: $a_4$ ha $3$ bit anziché $4$.

Ottimalità. Per i teoremi precedenti il codice ottimo ha i due simboli meno probabili come fratelli di lunghezza massima, e il problema si riduce a un codice con un simbolo in meno e probabilità $p_a+p_b$ (il nodo unito). Ripetendo, si ottiene che la procedura di Huffman produce un codice ottimo. Per alfabeti $M_y$-ari si uniscono a ogni passo gli $M_y$ nodi meno probabili (aggiungendo all'inizio simboli fittizi di probabilità zero, in modo che il numero di simboli sia $1\bmod(M_y-1)$).

Codice di Elias e codifica aritmetica

Il codice di Elias non richiede di ordinare né di costruire un albero: usa la retta reale.

Costruzione. Si fissa un ordine dei simboli $a_1,\dots,a_N$ (per esempio quello naturale). Si divide l'intervallo $[0,1)$ in $N$ sottointervalli contigui di ampiezze $p_1,\dots,p_N$. Per ogni simbolo $a_i$ si prende il punto medio $m_i$ del suo intervallo. La parola di codice è formata dalle prime $l_i$ cifre dopo la virgola dello sviluppo binario di $m_i$, con $$\boxed{l_i=\left\lceil-\log_2p_i\right\rceil+1.}$$

Perché funziona. Scrivere $m_i$ con $l_i$ cifre significa troncarlo, e il troncamento è $\le m_i$ e dista da $m_i$ meno di $2^{-l_i}\le\frac{p_i}2$ (infatti $2^{-l_i}=2^{-\lceil-\log_2p_i\rceil-1}\le\frac{p_i}2$). Il punto troncato e il segmento $[\text{troncato},\text{troncato}+2^{-l_i})$ stanno quindi dentro l'intervallo di $a_i$ (che si estende per $\frac{p_i}2$ a destra e a sinistra di $m_i$). Intervalli diversi sono disgiunti, quindi nessuna parola è prefisso di un'altra: il codice è a prefisso.

Esempio ($m=0{,}01$ in binario $\to\frac14$). Un numero binario $0{,}b_1b_2b_3\dots$ vale $\sum b_k2^{-k}$: $0{,}01$ è $\frac14$, $0{,}101=\frac12+\frac18=0{,}625$.

Esempio ($p=0{,}51;\ 0{,}27;\ 0{,}13;\ 0{,}09$, ordine naturale).

Conversione di $0{,}255$: $0{,}255\cdot2=0{,}51\to0$; $0{,}51\cdot2=1{,}02\to1$ (resta $0{,}02$); $0{,}02\cdot2=0{,}04\to0$; $\dots$ quindi $0{,}0100\dots$ e le prime due cifre sono $01$. Il codice è a prefisso ($01,\ 101,\ 1101,\ 11110$).

Lunghezza media $L_y=0{,}51\cdot2+0{,}27\cdot3+0{,}13\cdot4+0{,}09\cdot5=1{,}02+0{,}81+0{,}52+0{,}45=2{,}80$ bit $=1{,}80+1$ (una cifra in più del codice di Shannon).

Prestazioni. $L_y=\sum_ip_i\left[\lceil-\log_2p_i\rceil+1\right]\ge\sum_ip_i\left[-\log_2p_i+1\right]=H+1$ e $L_y<H+2$: il codice è subottimo di almeno $1$ bit per parola rispetto al limite di Shannon. Ha però un vantaggio: poiché il codice dipende solo dall'intervallo $[0,1)$ e dalle probabilità, si presta a un meccanismo adattativo. Nella codifica aritmetica il codificatore e il decodificatore tengono entrambi una stima delle probabilità $P(a_i)$ e la aggiornano a ogni simbolo; l'intervallo di partenza viene suddiviso con le probabilità correnti, così non serve conoscere in anticipo la statistica della sorgente né trasmettere un dizionario.

Confronto sull'esempio $0{,}51;\ 0{,}27;\ 0{,}13;\ 0{,}09$

con $H=1{,}70$ bit: i limiti di Shannon sono $1{,}70\le L_y<2{,}70$ ($L_y=2{,}80$ per Elias supera $H+1$ ma non $H+2$). Il codice ottimo è il migliore, Shannon è a meno di $0{,}1$ bit, Elias spreca $1$ bit.

Dalla sorgente al modulatore: periodo di simbolo

Un esercizio tipico concatena i blocchi. La sorgente emette un simbolo ogni $T_s=1$ ms con le probabilità sopra.

1. Codificatore di sorgente (Huffman, $L_y=1{,}71$ bit per simbolo): escono $\frac{L_y}{T_s}=1{,}71$ kbit/s, quindi un bit ogni $T_b=\frac1{1710}=0{,}585$ ms.
2. Codificatore di canale con rate $R_c=\frac34$ (per esempio $k=30$, $n=40$): ogni $3$ bit di informazione ne escono $4$, quindi il bit-rate sul canale è $\frac{1710}{3/4}=2280$ bit/s e il tempo di bit dopo il codice è $T_c=\frac34T_b=0{,}4386$ ms.
3. Modulatore 16-QAM ($\log_216=4$ bit per simbolo): $T=4T_c=1{,}754$ ms (570 simboli/s).

(Con arrotondamenti intermedi sui tempi di bit si trova $1{,}74$ ms; il valore senza arrotondamenti è $1{,}754$ ms.) In formula, per ogni simbolo della sorgente escono $L_y$ bit dal codificatore di sorgente, $\frac{L_y}{R_c}$ bit dal codificatore di canale e $\frac{L_y}{R_c\log_2M}$ simboli dal modulatore (Modulazione digitale - trasmettitore, bit map e canale AWGNIl trasmettitore digitale ha due blocchi: la bit map raggruppa $\log_2M$ bit in un simbolo $a_m\in{1,\dots,M}$ (periodo $T=T_b\log_2M$) e il modulatore associa a ogni simbolo una forma d'onda $s_{a_m}(t)$, così $s_{Tx}(t)=\sum_ms_{a_m}(t-mT)$; l'insieme delle $M$ forme d'onda è la segnalazione. Il canale ideale lascia il segnale com'è, il canale AWGN lo scala di $A$ e somma il rumore bianco gaussiano $w(t)$, il canale multipath somma echi ritardati: i suoi due effetti sono la deformazione delle forme d'onda ($s'm$) e l'interferenza intersimbolica. Il ricevitore ha un demodulatore digitale che decide $\hat a_m$ e una bit demap.Modulazione digitale - trasmettitore, bit map e canale AWGN →; per il rate del codice Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetricoPer proteggere i bit dagli errori si può chiedere la ritrasmissione (ARQ, serve il canale di ritorno), aggiungere ridondanza per correggere (FEC) o unire le due cose (HARQ). Un codice a blocco $(n,k)$ trasforma $k$ bit in una parola di $n>k$ bit scelta tra $2^k$ parole su $2^n$ sequenze; modulatore, canale e demodulatore equivalgono a un canale binario simmetrico senza memoria con probabilità d'errore sul bit $P{bit}$. Per $P_{bit}<\frac12$ il decodificatore ML sceglie la parola a minima distanza di Hamming; con distanza minima $d_{min}$ si correggono sempre $t=\lfloor\frac{d_{min}-1}{2}\rfloor$ errori e se ne rivelano sempre $d_{min}-1$. Il tasso è $R=\frac kn$ e la probabilità d'errore di parola è limitata da $P(\text{più di }t\text{ errori})$. L'ARQ ha efficienza $S_{SW}$, $S_{GBN}$, $S_{SR}$ in funzione di $t_P$, $t_A$, $\tau_P$ e $p$.Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetrico →), quindi $$T=\frac{T_s\,R_c\log_2M}{L_y}=\frac{1\ \text{ms}\cdot0{,}75\cdot4}{1{,}71}=1{,}754\ \text{ms}.$$

Errori comuni

• Costruire Huffman unendo i nodi più probabili, o non riordinare dopo ogni unione.
• Scambiare le etichette $0/1$ in modo incoerente: va bene qualunque scelta, ma una per ramo, e bisogna leggere dalla radice alla foglia.
• Dimenticare che $L_y$ dipende dalle probabilità dei simboli, non dal numero di rami: due codici con le stesse lunghezze ordinate hanno la stessa $L_y$.
• Dire che il codice di Shannon è ottimo: solo con probabilità potenze di $\frac12$.
• Prendere per Elias $l_i=\lceil-\log_2p_i\rceil$ senza il $+1$ (è la lunghezza di Shannon).
• Troncare il punto medio $m_i$ in modo sbagliato nella conversione in binario (moltiplicare per $2$ e prendere la parte intera a ogni passo).
• Nell'esercizio di catena, invertire il rapporto $T_c=R_cT_b$: il codice di canale aggiunge bit, quindi i bit sul canale sono più frequenti ($T_c<T_b$).

Domande d'esame

1. Si costruisca il codice di Huffman per $p=(0{,}51;\ 0{,}27;\ 0{,}13;\ 0{,}09)$ e se ne calcoli la lunghezza media. Unioni $0{,}22$, $0{,}49$, radice; parole $0,10,110,111$; $L_y=1{,}71$ bit.
2. Per la stessa sorgente si calcolino le lunghezze medie dei codici di Shannon e di Elias e i limiti di Shannon. Shannon $1,2,3,4\Rightarrow1{,}80$ bit; Elias $+1$ bit $\Rightarrow2{,}80$ bit; limiti $H=1{,}70\le L_y<2{,}70$.
3. Si dimostri che in un codice a prefisso ottimo le parole meno probabili non sono più corte. Scambio delle parole: $\Delta L=[p(x_1)-p(x_2)][l(y_2)-l(y_1)]<0$ se $p(x_1)<p(x_2)$ e $l(y_1)<l(y_2)$: assurdo con l'ottimalità.

Esercizi svolti

• Esercizio - sensori di temperatura, codice di Huffman, porta seriale e informazione mutua (esercizi del corso, cap. 5, es. 56): Huffman per quattro valori e numero di sensori su una porta seriale.
• Esercizio - Huffman, codice di Shannon, funzione deterministica di una sorgente e informazione mutua di un canale (secondo compitino del 9 gennaio 2026, es. 196): Huffman con pareggio, codice di Shannon e limite per una sorgente accorpata.
• Esercizio - entropia condizionata, Huffman per due sorgenti e informazione mutua (compito del 25 giugno 2024, es. 178): Huffman per due densità e per le coppie $(x,y)$.
• Esercizio - due sorgenti indipendenti, codice di Shannon, Huffman e informazione mutua con un prodotto (compito del 24 gennaio 2025, es. 189): Huffman e Shannon per $Y$ a quattro simboli.
• Esercizio - codice di Elias, Huffman sulla coppia di sorgenti e informazione mutua (compito del 22 gennaio 2019, es. 92): codice di Elias per tre simboli e Huffman per le coppie.
• Esercizio - canale binario non simmetrico, informazione mutua, Huffman ed Elias sulle coppie e canale a cancellazione (compito del 10 febbraio 2021, es. 123): Huffman ed Elias per le coppie di uscite binarie.
• Esercizio - Huffman, Elias ed entropia con probabilità dipendenti dalla matricola (secondo compitino dell'8 gennaio 2021, es. 118): Huffman, Shannon ed Elias con probabilità dipendenti da un parametro.
• Esercizio - canale binario con rumore aleatorio, capacità e Huffman sulle triplette (secondo compitino dell'11 gennaio 2019, es. 90): Huffman per otto triplette e confronto con l'entropia.
• Esercizio - Kraft-McMillan, Huffman, due canali binari alternati e codice di Hamming (15,11) (compito del 13 febbraio 2026, es. 201): Huffman a otto livelli con probabilità in trentaduesimi.
• Esercizio - Kraft-McMillan, Huffman, Hamming (7,4) e attenuazione massima con 16-QAM (secondo compitino del 12 gennaio 2024, es. 170): Huffman a otto livelli con $K=\frac1{20}$.