Déjà plus de
1 million
d'inscrits !
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.
Bit de parité :
Nous choisissons ici la convention suivante :
Nous pouvons l’exprimer d’une manière plus simple :
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 à , il saura qu’un bit est erroné et qu’une erreur de transmission est survenue.
Veillez à ne pas confondre :
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 :
(Nous représenterons, dans ce cours, les codes sous la forme de tableau, pour plus de lisibilité.)
Regardons la somme de parité : , qui est impair.
Distinguons maintenant deux cas.
Il opère la somme de parité : , qui est pair.
Il opère ici aussi la somme de parité : , qui est impair.
Limites du bit de parité
Nous voyons tout de suite quelles sont les limites d’un tel contrôle.
Reprenons l’exemple ci-dessus. Le destinataire reçoit un message avec erreurs :
Il opère la somme de parité : , qui est pair.
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 code :
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 est la distance minimale, alors on peut corriger au maximum erreur(s).
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é.
Pour la suite, nous nous intéresserons au message :
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 bits et un message initial de bits.
Soit , et les valeurs de ces bits. Le syndrome sera de la forme :
Commençons par regarder le tableau suivant, qui donne les valeurs possibles du syndrome.
Syndrome | |||
Bit du syndrome | Positions associées | |||
Maintenant, vous vous demandez sans doute où placer , et dans notre message de bits. La réponse est logique :
Reprenons notre exemple :
Vous vous demandez désormais, à partir du message initial, quelles valeurs donner à , et dans notre message complété.
, et sont les bits de parité du groupe qui leur est associé.
Ainsi, la somme totale de chaque groupe est paire.
Revenons encore une fois à notre exemple :
Nous savons que est associé aux positions , , et . Faisons la somme de parité des bits en position , et ( étant donc à la position ) : , qui est pair.
De la même façon, concernant , pour les bits en position , et : , qui est impair.
Enfin, concernant , pour les bits en position , et : , qui est pair.
Nous obtenons le message encodé :
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.
Le destinataire sait quels bits correspondent au syndrome et lesquels correspondent au véritable message.
Le destinataire opère les sommes de parité de chaque groupe :
Ce sont des règles mathématiques (et logiques) qui expliquent cela – n’hésitez pas à approfondir, vous en comprendrez sans doute la raison.
Imaginons que le destinataire reçoive le message :
Nous savons que l’erreur est sur le bit (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 , et :
Le destinataire obtient au final : .
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
Le destinataire peut maintenant extraire maintenant le message initial, il lui suffit de retirer les trois bits du syndrome :
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 , et faites vous-même le calcul (cela vous entraînera) :
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.