Codifica di sorgente

La sorgente emette simboli con certe probabilità; la entropiaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua → dice quanti bit di informazione contengono in media. Se si trasmette ogni simbolo con $\lceil\log_2M\rceil$ bit (lunghezza fissa) se ne spendono di più, quando i simboli non sono equiprobabili. La codifica di sorgente (source coding) rappresenta la stessa informazione con meno bit.

1. Lo schema e le grandezze

Esistono due famiglie. La codifica lossy accetta una perdita di informazione (mp3, jpeg, mpeg), la lossless è invertibile (zip, rar): da quello che si trasmette si ricostruisce esattamente la sequenza di partenza. Il corso studia solo la seconda.

Definizione (codice di sorgente). Una sorgente emette parole $\vec x$ di $N$ simboli (dizionario di ingresso $\mathcal D_x$, entropia $H(\vec x)$). Una mappa $\mu_s:\mathcal D_x\to\mathcal C$ associa a ogni parola una parola di codice $\vec b$ scritta con un alfabeto di $M$ simboli (alfabeto binario: $M=2$), e deve essere invertibile (diversamente si perderebbe informazione). $L(\vec b)$ è la lunghezza di $\vec b$; la lunghezza media è $$\tilde L=E\left[L(\vec b)\right]=\sum_{\vec b\in\mathcal C}P(\vec b)\,L(\vec b),$$ cioè il valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso → della lunghezza, vista come variabile aleatoria che dipende dalla parola emessa; e l'efficienza del codice è $\eta=\frac{H(\vec x)}{\tilde L\,\log_2M}$ (per un codice binario $\eta=\frac{H}{\tilde L}$).

Senza codifica servono $\lceil\log_2\lvert\mathcal D_x\rvert\rceil$ bit per parola. L'idea è: parole frequenti $\to$ parole corte; parole rare $\to$ parole lunghe, in modo che $\tilde L$ scenda. Se la sorgente emette $F_s$ simboli/s il bit-rate nominale diventa $F_s\tilde L/N$ (confrontalo con il rate di informazione $F_sH_s$, Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua →).

Esempio. $M=8$ simboli equiprobabili: $H=3$ bit e a lunghezza fissa 3 bit: la codifica non può migliorare ($\eta=1$). Se invece le probabilità sono $\left(\frac12,\frac14,\frac18,\frac18\right)$, la lunghezza fissa usa 2 bit e $H=1{,}75$: c'è margine per risparmiare $12{,}5\%$.

2. Decodificabilità e codici a prefisso

Definizione (decodificabile, a prefisso). Un codice è univocamente decodificabile se due sequenze diverse di parole di codice non danno mai la stessa stringa di bit. Una parola $\vec b$ è prefisso di $\vec b'$ se $L(\vec b)<L(\vec b')$ e $\vec b$ coincide con i primi $L(\vec b)$ simboli di $\vec b'$. Un codice è a prefisso se nessuna sua parola è prefisso di un'altra.

Il problema nasce quando le lunghezze sono diverse: una sequenza di bit ricevuta potrebbe essere divisa in più modi in parole di codice.

Esempio. Con $A\to0,\ B\to1,\ C\to01,\ D\to10$ la stringa $0101001101101$ è ambigua ($0\,1\,0\,1\dots$ = $ABAB\dots$ ma anche $01\,01\dots=CC\dots$): il codice non è decodificabile. Con $A\to0,\ B\to10,\ C\to110,\ D\to111$ (a prefisso) la stringa $0\,10\,110\,111\,0$ si legge in un solo modo.

Proposizione. Un codice a prefisso è decodificabile, e in modo istantaneo. Dimostrazione: si legge la stringa bit per bit; appena i bit letti coincidono con una parola di codice, quella è la parola emessa, perché nessuna parola più lunga può iniziare con essa (se no la prima sarebbe prefisso); si riparte da capo. Non vale il contrario: $\{0,01\}$ è decodificabile (dopo uno $0$ si guarda il bit successivo) ma $0$ è prefisso di $01$.

