Détection d'erreurs

Durée estimée: 45 minutes

Introduction

Comme nous l'avons vu, toutes les informations ou données peuvent être représentées par des bits : des 0 et 1.

Envisagez maintenant que votre banque fasse un transfert électronique de fonds et qu'un des bits passe de 0 à 1 au cours du transfert !
Ce type d'erreur peut arriver dans la transmission ou au moment de l'écriture sur disque. Pour vous, ça peut faire une grosse différence ! Par exemple, pour un virement de 1€, écrit sur 8 bits (00000001), si le bit de gauche passe à 1 (pour devenir 10000001), le virement va se faire sur 129€. Et pour une valeur sur 16 bits, l'erreur (de 0000000000000001 à 1000000000000001) ferait passer le de 1 à 32 769 € !

Quand un changement de bit de ce type se produit par erreur, est-il possible de détecter qu'une erreur s'est produite ?
Cette vidéo issue d'un exercice décrit page 31 de CS unplugged - l'informatique déconnectée montre, avec un jeu de cartes que l'on peut s'apercevoir qu'une carte (ou un bit) a changé. Dans cette vidéo, vous pouvez imaginer que la bascule d'une carte est équivalente à la bascule entre 0 et 1.

Regardez avec attention et essayez de deviner la méthode utilisée pour identifier la carte qui a changé. (rappelez-vous l'indice : la méthode est liée à l'ajout du 6° rang et de la 6° colonne, ...)


Recherche de la solution :
Quel est l'algorithme utilisé ?

L'application à gauche a été faite par Richard Zheng, élève au lycée Westhill. C'ets un moyen d'essai pour aider à comprendre et résoudre le problème.

A chaque fois que l'on rejoue, l'application génère de façon aléatoire un premier carré de 5 x 5 Androids, Puis ajoute la 6° colonne et la 6° ligne. L'indice de la vidéo nous dit que c'est pour nous aider à résoudre le problème. Il y a donc quelque chose à trouver sur la manière dont cette 6°colonne et cette 6° ligne sont construites. Essayez en mélangeant les cartes plusieurs fois. Y a t-il une propriété du tableau 6x6 qui est toujours vraie avant que l'on retounre une carte et qui ne l'est plus après ? L'astuce tient dans cette propriété.

Lorsque vous avez trouvé, essayez de définir un algorithme (pseudocode) qui permet d'identifier la carte retournée.

Activité par groupe (POGIL)ou pour la classe (30 minutes)

Constituez des équipes ("POGIL") de 4 et donnez à chacun un des rôles ci-dessous. Notez les réponses aux questions traitées dans cette fiche. (Faites une copie du fichier pour avoir une version éditable/modifiable.)
Rôle Responsabilité
Faciliteur Gère les interactions avec l'appli Parity Magic pour aider à l'évaluation des algorithmes proposés par l'équipe.
Porte-parole Rend compte des résultats de l'équipe à l'enseignant et aux autres équipes.
Contrôleur qualité Prend note de toutes les réponses & questions et fournit les rélfexions de l'équipe à l'équipe et à l'enseignant.
Analyste (méthode) Examine comment l'équipe pourrait travailler et apprendre de façon plus efficace.

Correction d'erreur : Questions d'analyse critique à traiter

L'enseignant donne à chaque équipe un jeu de cartes.
Vous pouvez considérer qu'une carte vaut 0 de face et 1 de dos. L'objectif à atteindre est que votre équipe puisse expliquer et montrer à la classe quelle est le principe de détection d'erreur et comment fonctionne l'algorithme qui permet de trouver la carte modifiée : C'est à dire que :

  • un élève ou l'enseignant va mettre les 5x5 cartes de dos ou de face, comme il veut.
  • un membre de l'équipe ajoutera la 6° colonne et le 6° rang.
  • Une carte sera retournée, sans que l'équipe puisse le voir.
  • La carte retournée sera ensuite montrée par un membre de l'équipe.

    • Questions à traiter :
    1. Dans la vidéo : est-ce que l'orientation des cartes sur la 6° ligne et la 6° colonne répondent à une règle ou pas ? Si oui quel est cette règle ou l'algorithme qui fixe l'orientation de la carte ?
    2. INDICE: Comptez le nombre de cartes qui sont de face dans chaque ligne et chaque colonne ? Que remarquez-vous ? Qu'est-ce que ces nombres ont en commun ?
    3. Exercice Pratique: chaque memre de l'équipe doit s'exercer à faire le tour de magie avec le jeu de cartes ou avec l'application à l'écran.
    4. (Pour votre Portfolio) Expliquez le "tour de magie" ? Bien entendu, ce n'est pas de la magie. C'est un algorithme. Donc décrivez l'algorithme qui permet de trouver la carte retournée, sous forme de pseudocode.
    5. (Pour votre Portfolio) Le tour de magie permet toujours de retrouver la carte retournée, si une seule a été retournée. Serait-il toujours possible de déterminer si une erreur s'est produite dans le cas où une deuxième carte s'était également retournée ? Faites des essais avec le jeu de cartes ou l'appli pour aider à traiter cette question.
    6. Dans le cas illustré, les 25 ou 5 x 5 premières cartes correspondent aux données, et les 11 suivantes (5+6) sont dédiées à la détection d'erreur. Sur le total de 36 cartes, 69% (25/36) sont des bits de données et 31% (16/36) des bits de contrôle ou de détection d'erreur.
      Dans le cas où le nombre de bits de données était de 9 (3x3). De combien de bits de contrôle aurait-on besoin ? Et quel serait le pourcentage de bits de données par rapport au nombre total de bits ?

Auto-contrôle


Not yet started
1 point
Trouvez le bit modifié.
Dans cette table, identifiez le bit qui a été inversé.
1001
1111
0011
0100

Not yet started
1 point
Complétez les données avec la ligne et la colonne de contrôle.
Quelle solution correspond à l'ajout de la ligne et de la colonne de contrôle, à cette table de 3 X 3 bits ?
(La bonne table de 4x4 doit permettre de détecter automatiquement si un bit est inversé et lequel)
100
111
001

En savoir plus ?

Cette leçon a permis de voir qu'il est possible de détecter certains types d''erreurs dans les documents numériques. La technique de contrôle ou de détection illustrée ici est le contrôle de parité. Elle ajoute de la redondance c'est à dire des bits supplémentaires qui permettent de savoir si le message reçu contient une erreur.

Que se passe t-il si les erreurs portent sur plus de 1 bit :
Est-il possible de détecter automatiquement la présence d'une ou deux erreurs ?
Est-il également possible de la ou les corriger ?
Les réponses à ces questions sont Oui et Oui.

Si vous voulez en savoir plus sur ce sujet, les références ci-dessous peuvent être utiles.

Pour votre Portfolio

Créez une page nommée : Détection des erreurs dans la catégorie "réflexions" de votre portfolio, puis répondez aux questions suivantes :

  1. (POGIL) Décrivez (enpseudo-code) un algorithme qui permet de d'identifier la care retournée
  2. (POGIL) Le tour de carte a montré qu'il est toujors possible d'identifier la carte retournée si il n'y en n'a qu'une. Et si deux cartes ont été retournées : peut-on le détecter ? et peut-on identifer quelles cartes ont été retrournées error occurred if two cards were flipped? Expliquez pourquoi ou comment.