ED n·2 Algorithmique-Programmation---Corrigé-

• Construction d'algorithmes par raffinements successifs et fonctions
• Les fonctions en Ada
• Les types tableau

Exercice

Enonçé

On suppose qu'une matrice 8*8 (tableau à 2 dimensions) contient une séquence de 8 octets (chaque octet représentant un caractère ASCII 7 bits).
Cette séquence d'octets est le résultat d'une transmission de données. On souhaite détecter les éventuelles erreurs de transmission. Pour cela , on met en place un "contrôle de parité".
Le premier bit de chaque octet représente le bit de parité. Celui-ci vaut 0 si le nombre de 1 est impair, 1 s'il est pair. La première colonne contient donc les valeurs de parité de chaque ligne .

Notes

• Les données utiles sont donc représentées par une matrice 8*7. La première colonne n'apporte pas d'information (sinon la parité).
• Les caractères codés en ASCII 7 bits sont les caractères usuels à l'exclusion des caractères accentués. Ce sont les seuls caractères autorisée en Ada 83.

Ecrire un programme qui évalue l'intégrité de données sur chaque ligne sur la base de la parité et affiche le résultat.

Travail demandé

    1. Compléter la spécification du problème
    2. Construire l'algorithme par raffinements successifs
    3. Coder l'algorithme en Ada. Chaque niveau de raffinement est codé par une fonction.
 

Solution

On construit la solution par raffinements successifs :

raffinement niveau 1 : Calcul et affichage de la parité d'une d'une séquence de 8 caractères ASCII 7 bits
 début
  Initialisation de la matrice représentant la séquence des 8 caractères ASCII;
  Calcul de la parité des lignes;
  Affichage de la parité des lignes;
 fin

raffinement niveau 2.1: Calcul de la parité des lignes
 début
   faire 8 fois
     Calculer la parité d'une ligne;
   fin faire
 fin

raffinement niveau 3.2.1: Calcul de la parité d'une ligne
 début
   Compter le nombre de 1 dans la ligne (les 7 bits significatifs);
   si le nombre de 1 est pair
   alors
      si  le bit de parité vaut 1
      alors les données sont intègres
      sinon erreur
      fsi;
   sinon
      si  le bit de parité vaut 0
      alors les données sont intègres
      sinon erreur
      fsi;
  fsi
 fin

raffinement niveau 2.2 : Affichage de la parité des lignes
 debut
   faire 8 fois
     Afficher la parité d'une ligne;
   fin faire
 fin

raffinement niveau 4.3.2.1 : Compter le nombre de 1 dans la ligne (les 7 bits significatifs)
 debut
   faire 7 fois
      cumuler l'élément courant;
   fin faire
 fin
 

Coder cet algorithme en Ada

with Ada.Text_io;use Ada.Text_io;
with Ada.Integer_Text_io;use Ada.Integer_Text_io;

procedure parite is

     subtype Bit is Integer range 0..1;
    subtype Indice is Integer range 1..8;
     type Ligne is array (Indice) of Bit;
     type Matrice8x8 is array(Indice) of Ligne;
     type TableauParites is array(Indice) of Boolean;
     type Uns is range 0..7;
     subtype Intervalle is Integer range 2..8;

    -- raffinement niveau 2.1: Calcul de la parité des lignes
     function paritesDesLignes(m:Matrice8x8) return  TableauParites is
        -- raffinement niveau 3.2.1: Calcul de la parité d'une ligne
        function pariteUneLigne(l:Ligne) return Boolean is
                -- raffinement niveau 4.3.2.1 : Compter le nombre de 1 dans la ligne (les 7 bits significatifs)
            function nbDe1(l:Ligne) return Uns is
                       nb:Uns:=0;
            begin
                 for i in Intervalle loop
                            nb:=nb+Uns(l(i));
                 end loop;
                 return nb;
            end nbDe1;

        begin
        if nbDe1(l) mod 2=1
        then
              if l(1)=0
              then return true;
              else return false;
              end if;
        elsif l(1)=0
             then return false;
             else return true;
             end if;
      end pariteUneLigne;

      t:TableauParites;
   begin
       for i in Indice loop
          t(i):=pariteUneLigne(m(i));
       end loop;
       return t;
 end paritesDesLignes;

-- Initialisation de la matrice représentant la séquence des 8 caractères ASCII
     uneMatrice:Matrice8x8:=((0,1,1,0,1,1,0,1),
                                                  (0,1,1,0,1,1,0,1),
                                                  (1,1,0,0,1,1,1,1),
                                                  (0,0,1,0,0,1,0,1),
                                                  (1,1,0,0,1,1,0,1),
                                                  (1,1,1,0,1,1,1,1),
                                                  (0,1,0,0,0,1,0,1),
                                                 (0,0,1,0,1,1,0,1));
     laParite:TableauParites;
begin
    -- raffinement niveau 2.1: Calcul de la parité des lignes
     laParite:=paritesDesLignes(uneMatrice);
    -- raffinement niveau 2.2 : Affichage de la parité des lignes
     put_line("Affichage de la parite des lignes");
     new_line;
     for i in Indice loop
        put("Intégrité de la ligne ");put(i,width=>1);put(" = ");
        put(Boolean'image(laParite(i)));
        new_line;
     end loop;
     new_line;
end parite;