Bell Labs, 1947
Richard Hamming si unì ai Bell Telephone Laboratories nel 1946. I computer a relè lì funzionavano solo nei giorni feriali, quando i tecnici potevano riavviarli dopo gli errori. Nei fine settimana, le macchine si fermavano ogni volta che qualcosa andava male, lasciando i lavori in coda fino al lunedì.
Hamming era furioso. 'Se la macchina può rilevare un errore,' pensò, 'perché non può localizzarlo e correggerlo?' Questa frustrazione, combinata con una profonda familiarità con l'aritmetica binaria e i controlli di parità, aprì la strada.
Prima intuizione: codici rettangolari
La prima idea di Hamming: disporre i bit di messaggio in un rettangolo m×n, aggiungere un controllo di parità a ogni riga & ogni colonna. Un singolo errore produce esattamente un controllo di riga fallito & un controllo di colonna fallito. La loro intersezione identifica la posizione dell'errore.
Rapporto di ridondanza: (m+1)(n+1) / mn. Il calcolo ti dice che un quadrato minimizza questo per una dimensione di messaggio fissa. Ma mentre m & n crescono, un errore doppio diventa più probabile: un giudizio ingegneristico senza risposta universale.
Minimizzare la ridondanza rettangolare
Un rettangolo 4×4 trasporta 16 bit di messaggio con 4 controlli di riga & 4 controlli di colonna, più 1 bit di parità d'angolo = 9 bit di controllo per 16 bit di messaggio.
Rapporto di ridondanza: (m+1)(n+1) / mn = 25/16 ≈ 1,56.
Per un rettangolo 10×10: 100 bit di messaggio, 121 bit totali, ridondanza ≈ 1,21.
La sindrome come numero binario
Poche settimane dopo l'intuizione del codice rettangolare, Hamming stava viaggiando verso New York attraverso le terre agricole del New Jersey, ripensando mentalmente ai suoi successi. L'idea del codice triangolare gli venne in mente: ridondanza migliore. Poi il cubo. Poi 4-dimensionale, 5-dimensionale...
Ogni dimensione extra migliorava la ridondanza. Un ipercubo di lato 2 in n dimensioni utilizza solo n+1 controlli di parità per 2^n vertici. Ma era questo ottimale?
L'argomento del conteggio
n+1 bit di parità producono una sindrome: un numero binario (n+1)-bit. Quella sindrome deve identificare 2^n + 1 risultati distinti: ognuna delle 2^n posizioni di errore, più il risultato speciale 'nessun errore'.
2^(n+1) = 2·2^n: quasi abbastanza. Fuori di un fattore 2. Hamming mise da parte il problema.
L'intuizione chiave
Più tardi, Hamming tornò con una nuova idea: usare la sindrome stessa come numero binario per denominare la posizione dell'errore. Posizione 1 = binario 001, posizione 2 = binario 010, posizione 3 = binario 011, ecc. Riserva tutti gli zeri per 'nessun errore'.
Questo trasforma la sindrome da un'uscita dei controlli di parità a un indirizzo. I controlli di parità sono progettati per produrre esattamente l'indirizzo giusto quando un singolo bit si capovolge.
Progettare il codice (7,4)
Per un codice a 7 bit (3 bit di parità, 4 bit di messaggio), le posizioni da 1 a 7 in binario sono: 001, 010, 011, 100, 101, 110, 111.
Il controllo di parità 1 copre le posizioni dove il bit 0 = 1: posizioni 1, 3, 5, 7.
Il controllo di parità 2 copre le posizioni dove il bit 1 = 1: posizioni 2, 3, 6, 7.
Il controllo di parità 3 copre le posizioni dove il bit 2 = 1: posizioni 4, 5, 6, 7.
I bit di parità occupano le posizioni potenza-di-2: 1, 2, 4. I bit di messaggio occupano il resto: 3, 5, 6, 7.
Se il bit 6 si capovolge, i controlli di parità 2 & 3 falliscono (110 in binario = 6). La sindrome legge 110 = 6. Capovolgi la posizione 6. Fatto.
Singolo errore corretto, doppio errore rilevato
Il codice (7,4) di Hamming corregge errori singoli. Ma se due bit si capovolgono? Senza protezione extra, il decoder applica la regola della sindrome e 'corregge' la parola di codice al messaggio sbagliato: una miscorrezione silenziosa.
SECDED: un bit di parità in più
Aggiungere un singolo bit di parità p₀ che copre l'intera parola di codice (tutti i 7 bit). Ora la sindrome ha 4 voci: i 3 controlli originali più p₀.
``
sindrome vecchia nuovo p₀ significato
000 0 corretto
000 1 errore solo in p₀
xxx 1 singolo errore, vecchia sindrome lo nomina
xxx 0 doppio errore: segnalalo
``
I quattro casi sono esaustivi. Un errore doppio capovolge due bit: la vecchia sindrome non leggerà 000 (entrambi i bit insieme corrompono due dei suoi controlli), ma p₀ si capovolge due volte e torna a 0. Il modello xxx + 0 è inconfondibile.
Perché SECDED funziona
La regola SECDED sfrutta la struttura modulare della parità. Con parità pari, qualsiasi singolo capovolgimento cambia p₀. Qualsiasi doppio capovolgimento lascia p₀ invariato. Quindi p₀ conta gli errori modulo 2.
L'immagine geometrica
Hamming è arrivato allo stesso luogo da una direzione diversa: geometria analitica. Rappresenta ogni stringa n-bit come un vertice di un ipercubo n-dimensionale. Un singolo capovolgimento di bit sposta un punto di una lunghezza di bordo lungo un asse. Due capovolgimenti: due bordi. La metrica è la distanza di Hamming.
Definire una palla di Hamming di raggio t intorno a una parola di codice c: tutti i punti entro t capovolgimenti di bit da c. Per la correzione di errori singoli, t = 1.
Condizione per la correzione di errori singoli: le palle di raggio 1 intorno a ogni coppia di parole di codice distinte non devono sovrapporsi. Se si sovrapongono, una parola ricevuta nella sovrapposizione potrebbe appartenere a entrambe le parole di codice e il decoder fallisce.
Questo si traduce direttamente in distanza minima: due palle di raggio 1 non si sovrapongono se e solo se le parole di codice sono almeno distanti 3 (d_min ≥ 3).
Il codice (7,4) raggiunge d_min = 3. Il limite di Hamming: 2^7 / (1 + 7) = 16 = 2^4. Esattamente 16 parole di codice. Un codice perfetto: le 16 palle di raggio 1 piastrellano {0,1}^7 senza spazi vuoti o sovrapposizioni.
Giudizi ingegneristici
Hamming fu esplicito: i codici di correzione degli errori comportano giudizi ingegneristici, non matematica pura.
Lunghezza del messaggio: i messaggi più lunghi consentono una codifica più efficiente (log n bit di parità per n bit di messaggio). Ma i messaggi più lunghi accumulano anche più rumore, aumentando il rischio che un errore doppio si infiltri come una falsa correzione singola.
Livello di correzione vs. rilevamento: scambiare una correzione di errore per due rilevamenti di errore extra. La divisione ottimale dipende dalle caratteristiche di rumore del canale.
Valore di manutenzione sul campo: man mano che l'apparecchiatura diventa più complessa, i tecnici sul campo non possono diagnosticare ogni guasto dai primi principi. Un sistema autodiagnostico riduce drammaticamente le competenze richieste per la manutenzione. Hamming ha chiamato questo uno dei vantaggi più importanti, spesso più importante del guadagno di affidabilità grezzo.
Stile: la fortuna favorisce la mente preparata
Hamming ha concluso il Capitolo 12 con una sfida diretta. Ha descritto la scoperta come richiedente da tre a sei mesi di lavoro, principalmente in momenti liberi mentre portava avanti i suoi compiti principali ai Bell Labs.
Ha identificato tre cose che l'hanno reso possibile:
1. Preparazione: profonda familiarità con i controlli di parità, l'aritmetica binaria & la teoria dei gruppi, prima che il problema apparisse.
2. Revisione dei successi: ripetere abitualmente le soluzioni passate per interiorizzarne lo stile. L'idea del codice triangolare gli venne mentre ripensava mentalmente al codice rettangolare durante un tragitto.
3. Non accontentarsi di 'sembra buono': ha sbagliato una volta accettando l'apparente ottimalità. Ha spinto fino a poter provare che il codice fosse il migliore.