Avant-propos

Il est possible que les élèves n’aient pas l’intuition de la méthode dite « des bits de parité ». Nous proposons 2 variantes de cette séance. Dans la première (qui est décrite pas à pas, ci-dessous), cette méthode est élaborée collectivement. Dans la seconde (décrite rapidement en fin de séance), l’enseignant effectue un « tour de magie », que les élèves doivent comprendre.

Situation déclenchante

L’enseignant montre  une image similaire à celle étudiée en début de la Séance III-3.1 ainsi que son codage en binaire (on a retiré, ici, l’en-tête du fichier « P1 5 5 » indiquant qu’il s’agit d’une image en N&B de 5x5 pixels) :

0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0

L’enseignant demande aux élèves ce qui se passerait si, lors de la transmission, certaines erreurs étaient produites, de sorte que la valeur de certains pixels soit changée. Il change 1 valeur quelconque et demande à un élève de venir dessiner la nouvelle figure au tableau. Si la valeur changée est celle surlignée, la nouvelle image est :

0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0

Note pédagogique
Cette situation déclenchante est un problème volontairement très simple, qui permet de réinvestir et consolider ce qui a été vu à la Séance 1 (page 288).

Recherche : comment détecter une erreur (collectivement)

L’enseignant demande aux élèves comment on pourrait s’assurer que l’image que l’on reçoit est bien celle qui a été prise. Il ne s’agit pas ici de corriger d’éventuelles erreurs mais, dans un premier temps, de pouvoir les détecter. On dit aussi qu’on veut garantir « l’intégrité » des données.
Certains élèves peuvent avoir l’idée de rajouter une information supplémentaire. On peut décider, par exemple, de faire la somme des valeurs ligne par ligne et de rajouter un nombre qui code cette valeur. Ou, plus simple (et plus pratique…), de compter si le nombre de « 1 » présents sur chaque ligne est pair ou impair. Il s’agit alors d’ajouter à la fin de chaque ligne un nouveau chiffre de sorte que le nombre de « 1 » soit toujours pair sur chaque ligne.

• Si le nombre de « 1 » présents sur la ligne était pair, alors on ajoute « 0 » à la fin de la ligne. La nouvelle ligne, complétée, comprend toujours un nombre pair de « 1 ».
• Si le nombre de « 1 » présents sur la ligne était impair, alors on ajoute « 1 » à la fin de la ligne. La nouvelle ligne, complétée, comprend maintenant un nombre pair de « 1 ».

Appliqué à la première image, cela donne :

0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0

0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1

On a ajouté une nouvelle colonne de façon à ce que, sur chaque ligne, le nombre de « 1 » soit pair. L’enseignant ferme alors les yeux et demande à un élève de changer une valeur, n’importe laquelle, sans lui dire. Il lui suffit désormais de compter, ligne par ligne, le nombre de « 1 » présents pour savoir sur quelle ligne se situe le problème.

Notes scientifiques :

• Cette méthode est couramment utilisée en informatique pour détecter (et corriger, voir ci-dessous) des erreurs dans la copie ou la transmission de fichiers.
• Le bit ajouté en fin de ligne s’appelle un « bit de parité ».

Recherche : comment corriger l’erreur ? (collectivement)

La classe remarque qu’elle est capable de dire s’il y a une erreur, mais pas de la corriger, car on ne sait pas quel pixel exactement a été changé : la seule chose que l’on sait, c’est le numéro de la ligne où le problème existe. Pour savoir quelle valeur exactement  a été changée, il faudrait connaître le numéro de la colonne.
L’enseignant demande à la classe comment faire. La réponse est, cette fois, plus facile à trouver par les élèves : il faut faire la même chose que précédemment mais en colonne plutôt qu’en ligne. On compte le nombre de « 1 » présent dans chaque colonne et on ajoute une dernière ligne de façon à ce que, dans chaque colonne, le nombre de « 1 » soit toujours pair.
Appliqué à la première image, cela donne désormais :

0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0

0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0

Un élève peut maintenant changer 1 valeur n’importe où et l’enseignant montre qu’il est capable de détecter cette valeur (en croisant l’information sur la ligne et la colonne modifiée) et donc de la corriger.

Note scientifique
Le bit de parité ajouté dans le coin en bas à droite permet de détecter (et corriger) une erreur qui se serait produite, non pas sur les bits de la grille 5x5 (l’image d’origine) mais sur les bits de parité eux-mêmes.

Exercice (par groupes)

Une fois la méthode expliquée, l’enseignant répartit les élèves par binômes ou groupes de 4 (en fonction du matériel disponible) et distribue un jeu de cartes à chaque binôme. Les élèves s’entrainent à détecter et corriger les erreurs.

• L’élève qui est testé se cache les yeux tandis que le reste du groupe s’accorde sur un motif dessiné à l’aide de cartes (chaque carte coté « personnage » équivaut à « 1 » tandis que chaque carte neutre, également appelée « dos taroté », équivaut à « zéro »).
• L’élève testé ouvre les yeux et place les cartes supplémentaires (« bits de parité »).
• l’élève-testé se cache à nouveau les yeux pendant que les autres élèves retournent 1 carte.
• L’élève-testé doit être capable, en regardant les bits de parité, de savoir quelles lignes et colonnes ont été changées, et ainsi de corriger les erreurs.

