Previous Up

Chapitre 6  Exercices corrigés

1  Enoncés

Les exercices corrigés suivants permettent soit d'introduire des notions nouvelles sans connaissance préalable (Exercice 1), soit de récapituler plusieurs outils introduits au fil de ces pages (Exercice 2), soit enfin d'illustrer une section précise du document (Exercice 3).

1.1  Exercice 1

La méthode des codes correcteur d'erreurs, introduite ici, permet d'expliquer le fait que les transmissions numériques sont plus fiables que les transmissions analogiques.

Supposons que les données à transmettre sur un réseau quelconque soient constituées de 16 bits (ce qui correspond à un mot mémoire de notre mini-ordinateur). La ligne de transmission, n'étant pas fiable (certains bits peuvent être modifiés ou perdus pendant leur transfert), on va utiliser une version simplifiée de cette méthode des codes correcteurs pour améliorer la transmission. Elle consiste à effectuer les transformations suivantes :
Example 5   La suite de bits 1101001101011000 donne lieu au tableau suivant :

          colonne de contrôle
  1 1 0 1 1
  0 0 1 1 0
  0 1 0 1 0
  1 0 0 0 1
           
ligne de controle 0 0 1 1  

Les données à transmettre sont donc : 1101001101011000 1001 0011.
  1. Montrer que si on reçoit le message suivant : 000?1?011100?010100?0110, où les "?" représentent des bits inconnus (de valeur incompréhensible), il est possible de reconstituer en entier les données qui ont été envoyées (y compris les bits de contrôle).
  2. Reconstituer autant que possible le message : 1??1101?110?0?001?0?1?10
  3. Montrer que le message suivant : 111001110010110011110101, transmis suivant le même mode, est incohérent. Quelle est l'explication la plus simple pour rendre compte de cette incohérence et comment y remédier ?

1.2  Exercice 2

Voici les codes ASCII, sur un octet chacun, de quelques caractères alphabétiques :
  1. Ecrire les valeurs en base 10 correspondant à ces nombres binaires.
  2. Quel doivent être les codes ASCII de D et de d ? De Z et de z ?
  3. Donner la description (sous forme de graphe) d'une machine de Turing permettant de transformer le code ASCII (en binaire) d'une lettre minuscule écrit sur son ruban en le code ASCII de la lettre majuscule correspondante.
  4. Donner le contenu de la mémoire d'un ordinateur de type Von Neumann (avec le schéma habituel) tel que si le code ASCII d'une lettre minuscule se trouve stocké à l'adresse 0110, alors après exécution du programme contenu dans cette mémoire, le code ASCII de la lettre majuscule correspondante sera stockée à l'adresse 1001.

1.3  Exercice 3

Ci-jointe une liste de logiciels, avec leur fonctionnalité principale : Dans quel ordre ces différentes couches doivent-elles être présentes dans un ordinateur (sans oublier le système d'exploitation) pour permettre d'interroger oralement une base de données ?

2  Corrections

2.1  Exercice 1

  1. Pour reconstituer la valeur des bits manquant, il suffit de reconstituer le tableau ayant servi au calcul de ligne et de la colonne de contrôle et de vérifier la valeur du bit de parité sur chaque ligne et sur chaque colonne de ce tableau. Le message 000?1?011100?010100?0110 devient donc :

              colonne de contrôle
      0 0 0 1 1
      1 0 0 1 0
      1 1 0 0 0
      0 0 1 0 1
               
    ligne de controle 0 1 1 0  

    On ne peut déduire la valeur d'un bit inconnu qu'à condition qu'il soit le seul indéterminé sur sa ligne ou sur sa colonne (contrôle compris). Il faut donc respecter un certain ordre...
    Le message envoyé était donc : 000110011100001010010110.
  2. Le message 1??1101?110?0?001?0?1?10 donne lieu au tableau :

              colonne de contrôle
      1 1 0 1 1
      1 0 1 1 1
      1 1 0 0 0
      0 ? 0 0 ?
               
    ligne de contrôle 1 ? 1 0  

    Tous les bits inconnus n'ont pas pu être déduits. Le message reconstitué au maximum est le suivant : 1101101111000?00110?1?10
  3. Le message transmis donne lieu au tableau suivant :

              colonne de contrôle
      1 1 1 0 1
      0 1 1 1 1
      0 0 1 0 1
      1 1 0 0 1
               
    ligne de controle 0 1 0 1  

    La 3ème colonne et la 4ème ligne de ce tableau (en gras) ne respectent pas les règles de construction des bits de contrôle. La raison la plus probable de cette incohérence est une erreur de transmission du bit situé à l'intersection de cette ligne et de cette colonne. Si en effet, la valeur de ce bit passe de 0 à 1, le tableau devient cohérent.
Le principe des codes correcteurs d'erreurs est donc d'ajouter des informations redondantes aux données transmises, pour contrôler leur cohérence et donc corriger les erreurs.

2.2  Exercice 2

  1. Les valeurs en base 10 correspondant aux codes ASCII fournis sont les suivantes :
  2. La suite des codes ASCII respectant l'ordre alphabétique, les codes manquant sont :

  3. Pour passer du code ASCII d'une lettre minuscule à celui de la majuscule correspondante, il suffit de transformer le 3ème bit en partant de la gauche de 1 à 0. Par ailleurs, les deux premiers bits sont toujours égaux à "01" et les 5 derniers bits ne sont pas modifiés. Supposons donc que le code ASCII d'une minuscule soit écrit sur le ruban, la machine de Turing la plus simple possible qui aura l'effet souhaité est décrite par le graphe de la figure 6.1.


    Figure 6.1: graphe de la machine de Turing de l'exercice 2


  4. En termes d'opération arithmétique décimale, transformer le code ASCII d'une lettre minuscule en celui de la majuscule correspondante revient à soustraire 32 à ce code. Cette opération suppose donc que le nombre 32 soit stocké quelque part dans la mémoire (à une adresse notée ad, différente des adresses imposées par l'énoncé), et que l'instruction élémentaire suivante : "0010 0110 ad 1001" soit stockée à l'adresse référencée dans le CO. La configuration de la figure 6.2 est donc une des solutions possibles (où ad vaut 0100) .


    Figure 6.2: machine de Von Neumann de l'exercice 2

2.3  Exercice 3

Les couches logicielles, de la plus "externe" à la plus "interne", doivent figurer dans l'ordre suivant :
Previous Up