Retour à la page principale

Accès à la partie pédagogique

Le contenu scientifique de cette partie de la formation est destiné aux enseignants. Tout en restant, nous l’espérons, accessible aux collègues de toutes origines, aussi bien néophytes que confirmés dans le domaine de la science informatique, il va volontairement très au-delà du contenu de l’activité destinée aux élèves. Il s’agit de répondre aux interrogations personnelles des enseignants, d’alimenter leur réflexion à l’occasion de la préparation d’une séance en classe, et de leur permettre de se sentir à l’aise vis-à-vis d’éventuelles questions des élèves.

Voici une version à télécharger :

Les notions d’informatique à acquérir pour les enseignants dans ce module sont divisées en sept chapitres. Chacun d’entre eux est présenté sous la forme d’une vidéo de trois à cinq minutes. Les textes et les diapositives utilisés sont disponibles sous forme de fichiers séparés à la suite de chaque vidéo.

Dans chaque chapitre, vous trouverez aussi :

• une rubrique Avez-vous retenu, comportant quelques questions sur le contenu de la vidéo (et leurs réponses)
• éventuellement, une rubrique Pouvez-vous définir, récapitulant les mots techniques introduits dans le chapitre, s’il y en a (les définitions sont à retrouver dans le glossaire )
• une rubrique Notions importantes, listant les points essentiels abordés dans la vidéo
• éventuellement, des Questions/Réponses pour apporter quelques compléments d’information qui ne sont pas abordés dans les vidéos
• une rubrique Question(s) d’approfondissement, comportant une ou des questions pour aller plus loin sur les idées présentées dans chaque vidéo, pour relier les vidéos entre elles, pour réfléchir à des points non abordés dans les vidéos,... (et leurs réponses)

Enfin, nous vous proposons un document supplémentaire, à consulter plutôt à la fin de la formation, pour vérifier si vous avez retenu l’essentiel du contenu de cette partie d’apport scientifique :

• Questionnaire vrai/faux d’autoévaluation (et sa solution)

1. Introduction

• Qu’est-ce-qu’un code détecteur et correcteur d’erreurs ? Pourquoi en avons-nous besoin ? Quel en est le fonctionnement général ?

• Avez-vous retenu :
  • De quels mots provient l’abréviation "bit" ?
  • Citer une origine possible des perturbations des transmissions numériques ?
  • Quelles sont les conséquences de ces perturbations ?
  • Pourquoi dit-on que les bits de contrôle sont redondants ?

Réponses

• Pouvez-vous définir :
  • Bit
  • Données binaires
  • Erreur
  • Bits d’information
  • Codage
  • Bits de contrôle
  • Décodage
  • Message émis
  • Message reçu

(les réponses se trouvent dans le glossaire)

• Notions importantes :
  • Omniprésence et transparence des codes détecteurs et correcteurs d’erreurs dans la transmission et le stockage des données numériques
  • Imprévisibilité et inévitabilité des perturbations

• Question d’approfondissement

2. Code de double parité

• Après avoir expliqué ce que sont les codes détecteurs et correcteurs d’erreurs et pourquoi ils sont indispensables aux communications numériques, nous présentons un premier exemple de code détecteur et correcteur d’erreurs. C’est celui qui est utilisé dans l’activité pour la classe. Il repose sur des notions mathématiques très simples (lignes et colonnes d’un tableau, nombres pairs et impairs).

• Avez-vous retenu :
  • Calculer le bit de parité permettant de compléter la ligne 0 1 1 0 0 selon le principe du code de double parité.
  • Trouver et corriger l’erreur dans le message ci-dessous, qui a été traité auparavant en utilisant le code de double parité :

    

Réponses

• Notion importante :
  • Fonctionnement du code de double parité

