Codifica di sorgente - codici a prefisso e teorema di Shannon

Lo schema

Al quantizzatore o alla sorgente esce un flusso di simboli. Si possono trasmettere così, con $\log_2M$ bit ciascuno (codifica a lunghezza fissa), oppure ridurre i bit con una codifica di sorgente (source coding). Esistono due tipi:

• lossycon perdita di informazione, come mp3 e jpeg (con perdita): mp3, jpeg, png compressi;
• losslesssenza perdita: dai bit codificati si ricostruisce esattamente la sequenza originale (senza perdita): zip. Il corso studia solo questa.

Lo schema è: sorgente $\to$ S/P (si raggruppano $N$ simboli in una parola $\mathbf x$) $\to$ mappa $\mu_s:\ \mathcal D_{\mathbf x}\to\mathcal D_{\mathbf y}$ $\to$ P/S (le parole codificate si mettono in fila). La mappa deve essere invertibile: così $H(\mathbf x)=H_s(\mathbf y)$ e non si perde informazione. $\mathcal D_{\mathbf x}$ è il dizionario di ingresso, $\mathcal D_{\mathbf y}$ quello delle parole di codice.

Grandezze

Il codice $\mathcal C=\mu_s(\mathcal D_{\mathbf x})$ ha un alfabeto di $M_y$ simboli (2 per un codice binario); $L(b)$ è la lunghezza della parola $b$ e la lunghezza media è $$L_y=E\left[L(b)\right]=\sum_{b\in\mathcal C}P(b)\,L(b).$$ Senza codifica $L_x=\lceil\log_2M\rceil$ ($=\log_2M$ se è una potenza di 2). L'idea: parole frequenti $\to$ corte, parole rare $\to$ lunghe, per abbassare $L_y$. L'efficienza del codice è $$\eta_y=\frac{H(\mathbf x)}{L_y\log_2M_y}\qquad(\text{binario: }\eta=\tfrac{H}{L_y}),$$ (come $\eta_s=\frac{H_s}{\log_2M}$ di 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 →; per una parola $\mathbf x$ senza codifica $\eta_x=\frac{H(\mathbf x)}{L_x\log_2M}$). Il rate nominale dopo la codifica è $F_sL_y\log_2M_y$ (bit/s) mentre il rate di informazione è $F_sH$.

Codici decodificabili e a prefisso

Esempio. Alfabeto $\{A,B,C,D,E\}$ con il codice $A\to0,\ B\to00,\ C\to01,\ D\to111,\ E\to1111$: la sequenza $010001111011111$ non è univocamente decodificabile (per esempio $000$ può essere $AAA$, $AB$ o $BA$). Il ricevitore deve poter ricostruire in modo univoco la sequenza trasmessa: il codice deve essere decodificabile (uniquely decodable).

Una parola $b$ è prefisso di $b'$ se $L(b)<L(b')$ e $b$ coincide con i primi $L(b)$ simboli di $b'$. Un codice è a prefisso se nessuna delle sue parole è prefisso di un'altra.

