TCA 101
Codes de Hamming

Aux 4 chiffres binaires d'un message m on ajoute 3 chiffres de contrôle calculés modulo 2 par les formules :

c1 = m2 + m3 + m4
c2 = m1 + m3 + m4
c3 = m1 + m2 + m4

  1. Calculer les chiffres de contrôle pour le message 1101.

  2. On suppose que le chiffre m1 est détérioré (inversé) lors d'une transmission, et on note m'1m2m3m4 c1c2c3 le message reçu. Le récepteur recalcule des chiffres de contrôle c'1c'2c'3, et les compare à c1c2c3. Exprimer les c'i en fonction des ci.

    Même question si le chiffre inversé est m2 (on suppose qu'un seul chiffre est inversé durant la transmission). Idem pour m3 et m4.

  3. En déduire que le calcul (modulo 2) des c'i - ci permet de détecter si le message a été transmis correctement, et de le corriger sinon, sous l'hypothèse qu'un seul chiffre (au plus) a été inversé.

  4. On considère la suite des trois chiffres c'i - ci comme la représentation binaire (de gauche à droite) d'un nombre e. Pour chaque valeur de e, indiquer l'action à effectuer pour corriger, si nécessaire, le message.

  5. Ecrire une procédure Maple controle qui calcule la liste des 3 chiffres de contrôle pour un message m représenté par une liste de 4 chiffres binaires. Ecrire une procédure coder qui ajoute les trois chiffres de contrôle à un message. Exemples d'exécution :
    > controle ([1, 1, 0, 1])
      

    [0, 0, 1]

    > coder ([1, 1, 0, 1])
      

    [1, 1, 0, 1, 0, 0, 1]

  6. Ecrire une procédure Maple decoder qui, à partir d'un message constitué de 4 chiffres binaires et de 3 chiffres de contrôle, reconstitue le message original dans le cas où un seul chiffre (au plus) a été inversé. Exemple d'exécution :
    > decoder ([1, 0, 0, 1, 0, 0, 1])
      

    [1, 1, 0, 1]

    Note : un corrigé Maple est disponible.

  7. Ecrire les formules qui permettent, sur le même principe, de protéger un message de 11 chiffres binaires, en ajoutant 4 chiffres de contrôle.

    Calculer la longueur du message qu'on peut protéger (en corrigeant les erreurs simples de transmission, c'est-à-dire les erreurs qui affectent un seul chiffre) avec n chiffres de contrôle.

    Note : un corrigé est disponible pour cette question.