• Pourquoi, dans ce chapitre, le message est-il représenté sous la forme d’un carré de bits et non d’une séquence de bits comme dans le chapitre précédent ?
  En réalité, l’ordinateur travaille bien sur des séquences de bits, et il connaît la correspondance entre chaque bit de parité et les cinq bits dont il dépend.
  Sur le schéma ci-dessous, dans la partie du haut, les couleurs montrent comment construire la représentation sous forme d’un carré de bits à partir d’une séquence de bits. Ensuite, une fois le code correcteur appliqué, la partie du bas du schéma explique comment obtenir la séquence de bits calculée par l’ordinateur, en ajoutant les bits de parité à la fin de la séquence initiale.
  Ainsi, plutôt que de devoir expliquer comment passer de la séquence de bits de la première ligne à la séquence de bits de la dernière ligne, il est beaucoup plus simple, comme nous l’avons fait dans la vidéo, de présenter les calculs à l’aide des représentations sous forme de carrés de bits qui se trouvent au milieu.

• Quel est le rôle du 36e bit ?
  Ce bit, situé à l’intersection de la ligne et de la colonne ajoutées, est un bit de parité, calculé à partir de la colonne ou de la ligne des bits de parité. En effet, ces derniers sont des bits transmis comme les autres, et donc potentiellement sujets à des erreurs. Ce 36e bit sert uniquement à repérer une erreur dans la transmission des bits de parité. Il est remarquable qu’on puisse le calculer indifféremment à partir de la colonne ou de la ligne des bits de parité. Cela vient du fait qu’il ne dépend que de la parité du nombre de 1 dans l’ensemble du carré 5x5 initial. (En termes techniques, on dit que l’addition modulo 2 étant commutative et associative, le résultat obtenu est le même en sommant d’abord sur les lignes, puis sur la colonne obtenue, ou bien le contraire.)
  Sur le schéma ci-dessous, le message émis est à gauche, et le message reçu à droite : une erreur se produit parmi les bits de parité, et le code de double parité permet de la détecter et de la corriger. À noter que la détection/correction marche encore si c’est le 36e bit lui-même qui est modifié au cours de la transmission.

  

• Et si les données initiales ne comportent pas exactement 25 bits pour en faire un carré de 5x5 ?
  En premier lieu, nous verrons dans le prochain chapitre que les données initiales sont découpées en blocs d’une longueur fixe et adaptée pour chaque code. Mais quoiqu’il en soit, le code de double parité est heureusement assez flexible et s’adapte facilement à d’autres situations. Les schémas ci-dessous montrent quelques variantes de la version présentée dans la vidéo.
  • Un message initial de 9 bits, qui donne un carré de 3x3
    

    

• • Un message initial de 35 bits, qui donne un rectangle de 5x7
    

    

• • Un message initial de 23 bits, auquel sont ajoutés 2 bits "de remplissage" quelconques (par exemple des zéros) pour se ramener à un carré de 5x5
    

    

• • Un message initial de 28 bits, qui donne (par exemple) un rectangle de 4x7
    Dans ce dernier cas, le code de double parité fonctionne encore, comme on le voit sur le schéma. Cependant, il ne faut pas confondre les rôles des 0 et des 1. En effet, sur les colonnes, après ajout des bits de parité, les deux chiffres ne jouent pas un rôle symétrique : s’il y a un nombre pair de 1, alors il y a un nombre impair de zéros. Cette subtilité se présente chaque fois que le nombre de lignes (ou de colonnes) avant ajout des bits de parité est pair. L’introduction du code de double parité avec une situation initiale ne présentant pas ce risque de confusion nous a paru préférable.

    

• Question d’approfondissement

• Remarque : Les noms des personnages d’Alice et Bob qui apparaissent dans cette vidéo (illustrations non contractuelles) sont traditionnellement utilisés par les informaticiens pour nommer l’expéditeur et le destinataire d’un message, en particulier en cryptologie, c’est-à-dire en ce qui concerne la sécurité des échanges. Leur principale qualité semble bien être qu’ils commencent respectivement par A et B...

