Math
Un code qui se répare lui-même
Seize bits dans un carré, onze portant un message : cliquez sur l’un d’eux et les quatre lampes de contrôle épellent son adresse, et le bloc se remet d’aplomb. Deux erreurs sont détectées mais irréparables ; à trois, le bloc ment avec assurance. Chaque affirmation est exhaustive : les 32 768 erreurs simples localisées, les 245 760 doubles détectées, toutes les triples mal corrigées.
Ce qui se passe
Seize bits disposés quatre par quatre. Onze portent un message ; quatre sont des contrôles de parité placés aux puissances de deux (1, 2, 4, 8), et un cinquième en position 0 contrôle le carré entier. Chaque contrôle surveille exactement la moitié du bloc. Comme chaque indice appartient à une combinaison différente de contrôles, les quatre réponses ensemble ne sont pas une alarme mais une ADRESSE : le ou-exclusif des indices de tous les bits allumés donne le nombre inscrit sous la tuile fautive. Cliquez sur une deuxième et le bloc sait encore que quelque chose cloche — le seizième bit sépare « corriger une erreur » de « en corriger une et savoir qu’il y en a deux ». À la troisième, le code ment : il désigne une tuile avec une assurance totale et rend le mauvais message. La distance quatre achète une réparation et deux détections, rien de plus. Sans ce seizième bit le code est PARFAIT au sens technique : 2048 mots de code, chacun avec quinze voisins, et 2048 × 16 = 32 768 = 2¹⁵ exactement. C’est l’arithmétique de la mémoire ECC, de chaque QR code et de tout disque optique ; c’est pourquoi un CD rayé se lit encore.
Équations du module
Équations syndrome : s = XOR des indices de tous les bits positionnés ; s = 0 signifie que les quatre contrôles concordent, et s ≠ 0 EST l'adresse du bit erroné contrôles : le contrôle p surveille chaque indice i tel que (i ET p) ≠ 0 ; p = 1, 2, 4, 8, et la position 0 contrôle le carré entier verdict : s = 0 et parité paire → intact ; parité impaire → une erreur en s (s = 0 signifie le bit 0 lui-même) ; s ≠ 0 et parité paire → deux erreurs, détectées et non réparables code parfait : Hamming(15,11) a 2^11 = 2048 mots de code, chacun avec 15 voisins à un seul bit d'écart ; 2048 × 16 = 32 768 = 2^15 exactement - les sphères de rayon un pavent l'espace sans rien laisser de côté distance : d = 3 pour Hamming(15,11), d = 4 avec le bit du carré entier ; corriger t erreurs exige d ≥ 2t + 1, en détecter t exige d ≥ t + 1 exhaustif : 32 768 cas d'un seul bit, 0 mal localisé ; 245 760 cas de deux bits, 0 manqué et 0 mal corrigé ; 35 840 cas de trois bits, tous les 35 840 "corrigés" à tort rendement : 11 bits de message pour 16 envoyés = 68.75 % ; Hamming(7,4) 57.1 %, Hamming(31,26) 83.9 %, Hamming(63,57) 90.5 % - les blocs plus longs sont une assurance moins chère et perdent davantage à cause d'une seconde erreur
