Se il canale introduce errori, come proteggere il messaggio? La risposta è aggiungere ridondanza strutturata - un codice correttore d'errore che consente al ricevitore di rilevare e correggere gli errori in modo deterministico. Il fondamento matematico è la distanza di Hamming, introdotta da Richard Hamming nel 1950: la distanza fra due stringhe binarie è il numero di posizioni in cui differiscono. Due parole codice distanti almeno 2t + 1 possono correggere fino a t errori - il ricevitore infatti sceglie il messaggio più vicino a quello ricevuto (decoding a distanza minima). Questo articolo introduce i bound teorici che limitano l'efficienza di ogni codice: il bound di Hamming (sphere-packing, limite massimo di codeword) e il bound di Singleton (relazione fra lunghezza, dimensione e distanza). Capire questi bound è cruciale per riconoscere quando un codice è perfetto o ottimale, e dove stanno i codici reali (Hamming, Reed-Solomon, turbo) in questo paesaggio teorico. Il tema centrale è il trade-off fra ridondanza e correzione: ogni bit di ridondanza consente di correggere più errori, ma riduce il tasso di codifica - e il bound di Shannon dalla lezione precedente definisce il limite ultimo di questo trade-off.
Contesto storico e formalizzazione
Richard Hamming (1950) sviluppa il concetto di distanza e di codice perfetto per risolvere un problema pratico: il calcolatore Bell Model II introduceva errori nei dati memorizzati su tamburi magnetici. Hamming crea il codice Hamming [7,4]: 4 bit di informazione + 3 bit di parità, che consente di correggere 1 errore qualsiasi. La scoperta chiave è che la minima distanza fra due codeword determina quanti errori si possono correggere. Negli anni '50 e '60, Plotkin, Singleton e altri sviluppano bound teorici che delimitano l'efficienza di qualsiasi codice. Nel 1960, Irving Reed e Gustavo Solomon inventano i codici Reed-Solomon (RS), che raggiungono il bound di Singleton ed sono usati oggi in ogni sistema critico (backup, comunicazioni spaziali, QR code, streaming video). Questi codici rappresentano il punto d'incontro fra teoria pura e applicazione pratica.
Outline dell'articolo
- La distanza di Hamming: definizione e interpretazione geometrica
- Sfere di Hamming e numero di codeword
- Codici a blocchi lineari: matrici generatrici e di controllo di parità
- Il bound di Hamming (sphere-packing bound)
- Il bound di Singleton e i codici MDS (Maximum Distance Separable)
- Esempi concreti: Hamming [7,4], Reed-Solomon [255,223]
La distanza di Hamming: definizione e interpretazione geometrica
La distanza di Hamming fra due stringhe binarie di lunghezza n, indicate x e y, è il numero di posizioni in cui differiscono:
d_H(x, y) = |{i : x_i ≠ y_i}|
Esempio: x = 1011, y = 1101. Differiscono in posizione 1 e 3, quindi d_H(x, y) = 2.
La distanza di Hamming gode delle proprietà metriche:
- Non-negatività:
d_H(x, y) ≥ 0, con uguaglianza iffx = y - Simmetria:
d_H(x, y) = d_H(y, x) - Disuguaglianza triangolare:
d_H(x, z) ≤ d_H(x, y) + d_H(y, z)
Interpretazione geometrica: lo spazio di tutte le stringhe binarie di lunghezza n ha 2^n punti. Una "sfera" di raggio t intorno a un punto c contiene tutti i punti a distanza al massimo t da c. Il numero di stringhe a distanza esattamente j è binom(n, j) (scegliamo quali j posizioni flippare), quindi il numero totale di stringhe in una sfera di raggio t è:
V(n, t) = sum_{j=0}^{t} binom(n, j)
Questa è la sfera di Hamming - il "volume" misura quante stringhe corregge il codice.
Sfere di Hamming e numero di codeword
Se un codice ha distanza minima d_min = 2t + 1 (cioè la minima distanza fra due codeword qualsiasi è 2t + 1), allora ogni codeword può correggere fino a t errori. Perché? Perché se ricevi una stringa y a distanza ≤ t da un codeword c, allora y non è a distanza ≤ t da nessun altro codeword c' (altrimenti, per la disuguaglianza triangolare, d_H(c, c') ≤ d_H(c, y) + d_H(y, c') ≤ 2t, contraddicendo d_min = 2t + 1). Quindi il decoding a distanza minima - scegli il codeword più vicino - corregge sempre l'errore.
Se il codice ha M codeword (informazione k = log2(M) bit) e ogni sfera di raggio t ha volume V(n, t), allora le M sfere non possono sovrapporsi:
M * V(n, t) ≤ 2^n
Riarrangiando: M ≤ 2^n / V(n, t), ovvero il numero di codeword è limitato dal rapporto fra lo spazio totale e il volume della sfera. Questo dà il bound di Hamming che affrontiamo dopo.
Codici a blocchi lineari: matrici generatrici e di controllo di parità
Un codice lineare [n, k] è un sottospazio lineare di F_2^n (binario n-dimensionale) di dimensione k. Contiene esattamente 2^k codeword. Si codifica moltiplicando il messaggio (vettore k-dimensionale) per una matrice generatrice G (k × n):
c = m * G
dove m è il messaggio, c è il codeword, e il prodotto è in algebra lineare su F_2 (modulo 2).
La decodifica usa una matrice di controllo di parità H (n-k) × n) tale che G * H^T = 0 (tutte le codeword soddisfano c * H^T = 0):
r * H^T = syndrome s = (codeword has errors) ? non-zero : zero
Se s ≠ 0, il ricevuto r ha errori; il syndrome individua quale bit è stato flippato (nel caso di codici perfetti come Hamming [7,4]).
Il bound di Hamming (sphere-packing bound)
Il bound di Hamming (anche detto Hamming bound o sphere-packing bound) afferma: per un codice [n, k] che corregge t errori,
2^k ≤ 2^n / V(n, t) = 2^n / sum_{j=0}^{t} binom(n, j)
Riarrangiando logaritmicamente:
k ≤ n - log2(sum_{j=0}^{t} binom(n, j))
Un codice è perfetto se raggiunge l'uguaglianza: allora le sfere di Hamming ricoprono esattamente lo spazio F_2^n senza sovrapporsi. Il codice Hamming [7,4] è perfetto: 2^4 = 16 codeword, raggio t = 1, volume sfera V(7,1) = 1 + 7 = 8, totale 16 * 8 = 2^7 = 128 - ricopertura perfetta.
Il bound di Singleton e i codici MDS
Il bound di Singleton afferma che la distanza minima d_min di un codice [n, k] soddisfa:
d_min ≤ n - k + 1
Un codice raggiunge il bound se d_min = n - k + 1 - è detto Maximum Distance Separable (MDS). Gli MDS sono ottimali per il trade-off fra distanza e tasso di codifica R = k/n.
I codici Reed-Solomon sono MDS: per lunghezza n = 2^m - 1 e dimensione k, hanno d_min = n - k + 1. Esempio: Reed-Solomon [255, 223] ha d_min = 255 - 223 + 1 = 33, corregge fino a t = 16 errori e raggio di burst (errori contigui) fino a 16 byte.
Comparazione di bound: Hamming limita il numero di codeword (assorbimento dello spazio), mentre Singleton limita la distanza (efficienza della correzione). Per il Hamming [7,4]: n - k + 1 = 7 - 4 + 1 = 4, ma la distanza reale è 3 (un errore, non perfetto per Singleton). Per il Reed-Solomon [255, 223]: il bound di Singleton è raggiunto, il codice è perfetto per quel trade-off.
Perché t = floor((d-1)/2): ragionamento geometrico
La formula della numero di errori correggibili t = floor((d_min - 1) / 2) emerge dalla geometria delle sfere di Hamming. Immagina lo spazio binario a n dimensioni come una griglia: ogni punto è una stringa di n bit, distanza fra due punti è il numero di coordinate in cui differiscono (distanza di Hamming).
Una sfera di raggio t intorno a un codeword c è l'insieme di tutte le stringhe a distanza ≤ t da c. Se il canale introduce fino a t errori, il ricevuto r cade dentro la sfera di c.
Condizione per correggere t errori: le sfere di raggio t intorno a due codeword diversi NON devono sovrapporsi. Se due codeword c e c' distano d_min, la distanza minima fra i loro centri è d_min. Le sfere di raggio t intorno a ciascuno non sovrappongono se:
t + t < d_min → 2t < d_min → t < d_min / 2
Poiché t deve essere intero, t = floor((d_min - 1) / 2). Visualizzazione: se d_min = 5, allora t = 2. Due codeword a distanza 5 hanno sfere di raggio 2 che non sovrappongono: la distanza fra centri è 5, e 2+2 = 4 < 5 ✓.
Limite di rilevazione: Se invece vuoi solo rilevare errori (non correggerli), basta che una stringa ricevuta a distanza ≤ d_min - 1 da un codeword non sia un altro codeword. Condizione: d_min ≥ 2 (distanza almeno 2). Quindi rilevazione è più facile di correzione: puoi rilevare d_min - 1 errori, ma correggi solo floor((d_min - 1) / 2).
Codici perfetti e la rarità dei codeword
Un codice è perfetto se raggiunge l'uguaglianza nel bound di Hamming: le sfere di raggio t intorno ai codeword ricoprono esattamente lo spazio F_2^n senza sovrapporsi. Ogni stringa ricevuta è a distanza ≤ t da esattamente un codeword - decoding a distanza minima è sempre corretto, senza ambiguità.
I codici perfetti sono straordinariamente rari. I soli codici binari perfetti sono:
- Codici Hamming [2^m - 1, 2^m - m - 1]: correggono 1 errore (t=1). Esempi: [7,4], [15,11], [31,26]. Dimostrato perfetto da Shannon.
- Codice Golay [23,12]: corregge 3 errori (t=3). Usato in comunicazioni spaziali NASA (Voyager).
- Codici triviali: il codice a ripetizione [n, 1] (trasmetti il messaggio n volte), codice identità [n, n] (nessuna ridondanza).
Non esistono altri. Questo significa: oltre Hamming, Golay e triviali, OGNI codice binario è "sub-perfetto" - spreca spazio, ha sfere sovrapposte. La maggior parte dei codici pratici (Reed-Solomon, turbo, LDPC) sacrifica perfezione per altri vantaggi: distanza grande, decodifica veloce, performance pratica sotto rumore reale.
Esempi concreti: Hamming [7,4], Reed-Solomon [255,223]
Hamming [7,4]: costruzione esplicita
Il codice Hamming [7,4] codifica 4 bit di informazione in 7 bit di codeword (3 bit di parità). Costruzione con la matrice generatrice G (4 × 7):
G = [1 0 0 0 1 1 0]
[0 1 0 0 1 0 1]
[0 0 1 0 0 1 1]
[0 0 0 1 1 1 1]
Questa è in forma sistematica: le prime 4 colonne sono la matrice identità (i bit di informazione), le ultime 3 sono i bit di parità calcolati dalle combinazioni dei 4 bit.
Esempio numerico completo - Codifica: Supponi di voler codificare il messaggio m = [1, 0, 1, 0] (4 bit di informazione).
c = m * G = [1, 0, 1, 0] * G
= 1*(1,0,0,0,1,1,0) + 0*(0,1,0,0,1,0,1) + 1*(0,0,1,0,0,1,1) + 0*(0,0,0,1,1,1,1)
= (1,0,0,0,1,1,0) + (0,0,1,0,0,1,1)
= (1,0,1,0,1,0,1) (modulo 2: 1+1=0 nella posizione 5)
Codeword trasmesso: c = 1010101 (7 bit).
Decodifica - canale senza errori: Se il ricevitore riceve r = 1010101 (identico a c), calcola il syndrome usando la matrice di parità H:
H = [1 1 0 1 0 0 0]
[1 0 1 1 0 1 0]
[0 1 1 1 0 0 1]
Syndrome: s = r * H^T (mod 2). Se r = c, il syndrome è zero (il codeword è valido).
Decodifica - con errore singolo: Supponi che il canale introduca un errore in posizione 3: ricevi r = 1011101 (l'1 in posizione 3 è diventato 0 e poi flippato di nuovo, oppure un altro errore). Calcola il syndrome:
s = r * H^T = 1011101 * [1 1 0]^T (partial - usando prima riga H^T)
[1 0 1]^T
[0 1 1]^T
[1 1 1]^T
[0 0 0]^T
[0 1 0]^T
[0 0 1]^T
= 1*1 + 0*1 + 1*0 + 1*1 + 1*0 + 0*0 + 1*0 = 2 mod 2 = 0 (prima component)
= 1*1 + 0*0 + 1*1 + 1*1 + 1*0 + 0*1 + 1*0 = 3 mod 2 = 1 (seconda component)
= 1*0 + 0*1 + 1*1 + 1*1 + 1*0 + 0*0 + 1*1 = 3 mod 2 = 1 (terza component)
→ s = [0, 1, 1] = 3 (numero binario)
Il syndrome 3 indica che l'errore è in posizione 3. Flip il bit 3 di r: r' = 1010101 (corretto).
Perché il syndrome identifica la posizione: Ogni colonna della matrice H è un numero binario unico da 0 a 7 (per [7,4]). Se il canale cambia il bit in posizione j, il syndrome è esattamente il numero binario della colonna j di H. Questa è la magia del codice di Hamming: il syndrome è la "firma" dell'errore.
Proprietà di Hamming [7,4]: Distanza minima d_min = 3 (può correggere 1 errore, rilevare 2). È perfetto: le 2^4 = 16 sfere di raggio 1 ricoprono esattamente 2^7 = 128 stringhe (16 * 8 = 128). Tasso di codifica R = 4/7 ≈ 0.571 (57% di ridondanza).
Reed-Solomon [255, 223]: Usato in trasmissioni spaziali (NASA), backup magnetici, QR code. Opera su alfabeto di 256 simboli (1 byte). Corregge fino a 16 errori di byte (non bit). La matrice generatrice è costruita su un campo di estensione (polinomi su GF(2^8)), non su F_2 ordinario. Implementazione: FFT veloce (FFT-based polynomial multiplication), costo O(n log n).
Trade-off reasoning
Ho scelto di presentare il bound di Hamming prima del bound di Singleton perché il primo è intuitivo (geometrico: sfere non sovrapposte) e il secondo è più algebrico-astratto. I codici reali operano fra questi bound: Hamming [7,4] è perfetto per Hamming ma non MDS; Reed-Solomon è MDS ma non perfetto per Hamming (le sfere sovrappongono). La scelta del codice dipende dall'applicazione: se lo spazio è limitato (memoria, larghezza di banda) e vuoi la massima distanza, MDS (Reed-Solomon); se vuoi il decodaggio veloce (syndrome decoding), perfetto (Hamming).
Connessioni avanzate
Rilevazione vs Correzione in rete: Nel contesto di reti digitali, non sempre conviene correggere ogni errore localmente. Una strategia alternativa è: rilevare l'errore (con un codice a distanza minima d ≥ 2), e richiedere la ritrasmissione del pacchetto (ARQ - Automatic Repeat reQuest). Vantaggi: (i) il codice ha meno ridondanza (richiede solo d ≥ 2, non d = 2t+1); (ii) il ricevitore non ha il costo computazionale di correzione iterativa. Svantaggi: (i) latenza aumentata (attesa ritrasmissione); (ii) larghezza di banda ulteriore per il feedback. In pratica: comunicazioni spaziali (lontane, uno-via) usano correzione (non è possibile ritrasmettere); reti terrestri a bassa latenza (Ethernet, Wi-Fi) usano rilevazione + ARQ. Il trade-off è fra ridondanza statica (correzione) e dinamica (ritrasmissione).
Turbo code e LDPC: Realizzano performance vicina alla capacità di Shannon attraverso iterative decoding. Il syndrome diventa la chiave per grafo fattoriale. Non geometrici come Hamming, ma algebrici e randomizzati.
BCH (Bose-Chaudhuri-Hocquenghem): Estensione dei codici Hamming che corregge multiple errori (non solo 1). Usati in memoria flash (SSD), dischi ottici.
Concatenated code: Combine due codici (es. outer Reed-Solomon + inner convolutional) per raggiungere threshold di performance con complessità gestibile.
Quantum error correction: Estende la teoria di Hamming ai qubit. La distanza è ancora il parametro critico, ma la ridondanza è su stati quantistici.
Trabocchetti e errori comuni
- Confondere distanza minima con numero di errori correggibili. Se
d_min = 5, correggit = (d_min - 1) / 2 = 2errori, non 5. La formula esatta èt = floor((d_min - 1) / 2). - Pensare che il bound di Hamming sia sempre raggiunto. Solo i codici perfetti lo raggiungono (Hamming, Golay, triviali). La maggior parte dei codici è "sub-perfetto".
- Applicare bound di Singleton a codici non-binari male. Il bound vale per qualsiasi alfabeto; per alfabeto q-ario,
d_min ≤ n - k + 1rimane esatto. - Dimenticare la modulo 2 nei calcoli booleani. Algebra lineare su
F_2non è algebra ordinaria:1 + 1 = 0. - Confondere tasso di codice con capacità del canale. Il tasso
R = k/nè la frazione di bit di informazione; la capacità C è il massimo tasso affidabile (dal secondo teorema).R < Cè necessario per affidabilità, ma non è sufficiente senza codifica.
Esercizi avanzati
- Sfera di Hamming: Calcola il volume della sfera di raggio 2 per n = 10. (Risposta: binom(10,0) + binom(10,1) + binom(10,2) = 1 + 10 + 45 = 56)
- Hamming [7,4] decodifica: Ricevi r = 1010101. Calcola il syndrome s = r * H^T (usando la H data sopra). Qual è la posizione dell'errore?
- Bound di Hamming: Un codice binario deve correggere 2 errori (t = 2) su lunghezza n = 15. Qual è il massimo k per cui il bound di Hamming è soddisfatto?
- MDS e Singleton: Un codice [20, 15] è MDS? (Esatto d_min = 20 - 15 + 1 = 6, che è il bound di Singleton.)
- Implementazione Reed-Solomon (simulazione): Usa la libreria Python `reedsolo` (o simile) per codificare un messaggio, introdurre errori, decodificare e misurare la capacità di correzione.
Bibliografia essenziale
- T. M. Cover, J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006. (Capitoli 10-13: Block Codes)
- C. E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, 1948.
- R. Hamming, "Error Detecting and Error Correcting Codes", Bell System Technical Journal, 1950.
- S. Lin, D. J. Costello, Error Control Coding: Fundamentals and Applications, 2nd ed., Pearson, 2004. (Standard industriale)
- I. Reed, G. Solomon, "Polynomial Codes over Certain Finite Fields", Journal of the Society for Industrial and Applied Mathematics, 1960.
- B. Vasic, A. Gabidulin, "Classical and Quantum Error Correction Codes", in Handbook of Coding Theory, Elsevier, 1998.
Prerequisiti tecnici
- Algebra lineare su campi finiti
F_2eGF(2^m)(opzionale) - Polinomi e aritmetica modulo primi (per Reed-Solomon)
- Combinatoria e binomiali
- Probabilità discreta (dal primo articolo della serie)
- Python: NumPy per algebra lineare, librerie dedicate (reedsolo, galois)
Risorse correlate e link interni
- Indice serie Teoria dell'Informazione
- Precedente: Canale rumoroso e capacità di Shannon
- Prossimo: Compressione con perdita e rate-distortion
- Correlato: Entropia e informazione mutua
- Sezione Università - Appunti e articoli didattici
- Wikipedia - Hamming Distance
Articolo pubblicato 2026-10-02, livello graduate, riferimento Cover & Thomas 2006, Hamming 1950 e Reed-Solomon 1960.
Commenti
Caricamento commenti...
Accedi per commentare