Codifica lossless - entropia, Huffman e codifiche a dizionario

Dopo la digitalizzazione (Digitalizzazione dei segnali multimediali - campionamento, quantizzazione e binarizzazioneLa conversione analogico-digitale (ADC) ha tre passi: campionamento $s_c(n)=s(nT_c)$, quantizzazione su $L=2^m$ livelli, binarizzazione dell'indice in $m$ bit; il bit-rate vale $R=F_c\log_2L$. Per il teorema di Shannon un segnale a banda limitata $f_M$ si ricostruisce senza errore se $F_c\ge2f_M$ (criterio di Nyquist), altrimenti c'è aliasing; per questo prima del campionatore c'è un filtro passa-basso. La quantizzazione uniforme di passo $\Delta=\frac{2A}{L}$ è irreversibile, con errore massimo $\frac\Delta2$ e $\mathrm{MSE}=\frac{\Delta^2}{12}$; la qualità si misura con MSE e $\mathrm{PSNR}=10\log_{10}\frac{(2^b-1)^2}{\mathrm{MSE}}$. In ricezione il bit mapper ricostruisce i valori e l'interpolazione con un nucleo $h$ (sample and hold, lineare, cubica, sinc troncato) riporta il segnale al tempo continuo.Digitalizzazione dei segnali multimediali - campionamento, quantizzazione e binarizzazione →) un segnale è una sequenza di simboli (valori quantizzati) scritti con un numero fisso di bit. Ma non tutti i simboli sono ugualmente probabili e non sono indipendenti: si può scriverli con meno bit, senza perdere nulla. Questa è la codifica lossless (o entropica): rappresentare i simboli emessi da una sorgente con una stringa di bit in modo perfettamente invertibile. Gli esempi del corso: un blocco $4\times2$ di pixel in scala di grigi codificato in bit e ridecodificato esattamente; un file XML compresso e riottenuto identico.

Questa nota contiene il quadro teorico di sorgente (richiamato anche in 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 →, 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 → e 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 →) e le tecniche usate in pratica. Gli esercizi sono in Esercizio - Entropia, codici di Huffman e Exp-Golomb (domande ed esercizi del corso).

1. Principi di base

Una sorgente $X$ emette simboli di un insieme finito $\mathcal X=\{x_1,\dots,x_M\}$ (alfabeto): lettere e punteggiatura per un testo, valori di luminanza quantizzati per un'immagine, valori quantizzati di pressione acustica per l'audio. È modellata come un processo aleatorio, cioè una sequenza di variabili aleatorie; ogni simbolo ha una probabilità $p_i=\Pr[X=x_i]$.

Definizione (codice). Un codice $C$ è una mappa dall'alfabeto all'insieme delle stringhe di bit di lunghezza finita: $C:x_i\mapsto c_i\in\{0,1\}^*$. Le stringhe $c_i$ sono le codeword, di lunghezza $\ell_i$. Nei codici a lunghezza fissa tutte le codeword hanno la stessa lunghezza; altrimenti il codice è a lunghezza variabile. La lunghezza media è $$\mathcal L=\sum_{i=1}^Mp_i\,\ell_i\quad\text{(bit per simbolo)}.$$

Cercare codici con $\mathcal L$ piccola è importante, ma non è l'unico requisito: il codice deve essere univocamente decodificabile (u.d.): ogni sequenza di codeword deve poter essere decodificata in un solo modo, perché le codeword vengono scritte una dopo l'altra senza separatori. Non basta che la mappa sia iniettiva.

Codice a lunghezza fissa (FLC). È la tecnica basilare: ogni simbolo ha lo stesso numero di bit, $\lceil\log_2M\rceil$ (per esempio 4 bit per i 15 indici da $-7$ a $7$). Vantaggi: il parsing è immediato (4 bit $\to$ un simbolo), l'univoca decodificabilità è intrinseca, un errore su un bit tocca un solo simbolo. Svantaggio: non sfrutta le distribuzioni non uniformi.

1.1 Confronto tra quattro codici

Sorgente con $\Pr(A)=\frac12,\ \Pr(B)=\frac14,\ \Pr(C)=\Pr(D)=\frac18$:

