Médaille
N°1 pour apprendre & réviser du collège au lycée.

Sécurité du transfert d'information

Déjà plus de

1 million

d'inscrits !

Introduction :

Lorsqu’une information est transmise, surtout si le « chemin » est long, comme l’envoi d’un courriel à l’autre bout de la planète, elle peut subir des dommages lors de son parcours. Comment, alors, s’assurer que le message reçu est bien celui qui a été envoyé ?

Dans ce cours, nous découvrirons comment on peut savoir s’il y a une erreur dans le message binaire transmis, mais aussi, le cas échéant, comment on peut la corriger, grâce au bit de parité et aux codes de Hamming.
Nous resterons sur les exemples les plus simples, afin de bien comprendre les principes qui sous-tendent ces méthodes de contrôle et de correction.

Somme de contrôle

Le principe de la somme de contrôle (checksum en anglais) repose sur l’ajout d’un nombre au message, qui permet au destinataire de vérifier la présence d’erreurs.

Bit et somme de parité

Dans le code du message original est ajouté un bit supplémentaire, appelé bit de parité, qui permettra au destinataire de faire un contrôle d’erreur.

  • Il se place avant le bit de poids fort (il est le dernier à être transmis).
bannière definition

Définition

Bit de parité :

Nous choisissons ici la convention suivante :

  • si la somme des autres bits est paire, alors le bit de parité sera égal à 00 ;
  • si la somme des autres bits est impaire, alors le bit de parité sera égal à 11.
  • Ainsi, la somme globale des bits incluant le bit de parité sera toujours paire.

Nous pouvons l’exprimer d’une manière plus simple :

  • si le nombre de bits égaux à 11 est pair, alors le bit de parité sera égal à 00 ;
  • si le nombre de bits égaux à 11 est impair, alors le bit de parité sera égal à 11.
  • Dans le message global, avant envoi, il y aura toujours un nombre pair de bits égaux à 11.
bannière à retenir

À retenir

Le destinataire, quand il recevra le message, opérera la somme de parité du code : si le résultat est impair, et donc qu’il y a un nombre impair de bits égaux à 11, il saura qu’un bit est erroné et qu’une erreur de transmission est survenue.

bannière attention

Attention

Veillez à ne pas confondre :

  • 01012=5100\purple10\purple1{\tiny 2}=5{\tiny 10}, qui est un nombre impair ;
  • la somme de parité est en revanche paire : 0+1+0+1=20+\purple1+0+\purple1=2, qui est pair.

Exemple

Pour bien comprendre comment cela fonctionne, prenons un exemple simple.
Nous souhaitons envoyer un message, codé sur un quartet de la manière suivante :

11 00 11 11

(Nous représenterons, dans ce cours, les codes sous la forme de tableau, pour plus de lisibilité.)

Regardons la somme de parité : 1+0+1+1=31+0+1+1=3, qui est impair.

  • Le bit de parité, identifié en bleu dans le code ci-dessous, est donc égal à 11, que nous ajoutons au code, pour obtenir :

1\blue 1 11 00 11 11
  • C’est donc ce message qui est envoyé.

Distinguons maintenant deux cas.

  • Le destinataire reçoit le message :

1\blue 1 11 00 11 11

Il opère la somme de parité : 1+1+0+1+1=41+1+0+1+1=4, qui est pair.

  • Il n’y a pas d’erreur. Comme il connaît l’emplacement du bit de parité, il retrouve le message original.
  • Le destinataire reçoit le message :

1\blue 1 11 00 0\red 0 11

Il opère ici aussi la somme de parité : 1+1+0+0+1=31+1+0+\red 0+1=3, qui est impair.

  • Il sait qu’il y a une erreur.

Limites du bit de parité

Nous voyons tout de suite quelles sont les limites d’un tel contrôle.

  • Imaginons qu’il y ait un nombre pair de bits erronés.

Reprenons l’exemple ci-dessus. Le destinataire reçoit un message avec 22 erreurs :

1\blue 1 0\red 0 00 0\red 0 11

Il opère la somme de parité : 1+0+0+0+1=21+\red 0+0+\red 0 +1=2, qui est pair.

  • Pour lui, il n’y a pas d’erreur, alors qu’il y en a 22.
  • Une autre limite apparaît de manière évidente : si le destinataire reconnaît qu’il y a un bit erroné, il ne sait pas lequel.
  • Enfin, comme il ignore quel bit est erroné, il ne peut le corriger.
  • Ainsi, ce simple contrôle peut permettre de repérer la présence d’une erreur, mais il ne peut localiser précisément l’erreur et ne peut la corriger.
  • Le destinataire doit donc demander à l’expéditeur le renvoi du message complet, qui peut être lourd.

