Cours : Sécurité du transfert d'information

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).

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 à $0$ ;
• si la somme des autres bits est impaire, alors le bit de parité sera égal à $1$.
• 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 à $1$ est pair, alors le bit de parité sera égal à $0$ ;
• si le nombre de bits égaux à $1$ est impair, alors le bit de parité sera égal à $1$.
• Dans le message global, avant envoi, il y aura toujours un nombre pair de bits égaux à $1$.

À 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 à $1$, il saura qu’un bit est erroné et qu’une erreur de transmission est survenue.

Attention

Veillez à ne pas confondre :

• $0\purple10\purple1_{\tiny 2}=5_{\tiny 10}$, qui est un nombre impair ;
• la somme de parité est en revanche paire : $0+\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 :

(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=3$, qui est impair.

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

• C’est donc ce message qui est envoyé.

Distinguons maintenant deux cas.

• Le destinataire reçoit le message :

Il opère la somme de parité : $1+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 :

Il opère ici aussi la somme de parité : $1+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 $2$ erreurs :

Il opère la somme de parité : $1+\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 $2$.
• 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)$, parfois appelé code de Hamming $(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.

À retenir

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

• le $7$ indique la longueur totale du message une fois encodé ;
• le $4$ indique la longueur du message original (sur $1$ quartet, donc) ;
• le $3$ indique la distance minimale du code.

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 $d$ est la distance minimale, alors on peut corriger au maximum $\frac {d-1}2$ erreur(s).

• Avec une distance de $3$, ce qui est notre cas, nous pouvons corriger $1$ erreur.

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.

Exemple

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

$1$

$0$

$1$

$1$

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 $7$ bits et un message initial de $4$ bits.

• Notre syndrome aura donc $3$ bits.

Soit $a$, $b$ et $c$ les valeurs de ces $3$ bits. Le syndrome sera de la forme :

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.

À retenir

• En regardant les valeurs décimales du syndrome, nous voyons qu’il peut décrire la totalité des $7$ positions de notre message à $7$ bits, avec en plus une valeur supplémentaire, $0$, pour indiquer l’absence d’erreur.
• Intéressons-nous aux lignes surlignées en bleu clair : il s’agit de celles où $c$ a pour valeur $1$.
• Nous pouvons associer à $c$ les positions $1$, $3$, $5$ et $7$.
• De la même manière, nous pouvons associer à $b$ les positions $2$, $3$, $6$ et $7$.
• Enfin, nous pouvons associer à $a$ les positions $4$, $5$, $6$ et $7$.

Bit du syndrome	Positions associées
$a$	$4$	$5$	$6$	$7$
$b$	$2$	$3$	$6$	$7$
$c$	$1$	$3$	$5$	$7$

Maintenant, vous vous demandez sans doute où placer $a$, $b$ et $c$ dans notre message de $7$ 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 $1$, $2$ et $4$ (des puissances de $2$) –, et leur position sera celle qui appartient à leur groupe.

À retenir

• Soit le message initial :

$i_3$

$i_2$

$i_1$

$i_0$

• Soit $a$, $b$ et $c$ les bits du syndrome.
• Alors le message encodé sera de la forme :

$\blue c$

$\blue b$

$i_3$

$\blue a$

$i_2$

$i_1$

$i_0$

Exemple

Reprenons notre exemple :

$1$

$0$

$1$

$1$

• Nous obtenons :

$\blue c$

$\blue b$

$1$

$\blue a$

$0$

$1$

$1$

Vous vous demandez désormais, à partir du message initial, quelles valeurs donner à $a$, $b$ et $c$ 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.

À retenir

$a$, $b$ et $c$ 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, $a$, $b$ et $c$ compris, est paire.

Exemple

Revenons encore une fois à notre exemple :

$\blue c$

$\blue b$

$1$

$\blue a$

$0$

$1$

$1$

Nous savons que $a$ est associé aux positions $4$, $5$, $6$ et $7$. Faisons la somme de parité des bits en position $5$, $6$ et $7$ ($a$ étant donc à la position $4$) : $0+1+1=2$, qui est pair.

• $a=0$.

De la même façon, concernant $b$, pour les bits en position $3$, $6$ et $7$ : $1+1+1=3$, qui est impair.

• $b=1$.

Enfin, concernant $c$, pour les bits en position $3$, $5$ et $7$ : $1+0+1=2$, qui est pair.

• $c=0$.

Nous obtenons le message encodé :

$\blue 0$

$\blue 1$

$1$

$\blue 0$

$0$

$1$

$1$

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.

À retenir

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

• s’il obtient $000$, 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.

Exemple

Imaginons que le destinataire reçoive le message :

$\blue 0$

$\blue 1$

$1$

$\blue 0$

$0$

$\red0$

$1$

Nous savons que l’erreur est sur le bit $6$ (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 $a$, $b$ et $c$ :

• pour le groupe de $a$, $0+0+0+1=1$, qui est impair,
• $a=1$ ;
• pour le groupe de $b$, $1+1+0+1=3$, qui est impair,
• $b=1$ ;
• pour le groupe de $c$, $0+1+0+1=2$, qui est pair,
• $c=0$.

Le destinataire obtient au final : $110_{\tiny 2}=6_{\tiny 10}$.

• Il sait maintenant que le bit $6$ 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 $6$

• Le message devient :

$\blue 0$

$\blue 1$

$1$

$\blue 0$

$0$

$\xcancel{\red 0}\ \green 1$

$1$

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

$1$

$0$

$1$

$1$

• 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 $3$, et faites vous-même le calcul (cela vous entraînera) :

$\blue 0$

$\blue 1$

$\red 0$

$\blue 0$

$0$

$1$

$1$

• Il vous faut trouver $011_{\tiny 2}=3_{\tiny 10}$.