• Codice 1: non è nemmeno iniettivo ($A$ e $B$ hanno la stessa codeword): "0" non si può decodificare.
• Codice 2: iniettivo ma non u.d.: la stringa $0011$ si decodifica come $AABB$, $AAD$, $CBB$ o $CD$.
• Entrambi hanno $\mathcal L$ piccola ma nessun interesse pratico.
• Codice 3: è u.d. perché è un codice a prefisso (nessuna codeword è prefisso di un'altra): appena si riconosce una codeword nel flusso si decodifica subito il simbolo, per questo si dice istantaneo.
• Codice 4: u.d. (basta contare quanti 1 ci sono tra due zeri) ma non istantaneo: dopo un 0 bisogna aspettare l'inizio della codeword successiva per sapere se la parola è finita.

Il migliore è il codice 3: u.d., istantaneo e di lunghezza media minima. D'ora in poi si considerano solo i codici a prefisso: si può dimostrare che il miglior codice istantaneo ha la stessa $\mathcal L$ del miglior codice u.d., quindi non si perde nulla. (La condizione di esistenza di un codice a prefisso con date lunghezze è la disuguaglianza di Kraft-McMillan, in 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 →.)

2. Entropia e teorema di Shannon

L'informazione associata all'evento $X=x_i$ è $$I(x_i)=\log_2\frac1{p_i}=-\log_2p_i\quad[\text{bit}].$$ È non negativa e decrescente con la probabilità: un evento improbabile porta molta informazione; l'informazione di due eventi indipendenti è la somma delle informazioni (perché i logaritmi trasformano il prodotto delle probabilità in somma). L'informazione media è l'entropia: $$\boxed{H(X)=E[I(X)]=\sum_{i=1}^Mp_i\log_2\frac1{p_i}.}$$

L'entropia è il grado di incertezza sulla realizzazione della variabile aleatoria.

• A parità di $M$, è massima se i simboli sono equiprobabili (condizione di non sparsità): $H=\log_2M$. Per una variabile binaria equiprobabile $H=\frac12\log_22+\frac12\log_22=1$ bit.
• È tanto più bassa quanto più la distribuzione è sparsa: pochi simboli molto probabili e molti poco probabili (lettere di un testo: alcune molto più frequenti; coppie di lettere: alcune non compaiono mai, come "qh"; blocchi di $n$ lettere: l'entropia per lettera diminuisce al crescere di $n$).

Teorema di Shannon sulla codifica di sorgente. La lunghezza media $\mathcal L^*$ del codice istantaneo ottimo per una sorgente $X$ soddisfa $$H(X)\le\mathcal L^*<H(X)+1,$$ e l'uguaglianza a sinistra vale se e solo se tutte le probabilità sono potenze intere negative di due (distribuzione diadica).

Significato: il livello di incertezza di una variabile aleatoria è il numero minimo di bit in media necessario a descriverne una realizzazione. Ma il teorema è non costruttivo: non dice come costruire il codice ottimo né, per una distribuzione non diadica, quanto vale $\mathcal L^*$. Ci risponde l'algoritmo di Huffman.

3. Codifica di Huffman

Trova uno dei codici ottimi (ne esistono diversi, equivalenti) per una data distribuzione. Si costruisce un albero binario:

1. si creano $M$ nodi attivi, uno per simbolo, etichettati con la probabilità (saranno le foglie);
2. si prendono i due nodi attivi con probabilità più bassa (a parità, uno qualunque);
3. si crea un nodo genitore di quei due con probabilità pari alla somma;
4. si tolgono i due figli dalla lista dei nodi attivi e si inserisce il genitore;
5. se i nodi attivi sono più di uno, si torna al punto 2.

Poi si etichettano i rami con 0 e 1; la codeword di un simbolo è la sequenza di bit sul cammino dalla radice alla foglia. Il codice è a prefisso per costruzione (tutte le codeword stanno sulle foglie) e se ne dimostra l'ottimalità. Perché prendere i due meno probabili: sono quelli che conviene "allungare" (metterli più in fondo), perché pesano meno nella media.

Esempio (6 simboli). $P(A)=0{,}4$, $P(B)=0{,}2$, $P(C)=P(D)=0{,}15$, $P(E)=P(F)=0{,}05$.

• $E+F\to0{,}10$; poi $0{,}10+D(0{,}15)\to0{,}25$; poi $C(0{,}15)+B(0{,}2)\to0{,}35$; poi $0{,}25+0{,}35\to0{,}60$; infine $A(0{,}4)+0{,}60\to1$.
• Una assegnazione dei bit: $A=0$, $B=110$, $C=111$, $D=100$, $E=1010$, $F=1011$.
• Lunghezza media: $0{,}4\cdot1+0{,}2\cdot3+0{,}15\cdot3+0{,}15\cdot3+0{,}05\cdot4+0{,}05\cdot4=2{,}3$ bit/simbolo.
• Entropia: $H=0{,}4\log_2\frac1{0{,}4}+\dots\approx2{,}246$ bit. Quindi $2{,}246\le2{,}3<3{,}246$ ✓.

Esempio (distribuzione diadica). $A=\frac12,\ B=\frac14,\ C=D=\frac18$: Huffman dà $A=0,\ B=10,\ C=110,\ D=111$, $\mathcal L=0{,}5\cdot1+0{,}25\cdot2+0{,}125\cdot3\cdot2=1{,}75=H(X)$: l'uguaglianza vale perché le probabilità sono potenze di $\frac12$ (è il codice 3 di prima).

Decodifica. Si legge un bit alla volta copiandolo in un buffer; se il buffer è una codeword si emette il simbolo e si svuota il buffer; altrimenti si legge il bit successivo. Con il codice $A=0,\ B=10,\ C=110,\ D=111$ la stringa $00101101111010$ si spezza in $0\,|\,0\,|\,10\,|\,110\,|\,111\,|\,10\,|\,10$, cioè $AABCDBB$.

Limite di Huffman. Se l'entropia è molto bassa ($H\to0$), Huffman diventa inefficace: poiché ogni simbolo ha almeno una codeword di 1 bit, $\mathcal L^*\ge1$ anche con $H\to0$: fino a un bit di overhead per simbolo. Inoltre non sfrutta la dipendenza statistica tra simboli consecutivi (lettere di un testo, luminanze di pixel vicini). Rimedio: la codifica a blocchi.

4. Codifica a blocchi

Si raggruppano i simboli in blocchi di $K$, che formano una nuova sorgente $X^K$ con alfabeto $\mathcal X^K$ di $M^K$ elementi. Per il teorema di Shannon applicato a $X^K$: $H(X^K)\le\mathcal L^*<H(X^K)+1$. Dividendo per $K$ si ottiene la lunghezza per simbolo: $$\frac{H(X^K)}K\le\mathcal L^*_s=\frac{\mathcal L^*}K<\frac{H(X^K)}K+\frac1K.$$ Due effetti:

1. il bit di overhead si ripartisce su $K$ simboli (costa $\frac1K$ per simbolo e tende a zero);
2. se i simboli sono dipendenti, $\frac{H(X^K)}K$ diminuisce (resta uguale a $H(X)$ solo per simboli indipendenti: $H(X^K)=K\,H(X)$).

Se $\frac{H(X^K)}K$ converge (come per segnali stazionari), il limite è il tasso entropico $\mathcal H(X)=\lim_{K\to\infty}\frac{H(X^K)}K\le H(X)$, con uguaglianza se e solo se i simboli sono indipendenti. Allora $\mathcal L^*_s\to\mathcal H(X)$: è il limite ultimo della codifica lossless.

Esempio (sorgente a 3 simboli). $P(a_1)=0{,}8,\ P(a_2)=0{,}02,\ P(a_3)=0{,}18$. Entropia $H=0{,}8157$ bit. Huffman sui singoli simboli: lunghezze $1,2,2$ e $\mathcal L=0{,}8+0{,}04+0{,}36=1{,}2$ bit/simbolo, 0,384 bit sopra l'entropia. Con le 9 coppie di simboli Huffman dà $\mathcal L=1{,}723$ bit per coppia, cioè $0{,}8614$ bit/simbolo: solo $0{,}045$ sopra l'entropia. Raggruppare a coppie ha quasi eliminato l'overhead.

Esempio (immagine binaria, dalle slide). Immagine binaria (una "T" nera su fondo bianco) con il 13,3% di pixel neri e l'86,7% bianchi. Le slide riportano: $K=1$: $H=0{,}586$ bit, Huffman 1 bit/pixel; $K=2$: $H(X_1,X_2)=1{,}022$ bit, ossia $0{,}511$ bit/pixel, Huffman $0{,}650$ bit/pixel; $K=4$: $H=1{,}533$ bit, ossia $0{,}383$ bit/pixel, Huffman $0{,}433$ bit/pixel. (Nota: con le probabilità indicate l'entropia dei singoli pixel è $0{,}566$ bit, non $0{,}586$: la differenza è probabilmente un refuso nelle slide.) Lezione: l'entropia per pixel cala (i pixel non sono indipendenti) e l'overhead di Huffman cala come $\frac1K$.

Costo. La complessità del codice di Huffman cresce esponenzialmente con $K$ (l'alfabeto ha $M^K$ simboli: da 3 a $3^2=9$ per la sorgente sopra, da 2 a $2^2$ e $2^4$ per l'immagine). Per questo, anche se conviene $K$ grande, non si usa.

5. Codifica aritmetica

La codifica aritmetica è subottima ma ha complessità lineare in $K$: per ogni nuovo simbolo servono un numero fisso di operazioni (due moltiplicazioni e due addizioni). Per un messaggio di $K$ simboli: $$H(X^K)\le\mathcal L_A<H(X^K)+2\ \Longrightarrow\ \mathcal H(X)\le\mathcal L_{A,s}<\frac{H(X^K)}K+\frac2K.$$ L'overhead (al più 2 bit) è per tutto il messaggio, non per simbolo: quindi tende a zero con $K$, senza costruire un codice per $M^K$ blocchi.

Come funziona. A ogni sequenza di simboli si associa un sottointervallo di $(0,1)$ la cui ampiezza è il prodotto delle probabilità dei simboli. L'intervallo $(0,1)$ si divide in sottointervalli di ampiezza pari alle probabilità dei simboli; si sceglie quello del primo simbolo e lo si suddivide di nuovo proporzionalmente; ogni nuovo simbolo restringe l'intervallo. La sequenza è codificata con il centro dell'intervallo finale scritto in binario, con tanti bit da rendere la precisione inferiore all'ampiezza.

Esempio (ACFD). Probabilità come sopra: $A$ in $[0;0{,}4)$, $B$ in $[0{,}4;0{,}6)$, $C$ in $[0{,}6;0{,}75)$, $D$ in $[0{,}75;0{,}9)$, $E$ in $[0{,}9;0{,}95)$, $F$ in $[0{,}95;1)$. Messaggio $ACFD$:

• $A$: $[0;0{,}4)$;
• $C$: dentro $A$ si prende la fetta $[0{,}6;0{,}75)$ dell'intervallo, cioè $[0{,}24;0{,}30)$ (ampiezza $0{,}06=0{,}4\cdot0{,}15$);
• $F$: la fetta $[0{,}95;1)$ di $[0{,}24;0{,}30)$ è $[0{,}297;0{,}300)$ (ampiezza $0{,}003$);
• $D$: la fetta $[0{,}75;0{,}9)$ di $[0{,}297;0{,}300)$ è $[0{,}29925;0{,}29970)$ (ampiezza $0{,}00045$). Servono $\lceil-\log_2 0{,}00045\rceil+1=13$ bit: $0{,}29947$ in binario inizia con $0100110010101$, e il numero a 13 bit $0{,}29944$ sta dentro l'intervallo. (L'informazione del messaggio è $-\log_2(0{,}4\cdot0{,}15\cdot0{,}05\cdot0{,}15)\approx11{,}1$ bit, quindi si spende circa 2 bit di overhead per tutto il messaggio. Huffman, per lo stesso messaggio, spende $1+3+4+3=11$ bit; ma la differenza non è sistematica e su messaggi lunghi vince l'aritmetica.)

Varianti. La codifica aritmetica adattativa cambia le probabilità man mano (le aggiorna uguale in codificatore e decodificatore, aumentando quelle dei simboli più frequenti). La codifica aritmetica basata sul contesto usa le probabilità condizionate $\Pr(x_n\mid x_{n-1},x_{n-2},\dots)$: è come un insieme di codificatori aritmetici, scelti dal contesto, e in media il tasso è l'entropia condizionata; raggiunge il tasso entropico con un modello più semplice da gestire. La codifica aritmetica adattativa basata sul contesto è lo stato dell'arte della codifica lossless per i segnali multimediali (CABAC in H.264 e HEVC).

6. Oltre Huffman e aritmetica: ZIP e ANS

Contesto storico: Huffman (1952) è la prima soluzione ottima ma con vincolo di bit interi; la codifica aritmetica (anni Settanta) raggiunge l'entropia ma è complessa e per anni è stata frenata da brevetti; gli algoritmi di Lempel-Ziv (LZ77, LZ78) cambiano paradigma.

• Codifica con dizionario (LZ, "zip"). Sostituisce stringhe di simboli ricorrenti con puntatori a occorrenze precedenti o a indici di un dizionario (costruito in modo ripetibile dal decodificatore). Più il file è grande, più il dizionario "impara". Pro: decompressione velocissima, nessuna tabella di probabilità da inviare, efficace con pattern lunghi (testo, codice sorgente). Contro: poco efficace su segnali multimediali grezzi (pixel e campioni audio raramente si ripetono in stringhe identiche senza una predizione a monte). LZW è alla base del formato GIF (1987); DEFLATE = ricerca di stringhe LZ77 più Huffman per i puntatori, è il cuore di ZIP, GZIP e delle immagini PNG.
• ANS (asymmetric numeral systems, 2013-14, di pubblico dominio): ha l'efficienza della codifica aritmetica (si avvicina al tasso entropico) con la velocità di Huffman. L'aritmetica restringe un intervallo reale (due variabili, divisioni e precisione alta); ANS fa crescere un solo numero intero $x$ con $x'\approx x/p_s$ per un simbolo di probabilità $p_s$, e quando $x$ diventa troppo grande ne scrive i bit meno significativi nel file. Due varianti: tANS (tabulata: macchina a stati finiti con tabelle precalcolate, nessuna moltiplicazione a runtime: erede di Huffman; usata in Zstandard e LZFSE) e rANS (con moltiplicazioni intere, parallelizzabile con SIMD e GPU: erede dell'aritmetica; usata in JPEG XL e nei videogiochi).

