Sorgente → Canale: Codifica a Due Fasi
Il Capitolo 10 di Hamming inizia con il modello di comunicazione di Shannon, che si applica a ogni sistema che trasmette informazioni: chiamate telefoniche, radio, dischi rigidi, replicazione del DNA, memoria del computer.
L'Architettura a Due Fasi
Fase 1: Codifica della sorgente (compressione). Converti il messaggio di sorgente in una rappresentazione compatta. Obiettivo: rimuovere la ridondanza nativa della sorgente. Il codice Morse fa questo: le lettere comuni ottengono codici brevi, le lettere rare ottengono codici lunghi.
Fase 2: Codifica del canale (protezione dagli errori). Aggiungi ridondanza controllata adattata alle caratteristiche di rumore del canale. Una linea telefonica rumorosa ha bisogno di più ridondanza di un cavo in fibra ottica. Le due fasi si disaccoppiano: ottimizza ognuna indipendentemente per il suo compito.
L'interfaccia comune tra le due fasi — un flusso di bit standardizzato — significa che qualsiasi sorgente può abbinarsi a qualsiasi canale. Questa modularità è l'intuizione architettonica chiave di Shannon.
Archiviazione come comunicazione. Hamming nota che inviare un messaggio nello spazio (trasmissione) e inviarlo nel tempo (archiviazione) usano lo stesso modello. Un'unità di backup è un canale rumoroso nel tempo.
Il Ruolo del Rumore
Il modello di Shannon fa un'assunzione radicale: il rumore è inevitabile. Ogni canale, ogni supporto di archiviazione, ogni circuito di commutazione introduce una certa probabilità di errore. La domanda non è 'come eliminiamo il rumore?' ma 'come recuperiamo il messaggio originale nonostante il rumore?'
Questo contrasta con la fisica classica, dove il rumore entra come un ripensamento (il principio di indeterminazione). Shannon tratta il rumore come la condizione fondazionale — tutta la teoria si costruisce su di essa.
Per ora, il Capitolo 10 si concentra sul caso senza rumore: codifica della sorgente senza errori. Il problema della codifica del canale (correzione degli errori) attende i capitoli successivi.
Quando Puoi Decodificare in Modo Univoco?
Per un codice a lunghezza variabile, il ricevitore deve decodificare un flusso di bit in modo univoco. Hamming illustra con un codice a 4 simboli che non supera questo test, quindi introduce la soluzione: codici privi di prefisso.
Condizione Priva di Prefisso
Un codice è privo di prefisso (o istantaneo) se nessun codeword è un prefisso di qualsiasi altro codeword. Dato un flusso di bit ricevuto, sai che un simbolo è terminato nel momento in cui raggiungi una foglia nell'albero di decodifica — nessun lookahead richiesto.
Esempio di codice privo di prefisso per {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Verifica: 0 non è un prefisso di 10, 110, o 111. 10 non è un prefisso di 110 o 111 (10 seguito da più bit dà 100... o 101..., nessuno dei quali inizia con 110 o 111). Il codice si qualifica.
La procedura di decodifica: segui l'albero, ramifica su ogni bit in arrivo, emetti il simbolo quando raggiungi una foglia, ritorna alla radice.
La Disuguaglianza di Kraft
Per ogni codice binario privo di prefisso con lunghezze di codeword l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
L'uguaglianza vale quando il codice è completo (le foglie ricoprono l'albero binario completo senza spazi). Questa è una condizione necessaria: nessun codice privo di prefisso può violarla. Al contrario, per qualsiasi insieme di lunghezze soddisfacenti la disuguaglianza di Kraft, esiste un codice privo di prefisso.
Applicazione della Disuguaglianza di Kraft
Dato le lunghezze di codeword, verifica Kraft: Σ 2^(−l_i) ≤ 1.
Per {s1=0, s2=10, s3=110, s4=111}: le lunghezze sono 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Entropia di Shannon
La lunghezza di codice media di un codice a lunghezza variabile: L = Σ p_i · l_i, dove p_i è la probabilità del simbolo s_i e l_i è la sua lunghezza di codice.
Quanto corta può diventare L? La risposta di Shannon: non inferiore all'entropia della sorgente.
Entropia di Shannon: H = −Σ p_i · log₂(p_i) (unità: bit/simbolo)
L'entropia misura l'informazione media per simbolo. Alta entropia significa che i simboli sono approssimativamente equiprobabili (massima imprevedibilità). Bassa entropia significa che alcuni simboli dominano (alta prevedibilità, più comprimibile).
Teorema della Codifica Senza Rumore
Per qualsiasi codice privo di prefisso, H(sorgente) ≤ L ≤ H(sorgente) + 1.
Nessun codice può battere l'entropia. La codifica di Huffman (prossimo capitolo) raggiunge il limite superiore: L < H + 1. Per codici a blocchi su n simboli, il limite si restringe: H ≤ L/n < H + 1/n.
L'entropia è anche il limite teorico di compressione: non puoi comprimere una sorgente sotto H bit per simbolo senza perdere informazioni.
Calcolo dell'Entropia
Esempio: 4 simboli con probabilità p = [1/2, 1/4, 1/8, 1/8].
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bit/simbolo
E il codice di Huffman {0, 10, 110, 111} raggiunge L = 1.75 = H esattamente.
Perché l'Entropia È un Limite Inferiore
Il limite inferiore del teorema della codifica senza rumore non è solo una formula — riflette qualcosa di profondo sull'informazione: non puoi comprimere ciò che è già massimamente imprevedibile.
Quando tutti i simboli sono equiprobabili (distribuzione uniforme), l'entropia H = log₂(n) per n simboli. Un codice a blocchi di lunghezza log₂(n) bit raggiunge esattamente H. Nessun codice può fare di meglio.
Quando un simbolo domina (diciamo, p(A) = 0.99, p(B) = 0.01), H è piccolo — vicino a 0. Un codice a lunghezza variabile può assegnare ad A un codice molto breve, codificando il flusso molto efficientemente.
La conclusione pratica: guadagni di compressione grandi esistono solo quando le probabilità dei simboli differiscono sostanzialmente. Se la sorgente è già 'uniforme' (casuale), la codifica di Huffman non guadagna nulla.