Il nous est donc nécessaire de faire appel à un autre système de contrôle, qui pourra identifier le bit erroné et ensuite le corriger, mais dans lequel la notion de bit de parité sera importante à connaître.

Code correctif de Hamming

Les codes de Hamming sont des codes correcteurs, qui doivent leur nom au mathématicien américain Richard Hamming. Ils reposent sur des notions mathématiques approfondies, que nous ne découvrirons qu’en terminale, voire plus tard.

  • Dans ce cours, nous nous contenterons donc d’étudier leur principe sur un cas particulier, le plus simple : le code de Hamming (7,4,3)(7,\,4,\,3), parfois appelé code de Hamming (7,4)(7,\,4), qui lui aussi aura ses limites.
    Mais, en comprenant ce principe, nous pourrons ensuite l’étendre à des codes plus complexes, qui permettront d’éliminer certaines de ces limites.
bannière à retenir

À retenir

Dans ce code (7,4,3)(7,\,4,\,3) :

  • le 77 indique la longueur totale du message une fois encodé ;
  • le 44 indique la longueur du message original (sur 11 quartet, donc) ;
  • le 33 indique la distance minimale du code.
bannière attention

Attention

Pour la distance minimale du code, nous n’entrerons pas non plus dans le détail. Pour l’instant, il vous suffit de savoir que le nombre d’erreurs détectables et corrigibles dépend de cette distance : si dd est la distance minimale, alors on peut corriger au maximum d12\frac {d-1}2 erreur(s).

  • Avec une distance de 33, ce qui est notre cas, nous pouvons corriger 11 erreur.
bannière definition

Définition

Syndrome :

L’objectif de cet élément est d’avoir un nombre binaire qui pourra, après décodage, indiquer la présence ou non d’une erreur et, surtout, qui localisera le cas échéant le bit erroné.

  • Ce nombre est appelé syndrome.
bannière exemple

Exemple

Pour la suite, nous nous intéresserons au message :

11 00 11 11

Et nous souhaitons envoyer ce message, dont nous voulons que le destinataire puisse vérifier la bonne transmission.

Encodage du message

Dans notre cas, nous avons donc un message total de 77 bits et un message initial de 44 bits.

  • Notre syndrome aura donc 33 bits.

Soit aa, bb et cc les valeurs de ces 33 bits. Le syndrome sera de la forme :

a\blue a b\blue b c\blue c

Commençons par regarder le tableau suivant, qui donne les valeurs possibles du syndrome.

  • Il s’agit d’une simple équivalence entre nombre binaire et nombre décimal, chose que nous avons déjà travaillée dans un cours précédent.

aa bb cc Syndrome
00 00 00 0\red 0
00 00 11 1\red 1
00 11 00 2\red 2
00 11 11 3\red 3
11 00 00 4\red 4
11 00 11 5\red 5
11 11 00 6\red 6
11 11 11 7\red 7
bannière à retenir

À retenir

  • En regardant les valeurs décimales du syndrome, nous voyons qu’il peut décrire la totalité des 77 positions de notre message à 77 bits, avec en plus une valeur supplémentaire, 00, pour indiquer l’absence d’erreur.
  • Intéressons-nous aux lignes surlignées en bleu clair : il s’agit de celles où cc a pour valeur 11.
  • Nous pouvons associer à cc les positions 11, 33, 55 et 77.
  • De la même manière, nous pouvons associer à bb les positions 22, 33, 66 et 77.
  • Enfin, nous pouvons associer à aa les positions 44, 55, 66 et 77.

Bit du syndrome Positions associées
aa 44 55 66 77
bb 22 33 66 77
cc 11 33 55 77

Maintenant, vous vous demandez sans doute où placer aa, bb et cc dans notre message de 77 bits. La réponse est logique :

  • ils seront placés aux positions où les groupes ci-dessus définis ne se chevauchent pas – soit les positions 11, 22 et 44 (des puissances de 22) –, et leur position sera celle qui appartient à leur groupe.
bannière à retenir

À retenir

  • Soit le message initial :

i3i3 i2i2 i1i1 i0i0
  • Soit aa, bb et cc les bits du syndrome.
  • Alors le message encodé sera de la forme :

c\blue c b\blue b i3i3 a\blue a i2i2 i1i1 i0i0
bannière exemple

Exemple

Reprenons notre exemple :

11 00 11 11
  • Nous obtenons :

c\blue c b\blue b 11 a\blue a 00 11 11

Vous vous demandez désormais, à partir du message initial, quelles valeurs donner à aa, bb et cc dans notre message complété.

  • Nous allons bien sûr nous servir de la somme de parité, que nous avons vue dans la première partie.