Le reti neurali (Autoencoderapprofondimento: non nel programma di Telecomunicazioni. Un autoencoder è una rete non supervisionata che impara a ricostruire il proprio ingresso passando per un collo di bottiglia: encoder $z=e(x)$ (dimensione bassa), decoder $\hat x=d(z)$, loss $|x-d(e(x))|^2$. Con attivazioni lineari equivale alla PCA; con non linearità impara rappresentazioni latenti più ricche (ipotesi del manifold). Varianti: sparse (penalità $\ell_1$ sulle attivazioni), denoising (ingresso corrotto, bersaglio pulito), convolutivi (inpainting). Anomaly detection: si addestra su dati normali e si segnala come anomalo ciò che ha errore di ricostruzione sopra una soglia. VAE: l'encoder produce media e deviazione standard di una gaussiana, il campione si ottiene con il trucco di riparametrizzazione $z=\mu+\sigma\odot\zeta$, $\zeta\sim\mathcal N(0,I)$, e la loss è errore di ricostruzione più KL verso $\mathcal N(0,I)$, con $KL=\frac12\sum(\mu^2+\sigma^2-1-\ln\sigma^2)$; il $\beta$-VAE pesa il KL con $\beta>1$ per rappresentazioni disaccoppiate. Cenno ai GAN.Autoencoder →, Reti neurali convolutive (CNN)approfondimento: non nel programma di Telecomunicazioni. Una rete convolutiva (CNN) sostituisce gli strati densi con filtri piccoli che scorrono sull'immagine: ogni neurone vede solo una patch locale (campo recettivo) e i pesi del filtro sono condivisi in tutta l'immagine, quindi i parametri non dipendono dalla dimensione dell'immagine ($K^2C_{in}C_{out}+C_{out}$ per strato) e si conserva l'informazione spaziale. Dimensione dell'uscita: $\lfloor(W-K+2P)/S\rfloor+1$. Pooling (max 2x2, stride 2) sottocampiona e dà invarianza locale; i filtri 1x1 riducono i canali; struttura tipica CONV+ReLU, POOL, ..., FLATTEN, FC, SOFTMAX, addestrata con cross-entropy e backpropagation. Tre strati 3x3 hanno il campo recettivo di un 7x7 con meno parametri e più non linearità (VGG). Architetture: LeNet, AlexNet (ReLU, dropout, data augmentation), VGG, GoogLeNet (moduli Inception), ResNet (blocchi residui $H(x)=F(x)+x$), EfficientNet. Nel lab: CNN su Fashion-MNIST (241 546 parametri) e su CIFAR-10 (122 570).Reti neurali convolutive (CNN) →) non sostituiscono la codifica entropica: fanno da predittori molto avanzati, che dal contesto passato producono una distribuzione di probabilità precisa per il simbolo corrente, poi passata a un codificatore aritmetico o ANS. Il decodificatore deve rieseguire la stessa rete per decodificare.

