Hamming, 1950 : trois bits de contrôle pour réparer une erreur

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.

Maintenance — 7 octobre 2026. La couverture a été remplacée car son fichier original et son reçu de génération n’ont pas pu être retrouvés dans les accès disponibles. Le remplacement a été reçu de l’outil natif d’image puis inspecté visuellement ; son fichier, sa consigne et ses références sont conservés dans le dossier éditorial privé. L’ancienne couverture et sa provenance non vérifiée restent dans l’historique. Il s’agit d’une illustration, pas d’une preuve expérimentale ; le résultat scientifique central est conservé.

Illustration conceptuelle générée par IA du code de Hamming (7,4) : quatre bits de données, trois bits de contrôle, une inversion corrigée par bloc. Tuiles symboliques, pas un circuit.

Avant les équations

Un bit est une valeur, 0 ou 1. Une inversion remplace l’une par l’autre. La parité indique si un groupe contient un nombre pair ou impair de 1. Par exemple, 101 contient deux 1 : sa parité est paire. La redondance consiste à transmettre des informations supplémentaires pour permettre au destinataire de vérifier les données. Ici, trois contrôles qui se recoupent localisent un bit inversé, à condition qu’il y en ait au plus un dans un bloc de sept bits.

Pour comprendre, suivez l’exemple de la section 3, puis revenez aux équations de la section 2. Pour vérifier, utilisez le programme complet ci-dessous. Avant de poursuivre, demandez-vous : un contrôle réussi prouve-t-il qu’aucun bit n’a changé ? La section 5 explique pourquoi la réponse dépend du modèle d’erreur.

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]

$p_1=d_1\oplus d_2\oplus d_4$p1​=d1​⊕d2​⊕d4​

$p_2=d_1\oplus d_3\oplus d_4$p2​=d1​⊕d3​⊕d4​

$p_4=d_2\oplus d_3\oplus d_4$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=s_1+2s_2+4s_4$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 :

$2^r\ge n+1$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]

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 :

$\begin{aligned} P_{\rm fail}&=1-(1-p)^7\\ &\quad-7p(1-p)^6. \end{aligned}$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é.

8. Reproduire le calcul fini

Protocole HAMMING-REPRO-1. Copiez le bloc Python complet dans reproduce_hamming.py et lancez python3 reproduce_hamming.py. Il utilise uniquement la bibliothèque standard de Python, sans réseau, téléchargement de données ni graine aléatoire. Il a été exécuté avec CPython 3.12.14 pour cette révision éditoriale. Les positions commencent à 1 ; le huitième bit impose une parité totale paire. Le programme énumère les 16 messages, construit séparément les mots valides à sept bits à partir des contraintes de parité, puis les compare à l’encodeur.

Sortie attendue : status PASS, codewords 16, minimum_distances [3, 4]. Les compteurs indiquent 128 restitutions correctes sans erreur ou avec une erreur sur sept bits ; 144 sur huit bits ; 448 doubles erreurs détectées par le code étendu ; 336 doubles erreurs mal corrigées par le décodeur à sept bits ; et 896 triples erreurs mal corrigées par le décodeur à huit bits décrit. Ces deux derniers compteurs sont des contrôles négatifs : ils exposent les limites, pas des corrections réussies. Pour p = 0,01, coded_message_error vaut environ 0,00203104163494 et uncoded_message_error 0,03940399. Ces probabilités supposent des inversions indépendantes à p fixé, pas une énergie ou une bande passante identiques.

"""News HAMMING-REPRO-1: finite mathematical check, not hardware validation."""
from itertools import combinations, product
import json
import platform


def encode(data):
    a, b, c, d = data
    return (a ^ b ^ d, a ^ c ^ d, a, b ^ c ^ d, b, c, d)


def syndrome(word):
    a, b, c, d, e, f, g = word[:7]
    return (a ^ c ^ e ^ g) + 2 * (b ^ c ^ f ^ g) + 4 * (d ^ e ^ f ^ g)


def flip(word, positions):
    result = list(word)
    for position in positions:
        result[position - 1] ^= 1
    return tuple(result)