3. Codage par blocs

• Nous revenons plus en détails sur le mécanisme du codage et sur les conséquences de l’adjonction de bits de contrôle aux bits d’information. Les notions présentées dans cette vidéo sont les plus mathématiques de l’ensemble de ce module de formation, et poseront peut-être quelques difficultés à certains.

• Avez-vous retenu :
  • Les mots d’information sont découpés en : (une seule bonne réponse)
    • plusieurs blocs de longueur fixe
    • plusieurs blocs de longueur variable
    • La question n’a pas de sens.
  • Le nombre de mots de code : (une seule bonne réponse)
    • est supérieur à celui des messages reçus possibles
    • est inférieur à celui des messages reçus possibles
    • est identique à celui des messages reçus possibles
  • Si m est la longueur des mots d’information, r, le nombre de bits de contrôle, et n, la longueur des messages reçus, alors : (une seule bonne réponse)
    • n = m - r
    • n = m + r
    • n = m x r
    • On ne peut pas connaître n.

Réponses

• Pouvez-vous définir :
  • Le nombre m
  • Mot d’information
  • Le nombre r
  • Mot de code
  • Le nombre n
  • Messages possibles
  • Mot binaire

(les réponses se trouvent dans le glossaire)

• Notions importantes :
  • Les données initiales sont découpées en blocs de longueur fixe.
  • Le nombre de mot d’information et le nombre de mots de code sont égaux.
  • Plus les mots binaires sont longs, plus ils sont nombreux : l’ensemble de tous les mots binaires d’une longueur donnée est d’autant plus vaste qu’ils comportent plus de bits.
  • Le nombre de messages reçus possibles est plus grand que le nombre de mots de code.

• Remarque : Le découpage des données binaires en mots d’information se fait sans tenir compte de la signification de ces données. L’ensemble de la procédure de codage-détection-correction-décodage agit uniquement sur des flux de bits, indépendamment de ce qu’ils représentent (des nombres, des textes, du son, des images, de la vidéo,...).

• Questions d’approfondissement

4. Principe de la détection et de la correction des erreurs

• Les phases de détection et de correction de tous les codes détecteurs et correcteurs d’erreurs sont basées sur les mêmes idées, que nous présentons dans cette vidéo.

• Avez-vous retenu :
  • Un message reçu sans anomalie détectée :
    • est forcément le message émis
    • est probablement le message émis
    • La question n’a pas de sens.
    • Il y a toujours une anomalie détectée.
  • Quelle(s) proposition(s) est(sont) vraie(s) ?
    • Dans un message reçu, on peut toujours détecter les erreurs et les corriger parfaitement.
    • Dans un message reçu, on peut toujours détecter les erreurs mais pas les corriger à coup sûr.
    • Dans un message reçu, on ne peut pas détecter à coup sûr toutes les erreurs.
    • Dans un message reçu, on ne peut pas corriger à coup sûr les erreurs.
    • Dans un message reçu, on peut corriger à coup sûr certaines erreurs, mais pas forcément toutes.

Réponses

• Notions importantes :
  • Règle de détection
  • Pari de la détection
  • Règle de correction
  • Pari de la correction
  • Nature imparfaite des codes

• Dans la vidéo de ce chapitre, le destinataire détecte les messages reçus qui ne sont pas des mots de code. Mais comment fait-il ?
  Rappelons que les mots de code ne constituent qu’une partie des messages reçus possibles. Pour savoir si un message reçu particulier est un mot de code ou pas, il y a deux méthodes, selon le code utilisé : ou bien il est comparé à une liste de tous les mots de codes pour ce code, ou bien il est testé pour une certaine propriété qui caractérise les mots de code pour ce code. Par exemple, dans le cas du code de double parité, les mots de codes sont les messages qui vérifient la règle de parité sur les lignes et les colonnes : c’est cette propriété qui est testée sur les messages reçus.

• Question d’approfondissement