7. Exp-Golomb e codifica per categoria e ampiezza

Exp-Golomb. Si usa quando l'alfabeto è fatto di naturali o interi. Non si basa su un modello esplicito di probabilità (quindi non è ottimo) e si può usare senza conoscere la distribuzione; funziona bene solo se la probabilità di un numero decresce con il modulo.

Senza segno (uEG). Per $n=0$: $c_U(0)=$ "1". Altrimenti sia $s$ la scrittura binaria di $n+1$ con il minimo numero di bit, $b=\lfloor\log_2(n+1)\rfloor+1$; $c_U(n)$ è formato da $b-1$ zeri (leading zeros) seguiti da $s$.

Con segno (sEG). Si mappa l'intero $n$ nel naturale $m(n)=2n-1$ se $n>0$, $m(n)=-2n$ se $n\le0$ (positivi sui dispari, non positivi sui pari), poi si applica uEG: $c_S(n)=c_U(m(n))$.

Esempio: $n=8$: $n+1=9=1001_2$ (4 bit), quindi $b-1=3$ zeri: $c_U(8)=0001001$. Con segno: $m(8)=15$, $15+1=16=10000_2$ (5 bit), $c_S(8)=000010000$. Per i valori piccoli: $c_S(0)=1,\ c_S(1)=010,\ c_S(-1)=011,\ c_S(2)=00100,\ c_S(-2)=00101$.

