Objectifs

Cette activité va présenter deux techniques qui peuvent être utilisées pour détecter des erreurs dans les séquences de bits (et parfois les corriger).

Mise en place

Cette activité se déroule en classe, à l'aide d'une flute pour faire des sons longs et courts, ainsi que des cartes de couleurs.

Cette activité est inspirée de l'activité "Tour de magie: retourner les cartes" ("Card Flip Magic") de cs-unplugged que vous pouvez retrouver à l'adresse: http://csunplugged.org/error-detection. Pour plus de renseignements sur cs-unplugged, voir: http://csunplugged.org/.

Introduction

Cette activité va présenter quelques techniques simples, utilisées pour trouver les erreurs dans les séquences de bits, et les corriger dans certains cas. Deux techniques vont être présentées: la redondance et le bit de parité.

Présentation

Tout d'abord, expliquons l'utilité de la recherche d'erreurs. Il est logique que lorsque l'on veut envoyer une information à un ami, on ne veut pas que l'information soit transformée pendant le trajet, et que l'ami reçoive quelque chose d'incorrect à la fin. Si j'envoie le mot "mot" à mon voisin, je ne veux pas qu'il reçoive "pot", par exemple. Des techniques ont donc été mise en place pour trouver les erreurs lorsqu'il y en a, et les corriger dans certains cas.

Dans le monde des ordinateurs, il peut arriver qu'il y ait des erreurs dans les transmissions de séquences de bits. Un ordinateur envoie "1100" et l'autre ordinateur reçoit "1101". Voici donc deux techniques, ainsi que leurs avantages et inconvénients.

Première technique: La redondance

Commençons par la redondance. Comme son nom l'indique, le but est de répéter les bits que l'on envoie. On peut choisir le nombre de fois que l'on répète les bits, mais plus on répète, plus on utilise de bits "inutiles" (qui ne portent pas l'information) et donc ça augmente le temps que l'on met pour lire toute la séquence (si on répète tout 3 fois et qu'on envoie seulement 3 bits, il faudra en lire 9!), mais plus on répète, plus on a de chance de trouver l'erreur. Illustrons cela dans des exemples. Imaginons que l'on veuille envoyer 1100:

• Si on répète deux fois chaque bit, on envoie 11110000. Ce qui veut dire que l'on peut repérer une erreur (mais pas deux erreurs successives!) mais on ne peut pas la corriger. Par exemple, si on reçoit 11110001, comme on doit recevoir les bits en double, on sait que la dernière paire est fausse! Cependant, on ne sait pas si on aurait du recevoir 11 ou 00. On l'a détecté, mais on ne peut donc pas la corriger. Maintenant, si les deux derniers bits sont erronés, on reçoit 11110011, ce qui semble correct au receveur mais qui ne l'est pas, en fait!
• Pour améliorer cela, on peut donc répéter trois fois au lieu de deux! On envoie donc 111111000000 (12 bits au lieu de 4!). De cette manière, si un bit est faux, on sait le repérer ET le corriger. Si deux bits redondants sont faux, on sait repérer l'erreur mais on va la corriger de la mauvaise manière, et si les trois bits redondants sont faux, le receveur va accepter la séquence alors qu'elle est fausse. Montrons cela:
  • si le receveur reçoit 111111000001: alors il sait que la dernière séquence de 3 bits est fausse car c'est 001 (et ce n'est pas 3 bits les mêmes). Comme il est plus probable qu'il y ai une faute et pas deux, il va la corriger et va donc recevoir la bonne séquence de bits.
  • si le receveur reçoit 111111000011: alors il va faire le même raisonnement qu'au dessus, sauf qu'il va mal corriger. Comme il a 011, il va le transformer en 111 alors que c'était 000 au départ (c'est pour ça qu'on est pas obligé de corriger, et que l'on peut juste signaler qu'il y a une erreur).
  • si le receveur reçoit 111111000111: alors il va penser que la séquence est correcte, alors qu'il y a 3 erreurs à la fin.
• Pour améliorer encore, on peut répéter 4, 5, 6 ou plus encore... Mais plus on répète, plus on a de bits à envoyer. Il faut donc faire un choix entre le nombre de bits que l'on veut envoyer et le niveau de détection que l'on veut avoir.

Deuxième technique: Le bit de parité

