Cosa Shannon Ha Chiamato Informazione
Shannon ha definito l'informazione misurando la sorpresa. Un messaggio con probabilità p contiene:
I = −log₂(p) bit
Un evento certo (p = 1) contiene 0 bit — nessuna sorpresa, nessuna informazione. Un evento raro (p = 1/1024) contiene 10 bit.
Hamming immediatamente segnala il problema: questa è una formula per misurare una quantità, non una definizione del concetto. Misura la sorpresa simile a quella di una macchina, non il significato umano. Uno studente che conosce già la risposta a una domanda riceve 0 bit dalla risposta — indipendentemente da quanto importante sia la risposta per altri.
La formula si applica bene ai sistemi telefonici, radio, computer. Si applica male alla comunicazione umana, alla biologia, o al significato. Il nome preferito di Hamming: 'Teoria della Comunicazione', non 'Teoria dell'Informazione.'
Entropia
Per un alfabeto di q simboli con probabilità p₁, p₂, ..., p_q, l'informazione media per simbolo è l'entropia:
H = −Σᵢ pᵢ log₂(pᵢ)
H raggiunge il suo massimo quando tutte le probabilità sono uguali: H_max = log₂(q) bit. Qualsiasi distribuzione non uniforme ha entropia più bassa.
Calcolo dell'Entropia
Entropia binaria: una sorgente con due simboli, P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) = 0 quando p = 0 o p = 1 (completamente prevedibile). H(p) = 1 bit quando p = 0.5 (completamente imprevedibile).
La Disuguaglianza di Gibbs & la Codifica Senza Rumore
Disuguaglianza di Gibbs: per qualsiasi due distribuzioni di probabilità p = {pᵢ} e q = {qᵢ}:
−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)
con uguaglianza solo quando p = q. Questo poggia sul fatto elementare che ln(x) ≤ x − 1 per tutti gli x > 0, con uguaglianza a x = 1.
Conseguenza: l'entropia H(p) è massimizzata quando tutti i simboli hanno la stessa probabilità. Per q simboli: H_max = log₂(q).
Teorema della codifica senza rumore: data un codice univocamente decodificabile, la disuguaglianza di Kraft richiede Σ 2^(−lᵢ) ≤ 1 dove lᵢ è la lunghezza del codice per il simbolo i. Dalla disuguaglianza di Gibbs, la lunghezza media del codice L = Σ pᵢ lᵢ soddisfa:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
Non puoi fare meglio dell'entropia in media. La codifica di Huffman raggiunge L < H + 1.
Capacità del Canale
Un canale simmetrico binario (BSC) capovolge ogni bit in modo indipendente con probabilità di errore Q = 1 − P. La capacità del BSC — il massimo tasso di informazione affidabile — è:
C = 1 + P log₂(P) + Q log₂(Q) = 1 − H(Q)
dove H(Q) = −Q log₂(Q) − (1−Q) log₂(1−Q) è l'entropia binaria del tasso di errore.
A Q = 0 (nessun errore): C = 1 bit/trasmissione (canale perfetto). A Q = 0.5 (capovolgimento casuale): C = 0 (il canale non porta informazione). A Q = 1 (tutti i bit si capovolgono): C = 1 (sai esattamente cosa ha inviato il mittente, basta capovolgere tutto indietro).
C misura il tasso massimo R al quale puoi trasmettere con probabilità di errore arbitrariamente piccola. Se R < C, tali codici esistono. Se R > C, non esistono — nessun codice può battere la capacità.
Calcolo della Capacità del Canale
Con P = 0.9 (tasso di errore del 10%, Q = 0.1):
C = 1 + 0.9 log₂(0.9) + 0.1 log₂(0.1)
log₂(0.9) ≈ −0.152, log₂(0.1) ≈ −3.322
C ≈ 1 + 0.9×(−0.152) + 0.1×(−3.322) = 1 − 0.137 − 0.332 ≈ 0.531 bit/trasmissione
Cosa Dimostra il Teorema
Teorema fondamentale di Shannon: per qualsiasi tasso R < C, esistono codici di lunghezza di blocco n (con n → ∞) che raggiungono una probabilità di errore P_E → 0.
La dimostrazione usa un argomento sorprendente: codici casuali. Invece di costruire un codice specifico, Shannon ha fatto la media su tutti i possibili libri di codice casuali (codifica per capovolgimento di moneta). Ha mostrato che l'errore medio su tutti i libri di codice è piccolo. Se la media è piccola, almeno un codice raggiunge un errore piccolo.
Analisi basata su sfere: il mittente sceglie messaggio aᵢ → sfera di raggio n(Q + ε₂) intorno a aᵢ nello spazio binario n-dimensionale. Per n grande, la parola ricevuta bⱼ giace all'interno di questa sfera con alta probabilità. Il ricevitore decodifica verso la parola di codice la cui sfera contiene bⱼ.
Quattro casi determinano la probabilità di errore P_E:
``
aᵢ nella sfera altro aⱼ nella sfera risultato
sì no corretto (nessun errore)
sì sì ambiguo → errore
no sì decodifica errata → errore
no no al di fuori di tutte le sfere → errore
``
Il limite su P_E risulta essere: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) per d e ε₂ opportunamente scelti. Scegliendo ε₂ in modo che H(Q+ε₂) < C rende l'esponente negativo. Per n grande, il secondo termine → 0.
La Natura Esistenziale del Teorema
Hamming era preciso su cosa il teorema fa e non fa.
Cosa dimostra: la comunicazione affidabile al tasso R < C è possibile, in linea di principio, per n sufficientemente grande.
Cosa non fornisce: costruzione esplicita del codice. Un codice casuale di lunghezza n sufficientemente grande per avvicinarsi alla capacità ha un libro di codice di dimensione M × n bit, dove sia M che n sono astronomicamente grandi. Non puoi immagazzinarlo o calcolarlo.
Codici di correzione degli errori vs. Shannon: i codici di correzione degli errori (Hamming, Reed-Solomon, turbo, LDPC) forniscono costruzioni esplicite e calcolabili. Sacrificano una certa distanza dalla capacità in cambio di codificatori & decodificatori pratici. Man mano che n cresce e più errori vengono corretti per blocco, i codici pratici possono avvicinarsi strettamente alla capacità.
L'esempio dei satelliti spaziali: Voyager e Pioneer hanno usato potenti codici di correzione degli errori per comunicare a miliardi di miglia su 5–20 watt di potenza. Lunghe lunghezze di blocco hanno permesso di correggere più errori per blocco, spingendosi verso la capacità nonostante il rumore enorme dalla distanza.
Valutazione Critica
Hamming ha chiuso il Capitolo 13 con una critica più ampia delle definizioni nella scienza. La formula dell'informazione di Shannon misura la sorpresa della macchina, non il significato umano. Il nome 'Teoria dell'Informazione' fa promesse eccessive. L'analogia della rete da pesca: un pescatore che cattura solo pesci più grandi della maglia della rete conclude che non ci sono pesci più piccoli. I limiti dello strumento diventano i vincoli apparenti del mondo.
Il Problema con le Definizioni
Hamming ha usato la teoria dell'informazione per fare un punto metodologico più ampio: le definizioni iniziali determinano cosa trovi, più di quanto la maggior parte delle persone realizzi.
Shannon ha scelto di definire 'informazione' come sorpresa. Quella definizione è stata produttiva per l'ingegneria della comunicazione. Ma ha importato uno scopo specifico — sistemi simili a macchine — in una parola ('informazione') che suggerisce applicabilità universale.
L'analogia della rete da pesca: una rete con maglie di 6 pollici cattura solo pesci grandi. Il pescatore conclude: la dimensione minima dei pesci è 6 pollici. La conclusione riflette lo strumento, non il mondo.
Il QI come parallelo: un test progettato per misurare 'intelligenza', calibrato per produrre una distribuzione normale, poi usato per definire l'intelligenza. Lo strumento plasma il concetto.
La raccomandazione di Hamming: ogni volta che incontri una definizione, chiediti (1) quanto è d'accordo con la tua intuizione precedente? (2) quanto distorce? (3) sotto quali condizioni è stata formulata? (4) è stata applicata ora sotto condizioni diverse?