Note pédagogique
Si la classe a un doute sur le fait que l’élève utilise bien la parité plutôt que simplement sa mémoire pour identifier et corriger l’erreur, il suffit d’augmenter le nombre de cartes (c.-à-d. le nombre de bits), et d’éviter de dessiner un motif facilement mémorisable.

Mise en commun

L’enseignant s’assure que tous les élèves ont compris la méthode des bits de parité et leur demande ce qui se passe si 2 erreurs sont produites par exemple sur la même ligne. La classe s’aperçoit alors que, dans ce cas, l’erreur est détectable car la parité de certaines colonnes a changé, mais l’erreur n’est pas corrigible car on ne sait pas quelle ligne a été corrompue.
La classe discute des moyens permettant de minimiser ce risque : il faut par exemple augmenter le nombre de bits de parité (au lieu d’en mettre tous les 5 bits, comme on l’a fait ici, on peut en mettre tous les 3 bits). Plus il y a de bits de parité, plus il est possible de détecter d’erreurs… mais, en contrepartie, plus il faut augmenter la quantité d’information à stocker (et à transférer, ensuite).
Dans la pratique, introduire 1 bit de parité tous les 5 bits revient à ajouter 20% d’information, et donc augmente la taille des fichiers de 20%. Selon l’importance des données et la fiabilité des processus de stockage ou transmission, on peut décider de descendre à 10% ou même 1% : c’est un compromis à trouver !

Conclusion et traces écrites

La classe synthétise collectivement ce qui a été appris au cours de cette séance :

• Un ordinateur représente n’importe quelle information en utilisant un codage binaire
• Lors de l’enregistrement ou de la manipulation (copie, transfert…), des données, il peut y avoir des erreurs.
• Certaines méthodes, comme l’ajout de bits de parité, permettent de détecter et corriger ces erreurs. Ces méthodes nécessitent d'augmenter la quantité d'information à stocker.

Les élèves notent ces conclusions dans leur cahier de sciences. L’enseignant, quant-à-lui, met à jour l’affiche « qu’est-ce que l’informatique ? ».

Variante

Il est possible de mener cette séance autrement, en s’éloignant un peu de la démarche d’investigation dans la mesure où le problème posé n’a pas de rapport avec ce qui a été vu lors des précédentes séances. Néanmoins, cette variante peut être intéressante ne  serait-ce que pour son caractère ludique.

• L’enseignant explique qu’il va faire un « tour de magie » (cette variante est inspirée d’une activité extraite du livre Computer science unplugged traduit en français sous le titre L’informatique sans ordinateur. Cf. bibliographie).
• La classe est divisée en 4 groupes, chacun disposant, sur la table 25 cartes de façon à former un motif de 5 lignes par 5 colonnes.
• L’enseignant passe d’une table à l’autre et place des cartes supplémentaires à la fin de chaque ligne et colonne de façon à respecter la parité (le nombre de cartes coté « motif » doit être pair), mais sans expliquer aux élèves ce qu’il fait.
• Il demande ensuite à chaque groupe de changer 1 carte (une seule) puis il passe dans les groupes et révèle la carte qui a été changé.
• Le reste de la séance peut être mené de façon similaire à ce qui est décrit plus haut, de façon à ce que les élèves découvrent et s’approprient la méthode de l’enseignant.

Les élèves peuvent refaire ce tour de magie en famille : succès garanti !

Prolongement

Un exercice en ligne permet de s'essayer à la reconstitution d'une image corrompue.

Prolongements pour le collège (cycle 4)

La classe peut prolonger ce travail en cherchant par exemple l’ensemble de 4 erreurs qui reste indétectable et incorrigible. Elle peut également s’intéresser aux applications pratiques de cette méthode dite de parité.

• Le code ASCII (codage des lettres de l’alphabet et de la ponctuation) se fait sur 7 bits, tandis que les ordinateurs manipulent couramment des paquets de 8 bits (des « octets ») : le dernier bit est utilisé comme bit de parité
• Les connections sur Internet utilisent des protocoles (comme TCP-IP) qui utilisent des bits de parité pour vérifier l’intégrité des données transmises.
• Le numéro de sécurité sociale identifie de manière unique une personne française. Ce numéro contient, à la fin, un nombre à 2 chiffes servant à vérifier l’exactitude des précédents. Ici, il ne s’agit pas de parité, mais d’une somme de contrôle : on additionne tous les nombres précédents et on fait la différence entre cette somme et 97. On divise alors cette somme par 97 et on garde le reste : c’est le nombre de contrôle.
• L’IBSN, numéro unique d’identification d’un livre, contient également un chiffre de contrôle, calculé de façon similaire, quoi qu’un peu plus compliquée, que les chiffres de contrôle du numéro INSEE.
• Les codes-barres utilisent également des contrôles du même type.
• Ces exemples (et d’autres) sont détaillés sur cette page : http://therese.eveilleau.pagesperso-orange.fr/pages/truc_mat/textes/cles.htm