• Document annexe sur les probabilités. Ce document détaille les calculs de probabilités auxquels il est fait référence dans la vidéo. Sa lecture n’est absolument pas nécessaire pour comprendre le contenu de cette formation. Elle requiert quelques notions élémentaires de calcul de probabilités, et en particulier, il est nécessaire de connaître la loi binomiale. Avec ces calculs, il s’agit simplement de montrer aux personnes intéressées comment l’expression "très très probable" utilisée dans la vidéo peut être dotée d’une signification mathématique précise. Il est préférable de lire ce document après avoir terminé les sept chapitres du module, car les exemples utilisés sont détaillés dans les chapitres suivants.

5. Code par répétition

• Un autre exemple de code détecteur et correcteur d’erreurs. Il est encore plus simple que le code de double parité déjà utilisé comme exemple au chapitre 2 ! C’est pourquoi il aurait été dommage de ne pas l’évoquer, pour se rendre compte qu’ils reposent bien tous les deux exactement sur les mêmes principes, que nous avons présentés dans le chapitre précédent.

• Avez-vous retenu ?
  • Quel est le résultat obtenu en appliquant le code par répétition utilisé dans la vidéo sur les bits d’information : 0 1 1 0 0 ?
  • Les messages 101 000 111 100 001 ont été reçus après avoir subi un codage par répétition, comme présenté dans la vidéo. Quel est le résultat de la détection et de la correction des erreurs ?
  • Les messages 011 111 101 100 010 ont été reçus après avoir subi un codage par répétition, comme présenté dans la vidéo. Parmi les propositions suivantes, laquelle représente les messages émis les plus plausibles ?
    • 011 111 101 100 010
    • 111 111 000 000 000
    • 111 111 111 000 000
    • On ne peut pas savoir

Réponses

• Notion importante :
  • Fonctionnement du code par répétition

• Questions d’approfondissement

6. Comment comparer les différents codes ?

• Au-delà du code de double parité et du code par répétition, de nombreux autres codes détecteurs et correcteurs d’erreurs sont utilisés en pratique. Nous allons voir quelques paramètres permettant de les comparer entre eux.

• Avez-vous retenu :
  • Calculer la redondance et le rendement de la variante du code par répétition où on répète 4 fois chaque bit de l’information transmise (autrement dit, le mot de code associé à 0 est 00000, et le mot de code associé à 1 est 11111).
  • Ce code est-il plus efficace pour détecter les erreurs que le code de double parité ?
  • Ce code transmet-il plus efficacement l’information que le code de double parité ?

Réponses

• Pouvez-vous définir :
  • Redondance
  • Rendement

(les réponses se trouvent dans le glossaire)

• Notions importantes :
  • Efficacité de la détection et de la correction des erreurs
  • Efficacité de la transmission
  • Compromis
  • Mathématiques

• La redondance et le rendement sont-ils les seuls paramètres permettant de comparer des codes ?
  Non. En particulier, la redondance donne seulement une mesure très grossière de la capacité d’un code à détecter et à corriger les erreurs. Ce qui compte plus précisément, pour un code donné, c’est d’une part le nombre d’erreurs qu’il permet de détecter à coup sûr dans un message, et d’autre part le nombre d’erreurs qu’il permet de corriger correctement à coup sûr dans un message.
  Par exemple, pour le code par répétition, on est sûr que tous les messages comportant une ou deux erreurs sont détectés, mais les messages comportant trois erreurs ne le sont pas. De plus, tous les messages comportant une erreur sont correctement corrigés, mais ceux comportant plus d’une erreur ne le sont pas.
  Il arrive que deux codes ayant la même redondance n’aient pas les mêmes performances en matière de détection et de correction des erreurs, selon que la méthode de calcul des bits de contrôle est plus ou moins astucieuse. C’est là que les théories mathématiques interviennent.

