Travaux Pratiques
du cours de Théorie de l'Information

ALGORITHMES ENUMERATEURS DE POIDS
  1. Poids d'un vecteur binaire. 
    Nous considérerons des espaces de Hamming binaires de dimension <=64, ainsi nous utiliserons la définition typedef  unsigned long long mot; pour représenter les mots de l'espace de Hamming . Ecrire une fonction uint poids( mot  x ) qui retourne le poids binaire du mot  x. 
  2. Construction de codes.
    Un code est complétement défini par une matrice génératrice, nous utiliserons le type :

    typedef struct c {
            uint dim;
            uint nbc;
            mot * code;
    } code;
    1. Ecrire une fonction void printcode( code c) qui imprime la matrice génératrice du code c.
    2. Ecrire  une fonction code parite( uint n ) qui  construit la  matrice génératrice du code des mots de poids pairs en longeur n. Remarque c'est un code de dimension n-1 engendré par les mots x poids 2 satisfaisant à l'équation x1 = 1.
    3. Ecrire une fonction code randcode( uint k, uint n) qui construit un [n,k]-code aléatoire.
  3. Enumeration naive.
    On rappelle que si G désigne une matrice kxn d'un [n,k]-code C alors les mots de C sont obtenus par les produits matriciels  m.G en faisant varier m dans l'espace binaire de Hamming de dimension k. 
    1. Ecrire une fonction mot encode(mot m, code G) pour calculer m.G
    2. L'énumérateur de poids d'un [n,k]-code C est un tableau A de dimension n+1 tel que A[i] soit égal au nombre de mots de poids i dans le code C. Ecrire une fonction uint *  enum( code c ) qui calcule l'énumérateur de poids du code c. Le coeur de cette fonction sera composé de la boucle : for( m = 0; m < (1 << c.dim) - 1; m++ ) A[ poids( encode(m, c) ) ]++;
    3. Ecrire une fonction void printp( uint *A) pour imprimer le polyôme énumérateur des poids A.
    4. Vérifier le bon fonctionnement de votre code en calculant l'énumérateur des poids des codes de parité.
  4. Enumeration récursive.
    Il s'agit de compléter d'écrire une fonction recursion(mot x, code c, uint nl, uint* a) compatible avec la fonction ci-dessous. Si nl == c.dim alors met à jour a[ poids(x) ] sinon on énumère les combinaisons sans la ligne nl  par par recursion(x, code c, nl + 1, a) puis on énumère avec les autres avec  recursion(x + c.code[nl],  c, nl + 1, * a)
    uint* enumrec( code c )
    {
    uint * a;
    a = (uint*) calloc( c.nbc, sizeof(uint) );
    recursion(0,  code c,  0,  a );
    return a;
    }
  5. Code de Gray.
    Un code Gray pour l'espace de Hamming de dimension k est une énumération des 2^k vecteurs v1, v2, etc... telle que la distance de Hamming entre deux vecteurs consécutifs soit égale à 1. Si on note numj le numéro de la composante à changer pour passer de vj à vj+1, on dispose d'un algorithme efficace pour énumérer un [n,k]-code :
    x = 0;  j = 1;
    tant que ( j < 2^k )
          traitement( x );
          x = x + code[ numj ];
    ftq
    1. Vous trouverez bien quelque part sur le web une preuve du fait que si numj = le plus petit entier r tel que 0 = j0= j1= ... = jr-1 < jr= 1, où j = ( ...  jr jr-1 ... j1j0) désigne la décompostion de j en base 2 alors le  numj  correspond bien à un code de Gray.
    2. Ecrire une fonction uint* enumGray( code c )
    3. comparez les performances des trois méthodes d'énumérations.
Philippe Langevin,
janvier 2006.