Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media

Una sorgente digitale spesso emette più bit del necessario: se i simboli non sono equiprobabili l'entropia è minore di $\log_2M$ (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 →) e si può rappresentare lo stesso messaggio con meno bit. La codifica di sorgente lo fa. Questa nota dice quali codici sono ammissibili (Kraft-McMillan) e quanto corto può essere un codice (teorema di Shannon); la costruzione dei codici ottimi è nella nota successiva (Codici di Shannon, Huffman ed Elias e codifica aritmeticaIl codice di Shannon(-Fano) assegna alla parola $i$ lunghezza $l_i=\lceil-\log_{M_y}p_i\rceil$, soddisfa Kraft-McMillan e ha $H\le L_y<H+1$; è ottimo solo se le probabilità sono potenze di $\frac1{M_y}$. Il codice ottimo (lunghezza media minima) dà parole più lunghe ai simboli meno probabili e ha almeno due parole di lunghezza massima che differiscono solo nell'ultimo simbolo: lo costruisce la procedura di Huffman, che unisce a ogni passo i due nodi meno probabili. Il codice di Elias prende le prime $l_i=\lceil-\log_2p_i\rceil+1$ cifre del punto medio dell'intervallo di ampiezza $p_i$ in $[0,1)$: è a prefisso ma subottimo ($H+1\le L_y<H+2$), e si adatta alla codifica aritmetica adattativa.Codici di Shannon, Huffman ed Elias e codifica aritmetica →).

Versione per 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 →. 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 →.

Dove sta la codifica di sorgente

Nella catena di trasmissione digitale il codificatore di sorgente sta subito dopo la sorgente; seguono il codificatore di canale e il modulatore.

$$\text{S}\xrightarrow{\ T_s\ }\boxed{\text{COD. SORGENTE}}\xrightarrow{\ T_c\ }\boxed{\text{COD. CANALE}}\xrightarrow{}\boxed{\text{MOD}}\longrightarrow\text{CANALE}\longrightarrow\boxed{\text{DEM}}\to\boxed{\text{DEC. CANALE}}\to\boxed{\text{DEC. SORGENTE}}\to\text{D}$$

Fino al codificatore di canale la comunicazione è digitale e (dopo la codifica di sorgente) affidabile; dal modulatore in poi il segnale è analogico e la comunicazione è inaffidabile (rumore). Il codificatore di sorgente riduce il numero di bit al secondo: se i bit entrano ogni $T_s$ e escono ogni $T_c$, allora $T_c>T_s$ e $\frac1{T_s}>\frac1{T_c}$ bit/s. Esistono due tipi di codifica di sorgente:

• con perdite (la quantizzazione, Quantizzazione uniforme - saturazione, errore granulare e SNR di quantizzazioneUn quantizzatore uniforme a L = 2^b livelli e range [−v_sat, v_sat] ha passo Δ = 2v_sat/L. L'errore e = x − x^(q) è di saturazione fuori range (illimitato, da rendere raro con P_sat piccola) e granulare dentro (|e| ≤ Δ/2, uniforme con potenza Δ²/12). L'SNR di quantizzazione Λ_q = E[x²]/E[e²] vale in decibel 20log₁₀(σ_x/v_sat) + 4,77 + 6,02·b: ogni bit in più dà 6 dB. Per b minimo che garantisce una specifica: ⌈(specifica − c)/6,02⌉ con c = 20log₁₀(σ_x/v_sat) + 4,77.Quantizzazione uniforme - saturazione, errore granulare e SNR di quantizzazione →): il segnale ricostruito è diverso dall'originale;
• senza perdite (questa nota): il decodificatore recupera esattamente la sequenza emessa.

Il modello