Proposizione. Un codice a prefissonessuna parola di codice è l'inizio di un'altra parola è decodificabileda una sequenza di parole di codice si risale in modo unico ai simboli trasmessi: letti i simboli uno a uno, appena si riconosce una parola di codice la si può emettere (nessuna parola più lunga la contiene all'inizio), e si riparte. Quindi la decodifica è istantanea.

Non vale il contrario: non tutti i codici decodificabili sono a prefisso. Per esempio $\{0,01\}$ è decodificabile (dopo uno 0 si attende il bit successivo) ma 0 è prefisso di 01.

Esempio di codice a prefisso: $A\to00,\ B\to01,\ C\to10,\ D\to110,\ E\to111$. La sequenza $0100011110\,1111$ si legge $01\,00\,01\,111\,01\,111=B\,A\,B\,E\,B\,E$ senza ambiguità.

Si possono costruire i codici a prefisso con un albero binario: ogni parola è una foglia, il percorso dalla radice la scrive (0 a sinistra, 1 a destra) e nessuna parola è su un nodo interno.

Teorema di Kraft-McMillan

Sia $\mathcal C$ un codice con alfabeto di $M_y$ simboli e $L(b)$ la lunghezza della parola $b$.

1. Se $\mathcal C$ è decodificabile, allora $$\boxed{\sum_{b\in\mathcal C}\frac1{M_y^{L(b)}}\le1.}$$
2. Viceversa, se esistono interi $\ell_1,\dots,\ell_N$ con $\sum_{i=1}^N\frac1{M_y^{\ell_i}}\le1$, allora esiste un codice a prefisso con alfabeto $M_y$ e parole di lunghezze $\ell_1,\dots,\ell_N$.

(Equivalente, per un codice con probabilità: $E\left[\frac1{M_y^{L(b)}P_y(b)}\right]\le1$.)

Il punto 1 serve per escludere codici: se la somma supera 1 il codice non è decodificabile. Il punto 2 per costruirli. Attenzione: il punto 1 è una condizione necessaria, non sufficiente. Controesempio: $\{0,01,10\}$ ha somma $\frac12+\frac14+\frac14=1$ ma $010$ è ambiguo ($0\,10$ oppure $01\,0$).

Esempio. Si applica ai due codici di prima (binari, $M_y=2$):

• $A\to0,B\to00,C\to01,D\to111,E\to1111$: $\frac12+2\cdot\frac14+\frac18+\frac1{16}=\frac{19}{16}>1$: non decodificabile;
• $A\to00,B\to01,C\to10,D\to110,E\to111$: $3\cdot\frac14+2\cdot\frac18=1$: compatibile (ed è a prefisso).

La disuguaglianza dice "non possiamo avere troppe parole corte": ognuna occupa una frazione $\frac1{M_y^{L}}$ dell'albero.

Esempio (esame, gennaio 2025). Lunghezze richieste $2,2,3,3,3,3,4,4$ per 8 parole: $2\cdot\frac14+4\cdot\frac18+2\cdot\frac1{16}=\frac98>1$: non esiste nessun codice decodificabile con queste lunghezze (Esercizio 2 · codice di Huffman a 8 livelli e verifica di Kraft-McMillan (tema d'esame gennaio 2025)).

Teorema di Shannon sulla codifica di sorgente

Sia $\mathcal C$ un codice con alfabeto di cardinalità $M_y$ per la parola $\mathbf x$ di entropia $H(\mathbf x)$.

1. Se $\mathcal C$ è decodificabile: $L_y\ge\dfrac{H(\mathbf x)}{\log_2M_y}$.
2. Esiste un codice decodificabile e a prefisso con $L_y\le\dfrac{H(\mathbf x)}{\log_2M_y}+1$.

Il teorema dà solo limiti: non dice se un codice ottimo esiste né come trovarlo.

Dimostrazione del punto 1 (per codici binari: $M_y=2$, ma vale in generale). Dalla disuguaglianza di Kraft $E\left[\frac1{M_y^{L}P}\right]\le1$. Applicando il logaritmo in base $\frac1{M_y}$ (decrescente: inverte la disuguaglianza) e la disuguaglianza di Jensen: $$0\le\log_{1/M_y}E\left[\frac1{M_y^{L}P}\right]\le E\left[\log_{1/M_y}\frac1{M_y^{L}P}\right]=E[L]-\frac{1}{\log_2M_y}E\left[\log_2\frac1P\right]=L_y-\frac{H(\mathbf x)}{\log_2M_y}.$$ Quindi $L_y\ge\frac{H}{\log_2M_y}$. $\square$

Dimostrazione del punto 2. Si scelgono le lunghezze $\ell_i=\left\lceil\log_{M_y}\frac1{P(a_i)}\right\rceil$. Allora $M_y^{-\ell_i}\le P(a_i)$ e $\sum_iM_y^{-\ell_i}\le\sum_iP(a_i)=1$: vale Kraft, quindi esiste un codice a prefisso con queste lunghezze (parole più brevi per le più probabili). Inoltre $\ell_i<\log_{M_y}\frac1{P(a_i)}+1$ e, mediando, $L_y<\frac{H}{\log_2M_y}+1$. $\square$

Il codice è ottimo (raggiunge il limite inferiore) se e solo se $P(a_i)=\left(\frac1{M_y}\right)^{c_i}$ con $c_i$ interi (probabilità potenze di $\frac1{M_y}$): allora $\log_{M_y}\frac1P$ è intero e $L_y=\frac{H}{\log_2M_y}$, cioè $\eta=1$.

Esempio. Sorgente con probabilità $\left(\frac12,\frac14,\frac18,\frac18\right)$: lunghezze $1,2,3,3$, $L_y=\frac12+\frac24+\frac38+\frac38=1{,}75=H$ bit: $\eta=1$. Sorgente con $(0{,}35,0{,}22,0{,}20,0{,}13,0{,}10)$ ($H=2{,}19$ bit): limiti $2{,}19\le L_y\le3{,}19$; le lunghezze del punto 2 ($\lceil\log_2\frac1P\rceil=2,3,3,3,4$) danno $L_y=2{,}75$, con Kraft $\frac14+\frac38+\frac1{16}=0{,}6875\le1$: un codice a prefisso c'è, ma non è il migliore (l'algoritmo di Huffman ottiene $2{,}23$, 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 →).

Raggruppare simboli per avvicinarsi al limite

Se le probabilità non sono potenze di $\frac12$, la lunghezza mediasomma delle lunghezze delle parole pesate con le loro probabilità per simbolo di un codice a parole intere può restare lontana da $H$. Si codifica una parola di $N$ simboli insieme: $L_y$ è per parola, per simbolo si divide per $N$ ($\frac{L_y}N\ge H_s$ e il margine "+1" pesa $\frac1N$).

Esempio. Sorgente binaria senza memoria con $P(A)=0{,}9$, $P(B)=0{,}1$: $H=0{,}469$ bit/simbolo. Un bit a simbolo dà $\eta=0{,}469$. Codificando coppie ($AA\ 0{,}81$, $AB\ 0{,}09$, $BA\ 0{,}09$, $BB\ 0{,}01$) con Huffman si hanno lunghezze $1,3,2,3$: $L=0{,}81+0{,}27+0{,}18+0{,}03=1{,}29$ bit/coppia $=0{,}645$ bit/simbolo, $\eta=0{,}73$. Con terne $L=0{,}533$ bit/simbolo, $\eta=0{,}88$. Il costo è la complessità (dizionario di $M^N$ parole).

Errori comuni

• Credere che Kraft dimostri la decodificabilità: serve solo per escludere codici o per costruirli.
• Dimenticare che Shannon vale per parola: se si codificano $N$ simboli insieme, $H(\mathbf x)\le N\log_2M$ e $L_y$ è la lunghezza media della parola.
• Dire che un codice a prefisso deve avere tutte le parole della stessa lunghezza.
• Usare $\log_2M_y$ per un codice binario ($=1$) senza accorgersene nell'efficienza: va scritto, anche se vale 1.