• Pour en savoir plus :
  • Pour trouver un autre exemple de code, vous pouvez taper "code de Hamming" dans un moteur de recherche. Ce code utilise un peu d’algèbre linéaire (les matrices) et de calcul Booléen.
  • À notre connaissance, les ouvrages et les cours en ligne disponibles sont essentiellement destinés à un public d’étudiants en informatique ou en mathématiques de niveau L3 ou M1. Voici deux références en Français, parmi d’autres :
    • Bruno Martin - "Codage, cryptologie et applications" - éd. Presses Polytechniques et Universitaires Romandes (PPUR) - 2004
    • Josèphe Badrikian - "Codes correcteurs : Mathématiques pour téléinformatique" - éd. Ellipses - 2002

• Question d’approfondissement

7. Quelles sont les limites des codes détecteurs et correcteurs d’erreurs ?

• Nous avons vu dans le cas du code par répétition que toutes les anomalies ne sont pas forcément détectées ou corrigées correctement. Qu’en est-il pour le code de double parité ? Les exemples que nous donnons dans cette vidéo illustrent les différents aspects de la nature imparfaite des codes en s’appuyant sur l’exemple du code de double parité.

• Avez-vous retenu :
  • Au minimum, si on utilise le code de double parité, quel est le nombre d’erreurs dans un message si on détecte des erreurs sans pouvoir les corriger ?
  • Pour le code de double parité, existe-t-il des cas où des erreurs sont corrigées de façon inexacte ? Si oui, donner un exemple.
  • Existe-t-il des cas où le code de double parité ne détecte pas des erreurs existantes ? Si oui, donner un exemple.

Réponses

• Notions importantes :
  • Détecter une anomalie et ne pas savoir la corriger (correction ambigue)
  • Détecter une anomalie et effectuer une correction inexacte
  • Ne pas détecter une anomalie

• Comment la correction d’un message erroné se déroule-t-elle lorsque deux ou plusieurs mots de code ont autant de chance d’être le message émis ?
  C’est ce qui se passe dans les deux exemples ci-dessous :
  • à gauche, deux lignes et deux colonnes ne respectent pas la règle de parité. Il y a deux façons différentes de corriger en modifiant le moins de bits possibles : en agissant sur les bits qui se trouvent ou bien en ligne 2 colonne 2 et en ligne 4 colonne 5, ou bien en ligne 2 colonne 5 et en ligne 4 colonne 2. Dans les deux cas, deux bits sont corrigés, et les deux mots de code obtenus ont autant de chance l’un que l’autre d’être le message émis.
  • à droite, deux lignes ne respectent pas la règle de parité, et toutes les colonnes la respectent. Il y a six façons différentes de corriger en modifiant le moins de bits possibles : en agissant sur les bits en lignes 2 et 4 de n’importe quelle colonne. Dans les six cas, deux bits sont corrigés, et les six mots de code obtenus ont autant de chance les uns que les autres d’être le message émis.

Lorsqu’il y a une ambigüité sur le mot de code à choisir pour la correction, par convention, le message reçu n’est pas du tout corrigé. Parfois, une "erreur non corrigeable" est indiquée, parfois rien du tout. La raison de ce choix est de ne pas risquer d’introduire des erreurs supplémentaires dans le message reçu.

• Question d’approfondissement

8. Compléments.

• Le document annexe ci-dessous détaille les calculs de probabilités auxquels il est fait référence dans la vidéo du chapitre 4. Sa lecture n’est absolument pas nécessaire pour comprendre le contenu de cette formation. Elle requiert quelques notions élémentaires de calcul de probabilités, et en particulier, il est nécessaire de connaître la loi binomiale. Avec ces calculs, il s’agit simplement de montrer aux personnes intéressées comment l’expression "très très probable" utilisée dans la vidéo peut être dotée d’une signification mathématique précise.

• Glossaire

• Questionnaire vrai/faux d’autoévaluation

Retour à la page principale

Accès à la partie pédagogique