def decode7(word):
    position = syndrome(word)
    return flip(word, (position,)) if position else word


def decode8(word):
    position, parity = syndrome(word), sum(word) % 2
    if parity:
        return flip(word, (position or 8,))
    return None if position else word


def distance(a, b):
    return sum(x != y for x, y in zip(a, b))


def require(condition, label):
    if not condition:
        raise RuntimeError(label)


messages = list(product((0, 1), repeat=4))
code7 = [encode(data) for data in messages]
code8 = [word + (sum(word) % 2,) for word in code7]
# Independent enumeration uses parity sums rather than the encoder equations.
groups = ((1, 3, 5, 7), (2, 3, 6, 7), (4, 5, 6, 7))
oracle = {
    word for word in product((0, 1), repeat=7)
    if all(sum(word[p - 1] for p in group) % 2 == 0 for group in groups)
}
require(len(set(code7)) == 16 and set(code7) == oracle, "codebook")
min7 = min(distance(a, b) for a, b in combinations(code7, 2))
min8 = min(distance(a, b) for a, b in combinations(code8, 2))
require((min7, min8) == (3, 4), "minimum distances")
counts = {"seven_zero_or_one": 0, "eight_zero_or_one": 0,
          "eight_double_detected": 0, "seven_double_miscorrected": 0,
          "eight_triple_miscorrected": 0}
for word in code7:
    for positions in [()] + [(i,) for i in range(1, 8)]:
        require(decode7(flip(word, positions)) == word, "seven-bit recovery")
        counts["seven_zero_or_one"] += 1
    for positions in combinations(range(1, 8), 2):
        received = flip(word, positions)
        require(syndrome(received) != 0, "double error detectable")
        require(decode7(received) != word, "double error outside correction guarantee")
        counts["seven_double_miscorrected"] += 1
for word in code8:
    for positions in [()] + [(i,) for i in range(1, 9)]:
        require(decode8(flip(word, positions)) == word, "eight-bit recovery")
        counts["eight_zero_or_one"] += 1
    for positions in combinations(range(1, 9), 2):
        require(decode8(flip(word, positions)) is None, "double error must be flagged")
        counts["eight_double_detected"] += 1
    for positions in combinations(range(1, 9), 3):
        result = decode8(flip(word, positions))
        require(result is not None and result != word and result in code8,
                "triple error counterexample")
        counts["eight_triple_miscorrected"] += 1
require(list(counts.values()) == [128, 144, 448, 336, 896], "case counts")
require(encode((1, 0, 1, 0)) == (1, 0, 1, 1, 0, 1, 0), "worked example")
require(syndrome((1, 0, 1, 1, 0, 0, 0)) == 6, "worked syndrome")
p = 0.01
failure = 1 - (1-p)**7 - 7*p*(1-p)**6
uncoded = 1 - (1-p)**4
require(abs(failure - 0.00203104163494) < 1e-12, "probability")
print(json.dumps({"protocol": "HAMMING-REPRO-1", "python": platform.python_version(),
                  "codewords": len(code7), "minimum_distances": [min7, min8],
                  "counts": counts, "p": p, "coded_message_error": failure,
                  "uncoded_message_error": uncoded, "status": "PASS"}, indent=2))

PASS signifie que ces vérifications mathématiques finies ont réussi. Cela ne démontre ni les performances d’un matériel, ni la robustesse à d’autres modèles d’erreur, ni une réplication indépendante. Le champ python indique la version de votre interpréteur et peut différer. En cas de RuntimeError, conservez le script et la sortie complète, puis examinez le contrôle nommé ; une exécution partielle ne vaut pas validation.

Méthode News pour cet article

2026-10-03 — La révision HAMMING-EN-2 ajoute l’introduction progressive et le protocole complet. Le corps scientifique et le schéma programmé sont conservés depuis HAMMING-EN-1. Pour cette mise à jour, la construction et ses limites ont été revérifiées dans l’article de 1950 et les sections 5.6–5.7 du MIT ; le programme fini a été exécuté. Rédaction et traductions sont réalisées par IA, sans expertise indépendante ni validation humaine.

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.