Categoria e ampiezza (C/A), usata in JPEG: estende Exp-Golomb riducendo i bit dei numeri grandi a spese di quelli piccoli. Si definiscono 11 (o 12) categorie, con un opportuno codice a prefisso. La categoria di $n$ è $k=\lceil\log_2(|n|+1)\rceil$, cioè il numero di bit di $|n|$ scritto in binario: categoria 0 contiene solo $0$; categoria 1: $\pm1$; categoria 2: $\pm2,\pm3$; categoria 3: da $\pm4$ a $\pm7$; la categoria $k>0$ contiene i valori da $2^{k-1}$ a $2^k-1$ in modulo. Si emette il codice della categoria e poi $|n|$ su $k$ bit; se $n<0$ si complementa bit a bit la stringa (in JPEG: ogni 0 diventa 1 e viceversa; il primo bit dopo la categoria indica quindi il segno: 1 positivo, 0 negativo). Il fatto che la categoria dica quanti bit seguono rende il codice istantaneo.

Per $n=8$: $k=\lceil\log_2 9\rceil=4$; nella tabella standard JPEG delle categorie DC la categoria 4 ha codice $101$; $8=1000_2$; quindi $c_{CA}(8)=101\ 1000$ ("1011000", 7 bit). Per $n=-6$: categoria 3 (codice $100$), $6=110_2\to$ complemento $001$: "100001". (Le slide, in un punto, dicono "complemento a 2": nel codice del corso l'operazione è l'inversione bit a bit, complemento a 1.)

