Contrôle de parité : expliquer le bit de parité avec des cartes

Le principe : un bit de plus pour compter les 1

Un bit vaut 0 ou 1. Pour le montrer en famille, prenez des cartes ou des carrés de papier : face visible colorée, c'est un 1 ; face blanche, c'est un 0. Une rangée de sept cartes figure donc un petit message de sept bits.

Le contrôle de parité repose sur un comptage. Vous comptez les 1 du message. Si ce nombre est pair, le message est « pair » ; s'il est impair, il est « impair ». Zéro est un nombre pair : une rangée entièrement blanche est donc paire, ce qui surprend souvent les enfants.

Le bit de parité est la carte supplémentaire que vous posez au bout de la rangée pour imposer le résultat voulu. Celui qui reçoit le message refait le comptage. Si le résultat n'est plus celui attendu, c'est qu'un bit a changé pendant le trajet.

Parité paire et parité impaire

Il existe deux conventions, et l'important est que l'émetteur et le récepteur choisissent la même.

• Avec la parité paire, on ajoute le bit qui rend le total des 1 pair, bit de parité compris.
• Avec la parité impaire, on ajoute le bit qui rend ce total impair.

Exemple avec la lettre A, codée en ASCII sur sept bits : 1000001. Elle contient deux 1.

• En parité paire, le total est déjà pair : le bit de parité vaut 0. Le message envoyé est 10000010.
• En parité impaire, il faut passer à trois 1 : le bit de parité vaut 1. Le message envoyé est 10000011.

Le contrôle de parité dans la transmission de données

En informatique, le même calcul s'applique à une chaîne de données binaires, une suite de 0 et de 1 envoyée d'une machine à une autre. On la découpe le plus souvent en octets, des groupes de huit bits, et chaque groupe reçoit son bit de parité. Ce bit de contrôle ne dit rien du contenu : il sert à vérifier le reste. L'émetteur compte les 1 et choisit le bit à ajouter ; le récepteur refait le comptage, et si la convention n'est pas respectée, il demande un nouvel envoi.

Prenons la lettre S, codée sur sept bits en ASCII : 1010011. Elle contient quatre 1.

• En parité paire, le total est déjà pair : le bit ajouté vaut 0, et l'octet transmis est 10100110.
• En parité impaire, il faut un 1 de plus pour atteindre cinq : le bit ajouté vaut 1, et l'octet transmis est 10100111.

Supposons que le quatrième bit de 10100110 soit inversé en route : 10110110. Le récepteur compte cinq 1, un nombre impair alors que la convention est paire. Il rejette l'octet. La parité détecte ainsi une erreur de transmission sur un seul bit.

Ce que le contrôle détecte, et ce qu'il laisse passer

Reprenons 10000010, le A en parité paire. Un joueur retourne en cachette la troisième carte : le message devient 10100010. Il contient maintenant trois 1, un nombre impair. Le récepteur sait qu'il y a eu une erreur.

Mais il ne sait pas où. Le contrôle dit « quelque chose a changé », pas « c'est la troisième carte ». Il ne corrige donc rien : il faut redemander le message.

Autre limite, plus piégeuse : deux erreurs s'annulent. Si le joueur retourne la première et la dernière carte de 10000010, le message devient 00000011. Il contient deux 1, un nombre pair. Le récepteur ne voit rien, alors que le message est faux. Retenez la règle : le contrôle attrape toute erreur qui touche un nombre impair de bits et laisse passer celles qui en touchent un nombre pair.

Le tour de magie des cartes retournées

Ce tour s'inspire d'une activité du programme CS Unplugged qui explique l'informatique sans ordinateur. L'activité d'origine pose des cartes au hasard, environ 5 sur 5, puis ajoute une rangée et une colonne de parité. Voici cette version, qui combine la parité sur les lignes et sur les colonnes. Il lui faut 36 cartes à deux faces, l'une colorée et l'autre blanche. Pour les fabriquer, le guide du memory personnalisé montre comment découper et coller des faces bien nettes.

Préparation. Posez 25 cartes en carré de 5 sur 5, au hasard (1 pour coloré, 0 pour blanc). Ajoutez ensuite une sixième carte à la fin de chaque ligne, de façon que chaque ligne compte un nombre pair de cartes colorées. Ajoutez une sixième ligne sous le carré, de façon que chaque colonne en compte aussi un nombre pair. La carte du coin, en bas à droite, se règle comme les autres, et elle convient pour la ligne comme pour la colonne. Cela fait bien 25 cartes de message et 11 cartes de parité.

Voici une grille complète, dont la sixième colonne et la sixième ligne sont les cartes de parité :