La deuxième technique est le bit de parité. Le principe est simple également: ajouter un bit à la fin de la séquence de bit, de sorte que la somme des 1 de la séquence donne un nombre pair. Si on veut envoyer 1100, on va envoyer 11000 (on ajoute un 0 à la fin car 1+1 = 2, ce qui est pair). Si il y a une erreur (ou plus généralement, un nombre impair d'erreurs) dans la séquence (un 0 changé en un 1, ou un 1 changé en un 0), cela va donner un nombre impair, et donc on va savoir qu'il y a une erreur dans la séquence (mais on ne sait pas où elle est!). Par contre, si il y a deux erreurs (ou plus généralement, un nombre pair d'erreurs) alors les erreurs vont passer inaperçues pour le receveur (car la somme sera paire). Si le receveur reçoit 11110 au lieu de 11000, il va trouver ça correct, alors que ça ne l'est pas.

Il existe une alternative à cette dernière technique. Dans le cas où ce que l'on envoie est représenté par des lignes et des colonnes (comme une image, voir l'activité "stocker une image"), on peut mettre un bit de parité par ligne et un bit de parité par colonne. De cette manière, si il y a une erreur, on va non seulement pouvoir la détecter, mais on va aussi pouvoir la corriger. Si il y a deux erreurs, alors on peut aussi les détecter et les corriger si elles sont sur des lignes et des colonnes différentes. Si elles sont sont sur une même ligne OU une même colonne, alors le bit de parité pour cette ligne ou cette colonne sera pair et on ne va pas savoir trouver où se trouve l'erreur (mais on aura quand même détecter une erreur sur les deux lignes (ou colonnes selon le cas) différentes). Illustrons ça par un exemple:

	           1100 0                        1101 0
	on envoie: 0011 0 et le receveur reçoit: 0011 0

	           1111                          1111

Dans ce cas, il y a une seule erreur: il y a un 1 au lieu d'un 0 tout en haut à droite (sans compter le bit de parité). On remarque donc que si on additionne les bits de la première ligne, c'est impair, et si on additionne les bits de la dernière colonne, c'est impair aussi. Ce qui veut dire que l'erreur est au croisement de la première ligne et de la dernière colonne, c'est le bit tout en haut à droite. On l'a donc repéré ET corrigé. Maintenant, présentons un cas où il y a deux erreurs:

	           1100 0                        1111 0
	on envoie: 0011 0 et le receveur reçoit: 0011 0

	           1111                          1111

Il y a deux erreurs dans la première ligne, mais ça ne se voit pas car la somme est paire! Par contre, la somme de la dernière et de l'avant-dernière colonne est impaire. Ce qui veut dire que l'on a détecté deux erreurs, mais qu'on ne sait pas les corriger car on ne sait pas où elles sont (dans la première ou la deuxième ligne? On ne sait pas... Les deux lignes ont une somme paire, elles ont l'air correctes...)! Voici une dernière situation où il est impossible de détecter les erreurs:

	           1100 0                        1111 0
	on envoie: 0011 0 et le receveur reçoit: 0000 0

	           1111                          1111

Dans cet exemple, il y a quatre erreurs. Mais le receveur ne va pas le détecter. En effet, la somme des éléments de chaque ligne est paire, et la somme des éléments de chaque colonne est paire également...

Conclusion

On a donc pu voir qu'il est possible de détecter des erreurs (et parfois les corriger) avec des techniques simples. Cependant, il y toujours l'inconvénient que l'on doive ajouter des bits supplémentaires (les bits de la redondance ou les bits de parité selon la technique).

L'exercice

Dans l'activité destinée aux élèves, le but sera de s'échanger des messages et de trouver l'erreur dans les messages, à l'aide de sons de flute ou de cartes double-face. Ils vont pouvoir constater que l'on peut ajouter des bits pour trouver des erreurs et parfois les corriger (ce qui fait que c'est plus long à lire). Ils vont pouvoir aussi constater que ça ne marche pas à tous les coups.

Cette activité est inspirée de l'activité "Tour de magie: retourner les cartes" ("Card Flip Magic") de cs-unplugged que vous pouvez retrouver à l'adresse: http://csunplugged.org/error-detection. Pour plus de renseignements sur cs-unplugged, voir: http://csunplugged.org/.

• Fiche pédagogique (pdf Δ, docx Δ)
• Synthèse pour les élèves (pdf Δ, docx Δ)
• Matériel:
  • Pas de matériel spécifique pour cette activité.

Cette activité est inspirée de l'activité "Tour de magie: retourner les cartes" ("Card Flip Magic") de cs-unplugged que vous pouvez retrouver à l'adresse: http://csunplugged.org/error-detection. Pour plus de renseignements sur cs-unplugged, voir: http://csunplugged.org/.