8. Codifica lossless predittiva

Se i dati presentano dipendenza statistica si può predire il simbolo corrente dai simboli già codificati (noti anche al decodificatore). Se la predizione è coerente con la natura dei dati, l'errore di predizione $Y(n)=X(n)-\hat X(n)$ ha piccola entropia (dati "sparsificati"), e si applica a $Y$ un qualunque codificatore entropico invece che a $X$. Il decodificatore ripete la stessa predizione e ricostruisce $X(n)=Y(n)+\hat X(n)$.

Esempio (immagine "house", 256 livelli). Entropia dei pixel $H(X)=7{,}056$ bit/pixel (quasi 8: i grigi sono quasi equiprobabili, nessuna compressione possibile con un codice sui singoli pixel).

• Predittore semplice (orizzontale): $\hat X(n)=X(n-1)$. Entropia dell'errore: $3{,}312$ bit/pixel.
• Predittore 2D adattivo. Per il pixel $X$, con $A$ a sinistra, $B$ sopra e $C$ in alto a sinistra (tutti già noti), si stima l'affidabilità della predizione orizzontale con $D_H=|C-B|$ e quella verticale con $D_V=|C-A|$: se $D_H<D_V$ si pone $\hat X=A$ (orizzontale), altrimenti $\hat X=B$ (verticale). (Nelle slide $D_H$ è scritto senza il valore assoluto e in una frase compare $C$ al posto di $B$: sono refusi; il codice della demo usa il valore assoluto e $B$.) Per la prima riga e la prima colonna si usa un valore di default, per esempio 128 o la mediana dell'immagine. Entropia dell'errore: $2{,}830$ bit/pixel.

