Article rédigé et traduit par un système d’IA à partir des sources citées, avec contrôles automatisés selon la méthode éditoriale News.
Couverture conceptuelle générée par IA : des contrôles structurés rétablissent l’ordre dans un flux perturbé ; ni circuit littéral ni preuve d’une correction illimitée.
1. Fiabiliser par une redondance structurée
En avril 1950, Richard W. Hamming publie « Error Detecting and Error Correcting Codes » dans le Bell System Technical Journal. Son problème est concret : détecter une panne pendant un calcul sans surveillance peut arrêter le travail ; la localiser et la corriger peut permettre de poursuivre. L’article fournit des constructions binaires explicites, pas une promesse de réparer tous les dommages. [1,2]
L’avancée consiste à rendre la redondance informative. Répéter chacun de quatre bits trois fois demanderait douze bits transmis. Un code de Hamming en utilise sept pour protéger les mêmes quatre bits contre une inversion quelconque dans le bloc. Ce sont deux organisations de la redondance, pas la preuve qu’un code convient à tous les canaux. La compression enlève de la redondance ; la correction d’erreurs en ajoute une forme contrôlée.
2. Sept positions, trois questions
Numérotons les positions transmises de 1 à 7. Les positions 1, 2 et 4 portent les bits de contrôle ; les positions 3, 5, 6 et 7 portent les données d₁, d₂, d₃ et d₄. Le symbole ⊕ désigne le OU exclusif, une addition modulo 2 : 1 ⊕ 1 = 0. Les trois équations ci-dessous imposent une parité paire. Les indices de p désignent les positions, pas le rang des contrôles. [1, §3]
p1=d1⊕d2⊕d4
p2=d1⊕d3⊕d4
p4=d2⊕d3⊕d4
Le récepteur refait les contrôles sur {1,3,5,7}, {2,3,6,7} et {4,5,6,7}. Un contrôle qui échoue produit un bit de syndrome égal à 1, sinon 0. Notons-les s₁, s₂ et s₄. Sous l’hypothèse d’au plus une inversion, sa position j vaut :
j=s1+2s2+4s4
Un syndrome nul signifie absence d’erreur seulement sous cette hypothèse ; ce n’est pas un certificat universel d’intégrité.
3. Une correction reproductible
Prenons les données 1010. Les équations donnent p₁ = 1, p₂ = 0 et p₄ = 1. Le mot transmis, lu de gauche à droite dans l’ordre des positions, est donc 1011010. Si le bit 6 s’inverse, le récepteur reçoit 1011000. Le premier contrôle est pair ; les deuxième et troisième sont impairs. Ainsi (s₁,s₂,s₄) = (0,1,1) et j = 0 + 2 + 4 = 6. On inverse à nouveau le bit 6 puis on lit les positions 3,5,6,7 : les données retrouvées sont 1010.
Schéma scientifique produit par code ; suites binaires exactes, sans données expérimentales.
Cet exemple est un calcul éditorial, pas une mesure expérimentale. La procédure corrige aussi l’inversion d’un bit de contrôle. Elle suppose que les frontières des blocs et les positions sont connues ; un bit supprimé ou inséré relève d’un autre modèle d’erreur.
4. Pourquoi la construction fonctionne
Trois contrôles binaires ont huit résultats possibles : exactement assez pour distinguer les sept positions d’une erreur unique et l’absence d’erreur. Plus généralement, pour corriger une inversion, un code binaire à r bits de contrôle et n bits au total doit disposer d’au moins n + 1 syndromes distincts :
2r≥n+1
La construction de Hamming atteint ce compte avec n = 2ʳ − 1 et k = n − r bits de données. Pour r = 3, n = 7 et k = 4. Sa distance minimale de Hamming — le plus petit nombre de positions différentes entre deux mots valides — est 3. Un mot reçu ne peut être à une inversion de deux mots valides distincts : ceux-ci seraient alors distants d’au plus 2.
Les 16 mots valides ont chacun sept voisins à une inversion, en plus d’eux-mêmes. Ces ensembles disjoints couvrent les 128 mots possibles : 16 × 8 = 128. « Parfait » qualifie ce pavage, pas un fonctionnement infaillible quel que soit le bruit. [1, §§5,7]
5. Le piège des deux erreurs
Deux inversions produisent toujours un syndrome non nul : un détecteur qui se contente de signaler les mots invalides peut donc les détecter. Mais un décodeur qui interprète tout syndrome non nul comme une erreur unique peut mal corriger. Par exemple, des inversions aux positions 2 et 5 donnent le même syndrome qu’une inversion au bit 7. Corriger le bit 7 laisse alors trois bits faux et un autre mot valide.
Ajoutons un huitième bit pour rendre paire la parité totale. Le code étendu a une distance minimale de 4 et permet la correction d’une erreur avec détection de deux erreurs, ou SECDED. Les décisions suivantes supposent au plus deux inversions. q est la parité des huit bits reçus. [1, §4]
| Syndrome j | Parité q | Action sous l’hypothèse indiquée |
|---|---|---|
| 0 | 0 | Aucune erreur |
| 0 | 1 | Réparer le bit 8 |
| non nul | 1 | Réparer le bit j |
| non nul | 0 | Signaler deux erreurs ; ne pas corriger |
Trois erreurs ou davantage sortent de cette garantie. Un décodeur SECDED peut en corriger certaines à tort ; « détection de deux erreurs » ne signifie pas diagnostic de toute panne plus importante.
6. Un bénéfice chiffré, sous hypothèses explicites
Supposons que chaque bit transmis s’inverse indépendamment avec une probabilité p = 0,01, identique pour 0 et 1. Supposons aussi un encodeur et un décodeur parfaits et des frontières de blocs connues. Pour le code à sept bits et le décodeur décrit, le message de quatre bits est faux exactement lorsque le bloc subit au moins deux inversions :
Pfail=1−(1−p)7−7p(1−p)6.
On obtient environ 0,002031, soit 0,2031 % des blocs. Transmettre les quatre bits sans codage donne 1 − (1 − p)⁴ = 0,039404, soit 3,9404 % de messages comportant une erreur. Ce sont des probabilités d’erreur de message, pas des taux d’erreur résiduels par bit ni des performances mesurées d’un appareil.
La protection coûte trois bits supplémentaires pour quatre bits de données : 75 % de bits transmis en plus, avec un rendement de 4/7 ≈ 0,5714 bit de données par bit transmis. La comparaison fixe p ; elle ne fixe pas simultanément la bande passante, le temps de transmission et l’énergie par message.
7. Ce que le résultat promet — et ne promet pas
L’apport durable est un lien constructif entre algèbre et fiabilité : espacer les mots valides, calculer des contrôles compacts, puis localiser une faute limitée. Le cas à sept bits se vérifie exhaustivement. Pour cet article, les 16 messages et leurs 128 cas sans erreur ou à une erreur ont été contrôlés, ainsi que les 448 cas à deux erreurs du code étendu.
Ce n’est pas un code pour réparer toutes les rafales d’erreurs, un logiciel corrompu, une altération malveillante ou une perte de synchronisation. Un système réel doit adapter le code à ses défauts et protéger l’encodeur, le décodeur et la logique environnante. L’article de Hamming ne mesure pas les matériels modernes. Notre exemple chiffré est séparé de telles affirmations. Le sujet complète les limites de communication étudiées par Shannon par une construction finie explicite, pas par une solution universelle atteignant la capacité.
Méthode News pour cet article
Révision de référence : HAMMING-EN-1. L’article primaire de 1950 a été lu intégralement dans un fac-similé archivé et son OCR ; la construction et les cas SECDED ont aussi été vérifiés sur les pages numérisées. La notice de l’éditeur confirme la date bibliographique. Les notes du MIT permettent une comparaison moderne des notations. Calculs et contrôles finis ont été exécutés par un script reproductible. Rédaction et sept traductions sont réalisées par IA ; ces contrôles ne sont ni une expertise indépendante ni une validation humaine. Le schéma localisé est produit par code. La couverture est une illustration conceptuelle générée par IA, pas une photographie, un instrument ou un graphique de données.
Sources
[1] R. W. Hamming — Error Detecting and Error Correcting Codes — DOI: 10.1002/j.1538-7305.1950.tb00463.x.
[2] Nokia Bell Labs — Error Detecting and Error Correcting Codes.
[3] MIT 6.02 — Coping with Bit Errors using Error Correction Codes.