Math
Un codice che si ripara da solo
Sedici bit in un quadrato, undici dei quali un messaggio: clicca su uno e le quattro spie di controllo compitano il suo indirizzo, e il blocco si rimette a posto. Due errori vengono rilevati ma non riparati; a tre, il blocco mente con sicurezza. Ogni affermazione è esaustiva: tutti i 32 768 errori singoli localizzati, tutti i 245 760 doppi rilevati, ogni tripla corretta male.
Cosa succede
Sedici bit disposti quattro per quattro. Undici portano un messaggio; quattro sono controlli di parità sulle potenze di due (1, 2, 4, 8), e un quinto in posizione 0 controlla tutto il quadrato. Ogni controllo sorveglia esattamente metà del blocco. Poiché ogni indice appartiene a una combinazione diversa di controlli, le quattro risposte insieme non sono un allarme ma un INDIRIZZO: lo or-esclusivo degli indici di tutti i bit accesi è il numero scritto sotto la tessera sbagliata. Clicca una seconda e il blocco sa ancora che qualcosa non va: il sedicesimo bit separa «correggere un errore» dal «correggerne uno e sapere che sono due». Alla terza il codice mente: indica una tessera con piena sicurezza e restituisce il messaggio sbagliato. La distanza quattro compra una riparazione e due rilevamenti, niente di più. Senza quel sedicesimo bit il codice è PERFETTO in senso tecnico: 2048 parole, ciascuna con quindici vicine, e 2048 × 16 = 32 768 = 2¹⁵ esattamente. È l’aritmetica della memoria ECC, di ogni codice QR e di ogni disco ottico; per questo un CD graffiato suona ancora.
Equazioni del modulo
Equazioni sindrome: s = XOR degli indici di ogni bit attivo; s = 0 significa che i quattro controlli concordano, e s ≠ 0 È l'indirizzo del bit sbagliato controlli: il controllo p sorveglia ogni indice i con (i AND p) ≠ 0; p = 1, 2, 4, 8, e la posizione 0 controlla l'intero quadrato verdetto: s = 0 e parità pari → integro; parità dispari → un errore in s (s = 0 significa il bit 0 stesso); s ≠ 0 e parità pari → due errori, rilevati e non riparabili codice perfetto: Hamming(15,11) ha 2^11 = 2048 parole di codice, ciascuna con 15 vicini a un solo bit di distanza; 2048 × 16 = 32 768 = 2^15 esattamente - le sfere di raggio uno ricoprono lo spazio senza lasciare nulla distanza: d = 3 per Hamming(15,11), d = 4 con il bit dell'intero quadrato; correggere t errori richiede d ≥ 2t + 1, rilevare t richiede d ≥ t + 1 esaustivo: 32 768 casi con un solo bit, 0 localizzati male; 245 760 casi con due bit, 0 mancati e 0 corretti male; 35 840 casi con tre bit, tutti i 35 840 "corretti" in modo errato rendimento: 11 bit di messaggio ogni 16 inviati = 68.75 %; Hamming(7,4) 57.1 %, Hamming(31,26) 83.9 %, Hamming(63,57) 90.5 % - i blocchi più lunghi sono un'assicurazione più economica e perdono di più con un secondo errore