I codici a prefisso si disegnano con un albero binario: ogni parola è una foglia (un nodo senza figli), il cammino dalla radice la scrive (0 a sinistra, 1 a destra) e nessuna parola sta su un nodo interno.

3. Disuguaglianza di Kraft-McMillan

Teorema (Kraft-McMillan). Sia $\mathcal C$ un codice con alfabeto di $M$ simboli e parole di lunghezze $l_1,\dots,l_K$.

1. Se $\mathcal C$ è decodificabile, allora $\displaystyle\sum_{i=1}^K\frac1{M^{l_i}}\le1$ (equivalentemente $E\left[\frac1{M^{L(\vec b)}P(\vec b)}\right]\le1$).
2. Viceversa, se $l_1,\dots,l_K$ sono interi con $\sum_iM^{-l_i}\le1$ esiste un codice a prefisso con alfabeto $M$ e quelle lunghezze.

Esempio. Le lunghezze $1,2,3,3$ danno $\frac12+\frac14+\frac18+\frac18=1\le1$: esiste un codice a prefisso binario (quello dell'esempio sopra con $B\to10$, $C\to110$, $D\to111$). Le lunghezze $2,2,3,3,3,3,4,4$ (otto parole) danno $2\cdot\frac14+4\cdot\frac18+2\cdot\frac1{16}=\frac12+\frac12+\frac18=\frac98>1$: nessun codice decodificabile ha queste lunghezze.

Dimostrazione del punto 2 (costruzione). Si ordinano le lunghezze in modo crescente e si assegnano le parole una dopo l'altra, sull'albero, scegliendo ogni volta il primo nodo libero a quella profondità che non sia discendente di una parola già scelta. Una parola di lunghezza $l$ "occupa" una frazione $M^{-l}$ di tutte le foglie (a una profondità fissata); la condizione $\sum M^{-l_i}\le1$ garantisce che le foglie occupate non superino mai quelle disponibili. Quindi il nodo libero esiste sempre. $\square$

Dimostrazione del punto 1. Si elevi la somma a una potenza $n$: $$\left(\sum_iM^{-l_i}\right)^n=\sum_{i_1,\dots,i_n}M^{-(l_{i_1}+\dots+l_{i_n})}=\sum_{k=n}^{n\,l_{\max}}N_k\,M^{-k},$$ dove $N_k$ è il numero di sequenze di $n$ parole di codice la cui lunghezza totale è $k$. Se il codice è decodificabile, sequenze diverse danno stringhe diverse di $k$ simboli, quindi $N_k\le M^k$ (tanti quante le stringhe possibili). Allora $\left(\sum_iM^{-l_i}\right)^n\le\sum_{k=n}^{n\,l_{\max}}1\le n\,l_{\max}$. Se la somma $S$ fosse $>1$, $S^n$ crescerebbe esponenzialmente in $n$ mentre $n\,l_{\max}$ cresce solo linearmente: contraddizione per $n$ grande. Quindi $S\le1$. $\square$

Osservazioni. (i) Il punto 1 è una condizione necessaria, non sufficiente: $\{0,01,10\}$ ha somma $\frac12+\frac14+\frac14=1$ ma $010$ è ambiguo ($0\,10$ oppure $01\,0$). (ii) Il punto 2 dice che non si perde nulla limitandosi ai codici a prefisso: se esiste un codice decodificabile con certe lunghezze, ne esiste uno a prefisso con le stesse. (iii) Kraft serve per escludere codici (somma $>1$) o per costruirli: ad esempio $A\to0,\ B\to00,\ C\to01,\ D\to111,\ E\to1111$ ha somma $\frac12+\frac14+\frac14+\frac18+\frac1{16}=\frac{19}{16}>1$, quindi non è decodificabile ($000$ potrebbe essere $AAA$, $AB$, $BA$).

4. Teorema di Shannon sulla codifica di sorgente

Teorema (Shannon). Sia $\mathcal C$ un codice con alfabeto di $M$ simboli per parole $\vec x$ di entropia $H(\vec x)$.

1. Se $\mathcal C$ è decodificabile, $\displaystyle\tilde L\ge\frac{H(\vec x)}{\log_2M}$.
2. Esiste un codice a prefisso con $\displaystyle\tilde L<\frac{H(\vec x)}{\log_2M}+1$. Corollario ($M=2$): $\tilde L=H(\vec x)$ se e solo se tutte le probabilità sono potenze di $\frac12$.

Dimostrazione del punto 1. Per Kraft $E\left[\frac1{M^{L}P}\right]\le1$. Si applica il logaritmo in base $\frac1M$ (funzione decrescente, quindi inverte la disuguaglianza) e Jensen (log in base $\frac1M$ è convessa, quindi $\log E[\cdot]\le E[\log\cdot]$ in questo verso, Segnali, potenza e decibelRichiami che servono in tutto il corso. Unità SI e prefissi (kilo = $10^3$, bit e non byte); decibel $[x]{dB}=10\log{10}x$ per le potenze e $20\log_{10}$ per le ampiezze (prodotti = somme); banda di un segnale (primo zero, a $\alpha$ dB, di energia) e banda pratica; energia, potenza e teorema di Parseval; processi aleatori: media, potenza, autocorrelazione, stazionarietà (WSS), ergodicità, densità spettrale di potenza $\mathcal P_x(f)$ e filtraggio $\mathcal P_y=\lvert G\rvert^2\mathcal P_x$.Segnali, potenza e decibel → §7): $$0\le\log_{1/M}E\left[\frac1{M^{L}P}\right]\le E\left[\log_{1/M}\frac1{M^{L}P}\right]=E\left[L\right]-E\left[\log_M\frac1P\right]=\tilde L-\frac{H(\vec x)}{\log_2M}.$$ (passaggi: $\log_{1/M}\frac1{M^LP}=\log_M(M^LP)=L+\log_MP=L-\log_M\frac1P$ e $\log_M\frac1P=\frac{\log_2(1/P)}{\log_2M}$, per il cambio di base e le proprietà dei logaritmi, Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →; la media si porta dentro e fuori dalla somma per la linearità del Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →.) $\square$

Vedi anche la stessa teoria nel corso di Ing. Elettronica: 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 → e 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 →.

Dimostrazione del punto 2 (lunghezze di Shannon). Si pone $l_i=\left\lceil\log_M\frac1{P_i}\right\rceil$. Allora $l_i\ge\log_M\frac1{P_i}$, cioè $M^{-l_i}\le P_i$, quindi $\sum_iM^{-l_i}\le\sum_iP_i=1$: vale Kraft e per il punto 2 di Kraft-McMillan esiste un codice a prefisso con queste lunghezze. Inoltre $l_i<\log_M\frac1{P_i}+1$ e mediando $\tilde L<\frac{H}{\log_2M}+1$. $\square$

Corollario. Con $M=2$ il limite inferiore è raggiunto esattamente quando $\log_2\frac1{P_i}$ è intero per ogni $i$, cioè $P_i=2^{-l_i}$: allora le lunghezze di Shannon sono $\log_2\frac1{P_i}$ senza arrotondamento e $\tilde L=H$.

Esempio. Probabilità $\left(\frac12,\frac14,\frac18,\frac18\right)$ e codice $A\to0$, $B\to10$, $C\to110$, $D\to111$: $H=\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+\frac18\cdot3=\frac74=1{,}75$ e $\tilde L=\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+\frac18\cdot3=1{,}75$: $\eta=1$.

Il teorema dà solo limiti: non dice come trovare il codice migliore. Servono algoritmi.

5. Codifica di Shannon

Definizione (codifica di Shannon). Le lunghezze sono $l_i=\lceil\log_2\frac1{P_i}\rceil$ e le parole si assegnano scorrendo l'albero dalle lunghezze più corte alle più lunghe.

Esempio. $P=(0{,}38,\ 0{,}19,\ 0{,}17,\ 0{,}14,\ 0{,}12)$ per $A,\dots,E$. $\log_2\frac1P=1{,}40,\ 2{,}40,\ 2{,}56,\ 2{,}84,\ 3{,}06$, quindi $l=(2,3,3,3,4)$ (Kraft: $\frac14+\frac38+\frac1{16}=0{,}6875\le1$). Assegnazione canonica: $A=00$; poi tre parole di 3 bit: $B=010$, $C=011$, $D=100$; poi la parola di 4 bit $E=1010$ (si parte da $101$ e si aggiunge uno $0$, perché $100$ è già usata e $101$ è libero). $\tilde L=0{,}38\cdot2+(0{,}19+0{,}17+0{,}14)\cdot3+0{,}12\cdot4=0{,}76+1{,}5+0{,}48=2{,}74$ bit, a fronte di $H=2{,}184$ bit: $\eta=0{,}797$.

6. Codifica di Shannon-Fano

Procedura (dall'alto, top-down).

1. ordina i simboli per probabilità decrescente;
2. dividili in due gruppi (i primi $k$ e i restanti) con probabilità totali il più possibile vicine;
3. ripeti in ogni gruppo fino ad avere un solo simbolo;
4. a ogni ramo associa $0$ o $1$ (di solito $0$ al gruppo di sinistra).

Esempio (stessi simboli). $\{A,B\}$ ($0{,}57$) contro $\{C,D,E\}$ ($0{,}43$): differenza $0{,}14$ (con $\{A\}$ contro $\{B,C,D,E\}$ sarebbe $0{,}24$). Poi $\{A\},\{B\}$ e $\{C\}$ ($0{,}17$) contro $\{D,E\}$ ($0{,}26$), poi $\{D\},\{E\}$. Parole: $A=00$, $B=01$, $C=10$, $D=110$, $E=111$. $\tilde L=2(0{,}38+0{,}19+0{,}17)+3(0{,}14+0{,}12)=1{,}48+0{,}78=2{,}26$ bit ($\eta=0{,}967$).

La divisione "quasi uguale" non è sempre unica e l'algoritmo non garantisce l'ottimo; qui comunque è migliore della codifica di Shannon.

7. Codifica di Huffman

Per dire che un codice è ottimo (minima $\tilde L$ tra i codici decodificabili, cioè, per Kraft, tra quelli a prefisso) servono due proprietà.

Teorema 1. In un codice ottimo, se $P_a\le P_b$ allora $L_a\ge L_b$ (la parola più probabile non è più lunga). Teorema 2. In un codice ottimo (binario) i due simboli meno probabili hanno parole di lunghezza massima, uguali in tutto tranne l'ultimo bit (sono "fratelli" nell'albero).

Dimostrazione del Teorema 1 (per assurdo). Se fosse $P_a\le P_b$ con $L_a<L_b$, scambiando le due parole il contributo di $a$ e $b$ alla lunghezza media passerebbe da $P_aL_a+P_bL_b$ a $P_aL_b+P_bL_a$: la differenza è $(P_a-P_b)(L_b-L_a)=-(P_b-P_a)(L_b-L_a)\le0$, prodotto di due fattori non negativi cambiato di segno. Quindi $\tilde L$ non aumenta, e diminuisce se $P_a<P_b$: il codice non sarebbe ottimo. Dimostrazione del Teorema 2. La parola di lunghezza massima ha un "fratello" della stessa lunghezza che differisce solo nell'ultimo bit: se non l'avesse, si potrebbe togliere l'ultimo bit ottenendo ancora un codice a prefisso e una $\tilde L$ minore, contro l'ipotesi di ottimalità. Per il Teorema 1 le parole più lunghe appartengono ai simboli meno probabili, e tra due parole di uguale lunghezza si possono sempre scambiare i simboli, quindi si può far sì che siano proprio i due meno probabili. $\square$

Procedura (dal basso, bottom-up).

1. ordina i simboli per probabilità;
2. unisci i due meno probabili in un nodo di probabilità la somma;
3. ripeti (il nodo nuovo è un simbolo come gli altri) fino alla radice;
4. etichetta con $0$ e $1$ i due rami uscenti da ogni nodo; la parola di un simbolo è la sequenza di etichette dalla radice alla foglia.

Per il Teorema 2 unire i due meno probabili è una scelta ottima, e ripetendo il ragionamento sul problema ridotto si ottiene un codice ottimo.

Esempio. Stessi simboli ($0{,}38,\ 0{,}19,\ 0{,}17,\ 0{,}14,\ 0{,}12$). Si uniscono $D+E=0{,}26$; poi i due minori sono $C\,(0{,}17)$ e $B\,(0{,}19)$: $B+C=0{,}36$; poi $DE\,(0{,}26)$ e $BC\,(0{,}36)$: $0{,}62$; infine $A\,(0{,}38)+0{,}62=1$. Codice: $A=0$, $B=100$, $C=101$, $D=110$, $E=111$. $\tilde L=0{,}38\cdot1+0{,}62\cdot3=2{,}24$ bit, $\eta=\frac{2{,}184}{2{,}24}=0{,}975$: è il minimo possibile con parole intere (meglio di Shannon, $2{,}74$, e di Shannon-Fano, $2{,}26$).

Scorciatoia per $\tilde L$. $\tilde L$ è la somma delle probabilità dei nodi interni (le unioni): $0{,}26+0{,}36+0{,}62+1=2{,}24$. Infatti ogni foglia contribuisce con la propria probabilità tante volte quanti nodi attraversa fino alla radice, cioè la sua lunghezza.

Il codice di Huffman non è unico (a parità di probabilità si può scegliere in modi diversi e le etichette 0/1 si scambiano) ma $\tilde L$ lo è.

Esempio (sette simboli). $P=(0{,}40,\ 0{,}16,\ 0{,}15,\ 0{,}10,\ 0{,}08,\ 0{,}06,\ 0{,}05)$: $H=2{,}446$ bit, quindi per Shannon $2{,}446\le\tilde L<3{,}446$. Lunghezze di Shannon $(2,3,3,4,4,5,5)$: $\tilde L=3{,}00$ (Kraft $0{,}6875$). Shannon-Fano $\{A,B\}\,|\,\{C,\dots,G\}$: $\tilde L=2{,}55$. Huffman: unioni $0{,}11,\ 0{,}18,\ 0{,}26,\ 0{,}34,\ 0{,}60,\ 1$, somma $2{,}49$; $\eta=\frac{2{,}446}{2{,}49}=0{,}982$ (Esercizio - sorgente a sette simboli e codici di Shannon, Shannon-Fano e Huffman).

8. Raggruppare i simboli

Se le probabilità non sono potenze di $\frac12$ le parole sono di lunghezza intera e $\tilde L$ resta sopra $H$. Si può codificare una parola di $N$ simboli alla volta: la lunghezza per simbolo è $\frac{\tilde L}N\ge H_s$ e il margine "$+1$" del teorema pesa solo $\frac1N$: $$H_s\le\frac{\tilde L}N<H_s+\frac1N.$$ Il costo è la complessità: il dizionario ha $M^N$ parole.

Esempio. Sorgente senza memoria con $P=(0{,}4,\ 0{,}3,\ 0{,}3)$: $H=1{,}571$ bit. Un simbolo alla volta: Huffman dà lunghezze $(1,2,2)$, $\tilde L=1{,}6$ ($\eta=0{,}982$). Per coppie ci sono $9$ parole con probabilità $0{,}4\cdot0{,}4=0{,}16$ (una), $0{,}4\cdot0{,}3=0{,}12$ (quattro: $AB,AC,BA,CA$) e $0{,}3\cdot0{,}3=0{,}09$ (quattro): Huffman dà $\tilde L=3{,}18$ bit/coppia, $1{,}59$ bit/simbolo, $\eta=0{,}988$. Per terne $1{,}581$ bit/simbolo, $\eta=0{,}993$. Con una sorgente più sbilanciata il guadagno è più evidente: per $P=(0{,}9,0{,}1)$, $H=0{,}469$ e Huffman a un simbolo dà $1$ bit ($\eta=0{,}47$), a coppie $0{,}645$ ($0{,}73$), a terne $0{,}533$ ($0{,}88$), a quaterne $0{,}493$ ($0{,}95$).

9. Codifica aritmetica

La codifica aritmetica (versione di Shannon-Fano-Elias) non assegna una parola a ogni simbolo ma un intervallo di $[0,1)$ a tutta la sequenza, in modo che la lunghezza del codice per simbolo tenda a $H_s$ senza dover costruire un dizionario enorme.

Procedura. Si divide $[0,1)$ in sottointervalli di ampiezza uguale alle probabilità dei simboli. Per ogni simbolo letto, l'intervallo corrente si restringe al sottointervallo del simbolo, suddiviso a sua volta con le stesse proporzioni. Alla fine la sequenza è identificata da qualsiasi numero binario nell'intervallo finale (la cui ampiezza è la probabilità $P(\text{sequenza})$); servono circa $\lceil\log_2\frac1{P}\rceil+1$ bit, cioè $\simeq$ l'informazione della sequenza più al massimo 2 bit in totale. Serve un segnale di fine messaggio (STOP).

Esempio. $p_A=0{,}5$, $p_B=0{,}3$, $p_C=0{,}2$: $A\to[0;0{,}5)$, $B\to[0{,}5;0{,}8)$, $C\to[0{,}8;1)$. Sequenza $B\,A\,C\,A$:

• $B$: $[0{,}5;0{,}8)$ (ampiezza $0{,}3$);
• $A$: la prima metà ($0{,}5$ dell'ampiezza): $[0{,}5;0{,}65)$;
• $C$: l'ultimo $20\%$, da $0{,}5+0{,}8\cdot0{,}15=0{,}62$ a $0{,}65$: $[0{,}62;0{,}65)$;
• $A$: la prima metà: $[0{,}62;0{,}635)$, ampiezza $0{,}015=0{,}3\cdot0{,}5\cdot0{,}2\cdot0{,}5$.

Servono $\lceil\log_2\frac1{0{,}015}\rceil+1=\lceil6{,}06\rceil+1=8$ bit: il punto medio $0{,}6275$ troncato a 8 bit è $0{,}10100000_2=0{,}625$, che sta nell'intervallo (in questo caso bastano anche solo i 3 bit $101$). In media si resta a $H_s=1{,}485$ bit/simbolo di questa sorgente più qualche bit di coda per l'intera sequenza, senza raggruppamento.

Errori comuni

• Credere che Kraft dimostri la decodificabilità: serve solo per escludere o costruire.
• Dimenticare che Shannon vale per parola: con $N$ simboli per parola $H(\vec x)\le N\log_2M$ e $\tilde L$ è la lunghezza media della parola; per simbolo si divide per $N$.
• Unire i due simboli più probabili in Huffman, o non riordinare i nodi nuovi con quelli rimasti.
• Calcolare $\tilde L$ senza pesare con le probabilità.
• Pensare che il codice di Huffman sia unico, o che l'efficienza possa superare 1.
• Usare $\log_2M$ per un codice binario ($=1$) senza scriverlo nell'efficienza, o dimenticarlo per $M>2$.