Il codificatore $\mathcal M_s$ riceve dalla sorgente una parola $\underline x_m$ (un vettore di uno o più simboli; $m$ è l'indice del tempo) del dizionario della sorgente $\mathcal D_x$ e produce una parola di codice $\underline y_m=\mathcal M_s(\underline x_m)$ nel dizionario del codice $\mathcal D_y$, formato da sequenze di simboli di un alfabeto di cardinalità $M_y$ (per il caso binario $M_y=2$). Si richiede che:

1. la codifica sia parola per parola (senza memoria): ogni $\underline x_m$ è codificata da sola;
2. la codifica sia invertibile: per ogni $\underline y\in\mathcal D_y$ esiste una sola $\underline x\in\mathcal D_x$ con $\underline y=\mathcal M_s(\underline x)$.

Le parole di codice hanno lunghezza variabile $l(\underline y)$. Se $p_{\underline x}(\underline a)$ è la probabilità che la sorgente emetta la parola $\underline a\in\mathcal D_x$, la metrica per valutare un codice è la lunghezza media.

Definizione (lunghezza media delle parole di codice). $$L_y=E\left[l(\mathcal M_s(\underline x))\right]=\sum_{\underline a\in\mathcal D_x}l\left(\mathcal M_s(\underline a)\right)\,p_{\underline x}(\underline a)\quad[\text{simboli di codice per parola}].$$

Un buon codice dà parole corte ai simboli frequenti e lunghe ai rari. Invertibile da sola non basta: il ricevitore riceve un flusso continuo e deve separare le parole.

Esempio (codice non decodificabile). Sorgente con $\mathcal D_x=\{A,B,C,D\}$ di probabilità $0{,}1;\ 0{,}2;\ 0{,}3;\ 0{,}4$ e codice $A\to01$, $B\to101$, $C\to1111$, $D\to0101$. La lunghezza media è $$L_y=0{,}1\cdot2+0{,}2\cdot3+0{,}3\cdot4+0{,}4\cdot4=0{,}2+0{,}6+1{,}2+1{,}6=3{,}6\ \text{bit}.$$ Ma il flusso $\dots01\,01\dots$ può essere letto come $A\,A$ oppure come $D=0101$: il codice non è decodificabile. La causa è che $01$ è l'inizio (prefisso) di $0101$.

Codici a prefisso

Definizione. In un codice a prefisso nessuna parola di codice è il prefisso (la parte iniziale) di un'altra parola.

Esempio. $\{1,\ 010,\ 0110,\ 0111\}$ è a prefisso. Il flusso $1\,|\,0110\,|\,0111\,|\,010\,|\,1$ si separa in modo unico: appena i bit letti formano una parola del codice, quella parola è finita (nessuna parola più lunga può iniziare con essa). Per questo la decodifica è istantanea, senza bisogno di guardare i bit seguenti. Un codice a prefisso è sempre decodificabile. Il contrario non vale in generale (esistono codici decodificabili non a prefisso, ma non servono: sono sempre eguagliati da un codice a prefisso con le stesse lunghezze, per il teorema che segue).

Un codice a prefisso si rappresenta con un albero $M_y$-ario: ogni parola è una foglia, nessuna foglia è antenata di un'altra.

Teorema di Kraft-McMillan

Teorema (Kraft-McMillan). Sia $M_y$ la cardinalità dell'alfabeto di codice.

1. (Condizione necessaria.) Per ogni codificatore decodificabile senza perdite, con parole di lunghezza $l_1,\dots,l_N$, $$\boxed{\sum_{i=1}^N\frac1{M_y^{\,l_i}}\le1.}$$
2. (Esistenza.) Se $l_1,\dots,l_N$ sono interi che soddisfano la disuguaglianza (con $M_y$ intero), esiste un codice a prefisso con alfabeto di cardinalità $M_y$ e parole di lunghezza $l_1,\dots,l_N$.

Il teorema dice due cose: nessun codice decodificabile può avere lunghezze che violano la somma $\le1$; e se la somma è $\le1$ le lunghezze vanno bene, anche a prefisso. Attenzione: la condizione riguarda le lunghezze, non un codice dato. Un codice con somma $\le1$ può non essere decodificabile: quello dell'esempio ($A\to01$, $B\to101$, $C\to1111$, $D\to0101$) ha $\frac14+\frac18+\frac1{16}+\frac1{16}=0{,}5\le1$, eppure non è decodificabile; esiste però un altro codice a prefisso con le stesse lunghezze $2,3,4,4$ (per esempio $00,\ 010,\ 0110,\ 0111$).

Perché (codici a prefisso, binari). Sia $l_{\max}$ la lunghezza massima. Ogni parola di lunghezza $l_i$ ha $2^{l_{\max}-l_i}$ discendenti alla profondità $l_{\max}$, e per la proprietà del prefisso questi insiemi di discendenti sono disgiunti. In tutto ci sono $2^{l_{\max}}$ nodi alla profondità $l_{\max}$, quindi $\sum_i2^{l_{\max}-l_i}\le2^{l_{\max}}$, cioè $\sum_i2^{-l_i}\le1$. Per l'esistenza si ordinano le lunghezze $l_1\le\dots\le l_N$ e si assegna alla parola $i$ le prime $l_i$ cifre dello sviluppo in base $M_y$ del numero $c_i=\sum_{j<i}M_y^{-l_j}$: la somma $\le1$ garantisce $c_i<1$, e le parole successive non possono iniziare con una precedente, perché $c_i-c_j\ge M_y^{-l_j}$. Per il caso generale dei codici decodificabili (McMillan) si usa la potenza $k$-esima: $\left(\sum_iM_y^{-l_i}\right)^k=\sum_mN_k(m)M_y^{-m}$ con $N_k(m)\le M_y^m$ numero di sequenze di $k$ parole lunghe $m$ (altrimenti due sequenze darebbero la stessa stringa), da cui la somma è al più $k\,l_{\max}$; un numero la cui potenza $k$-esima cresce al più linearmente in $k$ non supera $1$.

Esempio. Lunghezze $2,2,3,3,3,3,4,4$ con alfabeto binario: $2\cdot\frac14+4\cdot\frac18+2\cdot\frac1{16}=\frac12+\frac12+\frac18=\frac98>1$. Non esiste un codice decodificabile con quelle lunghezze. Si vede sull'albero: le due parole da $2$ bit occupano metà dei nodi, le quattro da $3$ bit l'altra metà, e per le due da $4$ bit non resta spazio.

Esempio (alfabeto ternario). Lunghezze $1,1,2,2,2,3$ con $M_y=3$: $\frac23+\frac39+\frac1{27}=\frac{18+9+1}{27}=\frac{28}{27}=1{,}037>1$: non esiste un codice decodificabile ternario con quelle lunghezze.

Teorema di Shannon sulla codifica di sorgente

Sia $\underline x\in\mathcal D_x$ la parola emessa, con entropia $H(\underline x)$ (in bit).

Teorema (Shannon, codifica di sorgente). Per un codificatore senza perdite con alfabeto di cardinalità $M_y$:

1. (Limite inferiore.) Ogni codice decodificabile ha $\displaystyle L_y\ge\frac{H(\underline x)}{\log_2M_y}$.
2. (Esistenza.) Esiste un codice a prefisso con $\displaystyle L_y<\frac{H(\underline x)}{\log_2M_y}+1$.

In sintesi, esiste sempre un codice a prefisso con $$\boxed{\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1.}$$ Per il codice binario ($M_y=2$): $H(\underline x)\le L_y<H(\underline x)+1$, in bit per parola.

L'entropia è dunque il limite fondamentale: nessun codice può scendere sotto di essa, e con un codice a prefisso ci si avvicina a meno di $1$ bit.

Dimostrazione del limite inferiore. Dalla disuguaglianza di Kraft-McMillan, riscrivendo ogni termine con la probabilità $p_{\underline y}(\underline y)=p_{\underline x}(\underline x)$ (il codice è invertibile): $$1\ge\sum_{\underline y}\frac1{M_y^{l(\underline y)}}=\sum_{\underline y}p_{\underline y}(\underline y)\cdot\frac1{M_y^{l(\underline y)}p_{\underline y}(\underline y)}=E\left[\frac1{M_y^{l(\underline y)}p_{\underline y}(\underline y)}\right].$$ Passando ai logaritmi, il logaritmo di un numero $\le1$ è $\le0$, e si applica Jensen (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 →) al logaritmo, concavo: $$0\ge\log_2E\left[\frac1{M_y^{l(\underline y)}p_{\underline y}(\underline y)}\right]\ge E\left[\log_2\frac1{M_y^{l(\underline y)}p_{\underline y}(\underline y)}\right]=E\left[-l(\underline y)\log_2M_y+\log_2\frac1{p_{\underline y}(\underline y)}\right]=-L_y\log_2M_y+H(\underline x).$$ Da $0\ge H(\underline x)-L_y\log_2M_y$ segue $L_y\ge\frac{H(\underline x)}{\log_2M_y}$. $\blacksquare$

Dimostrazione dell'esistenza. Si scelgono le lunghezze $$l_i=\left\lceil\log_{1/M_y}p_{\underline x}(\underline a_i)\right\rceil=\left\lceil-\log_{M_y}p_{\underline x}(\underline a_i)\right\rceil,\qquad\text{cioè }l_i=\left\lceil\frac{\log_2\frac1{p_i}}{\log_2M_y}\right\rceil.$$ (il logaritmo in base $\frac1{M_y}<1$ di una probabilità è positivo).

• Soddisfano Kraft-McMillan: poiché $\lceil u\rceil\ge u$ e la base $\frac1{M_y}$ è minore di $1$, $\left(\frac1{M_y}\right)^{l_i}\le\left(\frac1{M_y}\right)^{\log_{1/M_y}p_i}=p_i$. Sommando: $\sum_iM_y^{-l_i}\le\sum_ip_i=1$. Quindi esiste un codice a prefisso con queste lunghezze.
• Lunghezza media: da $\lceil u\rceil<u+1$, $$L_y=\sum_ip_i\,l_i<\sum_ip_i\left[\frac{\log_2\frac1{p_i}}{\log_2M_y}+1\right]=\frac{H(\underline x)}{\log_2M_y}+1,$$ dove si è fatto un cambio di base del logaritmo ($\log_{M_y}u=\frac{\log_2u}{\log_2M_y}$). $\blacksquare$

Quando si raggiunge il limite. $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze intere di $\frac1{M_y}$, $p_i=M_y^{-k_i}$: allora $l_i=k_i$ esatti, senza arrotondamento. Per esempio $p=\left(\frac12,\frac14,\frac18,\frac18\right)$ con $M_y=2$ ha lunghezze $1,2,3,3$, $L_y=1{,}75=H$.

Esempio (alfabeto ternario). Stessa sorgente con $M_y=3$: lunghezze $\lceil\log_32\rceil=1$, $\lceil\log_34\rceil=2$, $\lceil\log_38\rceil=2,\ 2$. Kraft: $\frac13+3\cdot\frac19=\frac23\le1$. Lunghezza media $L_y=0{,}5\cdot1+0{,}25\cdot2+0{,}25\cdot2=1{,}5$ simboli ternari. Limiti: $\frac H{\log_23}=\frac{1{,}75}{1{,}585}=1{,}104$ e $1{,}104+1=2{,}104$: $1{,}104\le1{,}5<2{,}104$ ✓.

Raggruppare più simboli per avvicinarsi al limite

Il "+1" del limite superiore è un costo per parola. Se si codificano blocchi di $N$ simboli indipendenti, l'entropia della parola è $NH_s$ e la lunghezza media per simbolo $\frac{L_y}N$ soddisfa $H_s\le\frac{L_y}N<H_s+\frac1N$: tende al limite.

Esempio. Sorgente binaria con $P(0)=0{,}9$, $P(1)=0{,}1$, $H=0{,}469$ bit per simbolo. Codificando un simbolo alla volta serve sempre $1$ bit (due parole, lunghezze $1,1$): $L=1$ bit per simbolo, il $213\%$ di $H$. A coppie ($00,01,10,11$ con probabilità $0{,}81;\ 0{,}09;\ 0{,}09;\ 0{,}01$) il codice ottimo ha lunghezze $1,2,3,3$ e $L_y=0{,}81+0{,}18+0{,}27+0{,}03=1{,}29$ bit per coppia, cioè $0{,}645$ bit per simbolo; a triple si scende a $0{,}533$ bit per simbolo (valori calcolati con Python). L'efficienza sale, a prezzo di un ritardo e una complessità maggiori.

Errori comuni

• Usare Kraft-McMillan per dimostrare che un codice dato è decodificabile: la somma $\le1$ vale per le lunghezze, un codice può violare il prefisso pur rispettandola.
• Concludere da $\sum M_y^{-l_i}>1$ che "si può aggiustare qualche parola": la risposta è netta, non esiste nessun codice decodificabile con quelle lunghezze.
• Confrontare $L_y$ con $H$ senza dividere per $\log_2M_y$ per alfabeti non binari.
• Dire che il codice di Shannon ha $L_y=H$: vale solo con probabilità potenze di $\frac1{M_y}$; in generale è $H\le L_y<H+1$.
• Calcolare $L_y$ senza pesare le lunghezze con le probabilità.
• Dimenticare che il codice a prefisso con $L_y<H+1$ può non essere ottimo: il limite superiore dice solo che il migliore ci sta sotto.

Domande d'esame

1. Si enunci la disuguaglianza di Kraft-McMillan e la si usi per stabilire se esiste un codice binario con lunghezze $2,3,3,3,4,4,5,5$. $\sum_i2^{-l_i}\le1$ è necessaria per la decodificabilità e sufficiente per l'esistenza di un prefisso. Qui $\frac14+3\cdot\frac18+2\cdot\frac1{16}+2\cdot\frac1{32}=\frac{8+12+4+2}{32}=\frac{26}{32}<1$: il codice esiste.
2. Si enunci il teorema di Shannon per la codifica di sorgente e se ne dimostri il limite inferiore. $\frac H{\log_2M_y}\le L_y<\frac H{\log_2M_y}+1$; limite inferiore: da Kraft, $1\ge E\left[\frac1{M_y^{l}p}\right]$, logaritmo e Jensen danno $0\ge H-L_y\log_2M_y$.
3. Un codice di Shannon binario per una sorgente con $H=2{,}45$ bit può avere lunghezza media $4$ bit? No: il codice di Shannon ha $L_y<H+1=3{,}45$ bit.

Esercizi svolti

• Esercizio - Kraft-McMillan, Huffman, due canali binari alternati e codice di Hamming (15,11) (compito del 13 febbraio 2026, es. 201): Kraft con lunghezze $2,3,3,3,4,4,5,5$, assegnazione ottima e bit rate minimo.
• Esercizio - Kraft-McMillan, Huffman, Hamming (7,4) e attenuazione massima con 16-QAM (secondo compitino del 12 gennaio 2024, es. 170): Kraft con lunghezze $2,2,2,3,3,3,4,5$ (somma $\frac{39}{32}>1$) e bit rate minimo.
• Esercizio - entropia, Kraft-McMillan ternario, Huffman e capacità di due canali binari in cascata (secondo compitino del 14 gennaio 2025, es. 186): Kraft ternario con lunghezze $1,1,2,2,2,3$ (somma $\frac{28}{27}>1$).
• Esercizio - due sorgenti indipendenti, codice di Shannon, Huffman e informazione mutua con un prodotto (compito del 24 gennaio 2025, es. 189): limite del codice di Shannon, $L<H+1$, e cardinalità dal tasso nominale.
• Esercizio - sensori di temperatura, codice di Huffman, porta seriale e informazione mutua (esercizi del corso, cap. 5, es. 56): codice per quattro temperature e limite inferiore per le coppie.