1 0 1 1 0 | 1
0 1 0 0 1 | 0
1 1 0 0 0 | 0
0 0 1 0 1 | 0
1 0 0 1 1 | 1
----------+--
1 0 0 0 1 | 0

Vérifiez la première ligne : 1, 0, 1, 1, 0 contient trois 1, donc la carte de parité vaut 1 et la ligne en compte quatre. La première colonne (1, 0, 1, 0, 1) en contient trois : sa carte de parité vaut 1 aussi. Chaque ligne et chaque colonne de la grille complète a un nombre pair de 1.

Le tour. Pendant que vous tournez le dos, un spectateur retourne une seule carte, n'importe laquelle. Vous vous retournez et comptez les cartes colorées de chaque ligne et de chaque colonne. Une seule ligne est impaire, une seule colonne est impaire. La carte retournée est à leur croisement.

Avec notre grille, imaginez que la carte de la troisième ligne, quatrième colonne, passe de 0 à 1. La troisième ligne devient 1 1 0 1 0 | 0 : trois 1, impair. La quatrième colonne devient 1, 0, 1, 0, 1, 0 : trois 1, impair. Aucune autre ligne ni colonne n'a changé. Vous désignez ce croisement, et c'est la carte retournée.

Si le spectateur retourne une carte de parité, le tour marche pareil : la ligne et la colonne impaires se croisent sur cette carte. Avec deux directions, l'erreur n'est plus seulement détectée : elle est localisée, donc corrigeable en retournant la carte. C'est le passage de la simple détection à la correction d'erreurs.

Cette logique de lignes et de colonnes dont le croisement tranche rappelle le sudoku 4x4 et sa façon de déduire chaque case en recoupant sa ligne et sa colonne.

Où se place la parité parmi les méthodes de détection d'erreurs

Le code ASCII historique n'utilise que sept bits par caractère : le huitième bit d'un octet pouvait servir de bit de parité, et des liaisons série et des mémoires y ont eu recours. Le but est l'intégrité des données : recevoir exactement ce qui a été envoyé. La parité est la méthode de détection la moins coûteuse, un seul bit par groupe. Voici ce qui existe au-dessus.

• La parité par ligne et par colonne. Les caractères d'un bloc sont empilés, chacun avec sa parité, puis une ligne de contrôle donne la parité de chaque colonne de bits. C'est exactement la grille du tour de magie. Une erreur isolée est repérée et localisée, donc corrigeable.
• La somme de contrôle. On additionne les valeurs des octets ou des mots d'un bloc, et l'on envoie le résultat avec le bloc. Le récepteur refait l'addition. Elle attrape plus d'erreurs qu'un bit seul, mais des erreurs qui se compensent peuvent la tromper.
• Le contrôle de redondance cyclique, ou CRC. Le bloc est traité comme un grand polynôme, divisé par un polynôme générateur fixé d'avance, et le reste de cette division est ajouté au message. Le récepteur refait la division. Un reste nul laisse penser que le bloc est intact. Il repère bien mieux les rafales, ces séries de bits abîmés à la suite, et on le rencontre dans les réseaux et les fichiers compressés.
• Le code de Hamming. Il mélange plusieurs bits de parité, chacun couvrant une partie du message. Dans sa version classique, 4 bits de données reçoivent 3 bits de parité. Contrairement aux méthodes précédentes, il ne se contente pas de signaler une erreur : il la corrige quand elle touche un seul bit.

Voici Hamming sur un petit exemple. On numérote les positions de 1 à 7. Les bits de parité occupent les positions 1, 2 et 4 ; les données occupent les positions 3, 5, 6 et 7. La parité de la position 1 couvre les positions 1, 3, 5 et 7 ; celle de la position 2 couvre 2, 3, 6 et 7 ; celle de la position 4 couvre 4, 5, 6 et 7. Chaque groupe doit compter un nombre pair de 1.

Pour les données 1011, placées aux positions 3, 5, 6 et 7, on obtient une parité de 0 en position 1 (bits 1, 0, 1), de 1 en position 2 (bits 1, 1, 1) et de 0 en position 4 (bits 0, 1, 1). Le mot envoyé est 0110011.

Si la position 5 est inversée en route, le mot reçu devient 0110111. Groupe 1, 3, 5, 7 : trois 1, il échoue. Groupe 2, 3, 6, 7 : quatre 1, rien à signaler. Groupe 4, 5, 6, 7 : trois 1, il échoue aussi. Les deux groupes en échec sont ceux des parités 1 et 4, et 1 + 4 donne 5. Le bit fautif est donc à la position 5. On l'inverse, et le message est rétabli. Le tour de magie en reprend l'idée, avec des cartes à la place des bits.