bannière à retenir

À retenir

aa, bb et cc sont les bits de parité du groupe qui leur est associé.
Ainsi, la somme totale de chaque groupe est paire.

  • La somme de tous les bits, aa, bb et cc compris, est paire.
bannière exemple

Exemple

Revenons encore une fois à notre exemple :

c\blue c b\blue b 11 a\blue a 00 11 11

Nous savons que aa est associé aux positions 44, 55, 66 et 77. Faisons la somme de parité des bits en position 55, 66 et 77 (aa étant donc à la position 44) : 0+1+1=20+1+1=2, qui est pair.

  • a=0a=0.

De la même façon, concernant bb, pour les bits en position 33, 66 et 77 : 1+1+1=31+1+1=3, qui est impair.

  • b=1b=1.

Enfin, concernant cc, pour les bits en position 33, 55 et 77 : 1+0+1=21+0+1=2, qui est pair.

  • c=0c=0.

Nous obtenons le message encodé :

0\blue 0 1\blue 1 11 0\blue 0 00 11 11

Réception et décodage du message

Notre message encodé, où nous avons donc ajouté au message initial le syndrome, a été envoyé et est reçu par le destinataire.

  • Charge à lui d’en vérifier la bonne transmission.

Le destinataire sait quels bits correspondent au syndrome et lesquels correspondent au véritable message.

  • Il n’aura aucun souci pour reconstituer le syndrome et le message initial.
bannière à retenir

À retenir

Le destinataire opère les sommes de parité de chaque groupe :

  • s’il obtient 000000, alors il n’y a pas d’erreur ;
  • s’il obtient un nombre binaire différent, alors ce nombre binaire, une fois converti en décimal, lui indiquera la position du bit erroné.
  • L’erreur pourra même être corrigée.

Ce sont des règles mathématiques (et logiques) qui expliquent cela – n’hésitez pas à approfondir, vous en comprendrez sans doute la raison.

  • Ici, toutefois, nous nous contenterons d’illustrer par l’exemple.
bannière exemple

Exemple

Imaginons que le destinataire reçoive le message :

0\blue 0 1\blue 1 11 0\blue 0 00 0\red0 11

Nous savons que l’erreur est sur le bit 66 (en rouge). À la réception, le destinataire, lui, ne sait même pas qu’il y a une erreur.
Il effectue donc le contrôle, en effectuant pour chaque groupe (toujours les mêmes) les sommes de parité, jusqu’à obtenir aa, bb et cc :

  • pour le groupe de aa, 0+0+0+1=10+0+0+1=1, qui est impair,
  • a=1a=1 ;
  • pour le groupe de bb, 1+1+0+1=31+1+0+1=3, qui est impair,
  • b=1b=1 ;
  • pour le groupe de cc, 0+1+0+1=20+1+0+1=2, qui est pair,
  • c=0c=0.

Le destinataire obtient au final : 1102=610110{\tiny 2}=6{\tiny 10}.

  • Il sait maintenant que le bit 66 est erroné.

Et, le binaire étant bien fait, si ce n’est pas une valeur, alors c’est l’autre, il peut corriger l’erreur sur le bit 66

  • Le message devient :

0\blue 0 1\blue 1 11 0\blue 0 00 0 1\xcancel{\red 0}\ \green 1 11

Le destinataire peut maintenant extraire maintenant le message initial, il lui suffit de retirer les trois bits du syndrome :

11 00 11 11
  • Il s’agit bien du message que nous voulions transmettre.

Prenons un autre exemple, pour finir de nous convaincre.
Considérez le message suivant, reçu par le destinataire, où le bit erroné est cette fois le bit 33, et faites vous-même le calcul (cela vous entraînera) :

0\blue 0 1\blue 1 0\red 0 0\blue 0 00 11 11
  • Il vous faut trouver 0112=310011{\tiny 2}=3{\tiny 10}.

Conclusion :

La sécurité du transfert d’information, où l’on s’assure que le message reçu est bien celui envoyé, est un enjeu primordial de nos jours : l’immense majorité des communications reposent sur les réseaux. Il s’agit donc d’un domaine où de nombreuses recherches informatiques sont faites, qui s’attachent à trouver le bon équilibre entre poids des données et fiabilité de la communication.

Dans ce cours, nous en avons fait une première approche, en regardant des codes simples mais qui nous ont permis de comprendre comment l’on pouvait opérer des contrôles et des corrections automatiques sur des messages comportant une erreur.
En théorie, nous pouvons avoir des codes qui permettent les distances minimales que l’on souhaite, et donc un nombre d’erreurs corrigibles aussi élevé que l’on veut.