(bit per pixel; i valori ZIP nelle due serie di slide differiscono leggermente, 4,003 e 3,77 sull'originale: dipende dalla versione del programma). Osservazioni:

• sull'originale Exp-Golomb è pessimo (11,3 bit, più di 8 bit non compressi) perché presuppone che i valori piccoli siano più probabili, il che non è vero per i grigi; Huffman raggiunge quasi l'entropia ($7{,}08$); ZIP fa meglio perché lavora su sequenze di pixel potenzialmente lunghe;
• sull'errore di predizione semplice, Exp-Golomb funziona molto meglio (l'ipotesi è ora vicina alla realtà), Huffman è vicino all'entropia, ZIP ancora meglio perché il modello predittivo è semplice;
• sull'errore di predizione avanzata i tre codici sono quasi equivalenti; con un predittore migliore (altre direzioni) le prestazioni crescerebbero ancora.

Morale: la compressione efficace non viene dal solo codificatore, ma dalla sparsificazione (predizione, trasformata, contesto) seguita da una codifica entropica.

Domande d'esame

1. Qual è il concetto dietro la codifica a blocchi? Traccia: il bit di overhead dei codici a prefisso ($\mathcal L<H+1$) si ripartisce su tutti gli elementi del blocco e la lunghezza per simbolo si avvicina all'entropia; inoltre per simboli non indipendenti (luminanze di pixel vicini) la codifica a blocchi sfrutta la correlazione, abbassando ulteriormente il limite (tasso entropico $\le H$).

2. Il minimo tasso di codifica senza perdite per un codice a prefisso è (a) $\ge$ l'entropia, (b) $\le$ l'entropia, (c) sempre un numero intero di bit? Traccia: (a), è il teorema di Shannon: $H\le\mathcal L^*<H+1$; $\mathcal L$ non è mai intero in generale (è una media).

3. Sorgente con probabilità $0{,}07;\,0{,}25;\,0{,}11;\,0{,}12;\,0{,}31;\,0{,}14$: calcolare l'entropia e la lunghezza media del codice di Huffman. Traccia: $H\approx2{,}4068$ bit; Huffman dà lunghezze $3,2,3,3,2,3$ e $\mathcal L=3\cdot0{,}07+2\cdot0{,}25+3\cdot0{,}11+3\cdot0{,}12+2\cdot0{,}31+3\cdot0{,}14=2{,}44$ bit; nessun codice a prefisso può scendere sotto 2,40.