Téléchargez l'archive contenant les fichiers du TP. Vous ne devrez modifier que le fichier harry-potter.c.

Définissez la fonction

int bit(int i, mot m);

qui donne le bit (0 ou 1) numéro i du mot m. Le bit de poids faible aura le numéro 0 et le bit de poids fort aura le numéro 31. Par exemple :

    // test pour la question 1
    mot m = 0x555;  /* càd 00...000010101010101 en binaire */
    int n = 3;
    printf("Le bit numéro %d de %x est %u et le bit %d est %u.\n", n, m, bit(n,m), n+3, bit(n+3,m));

devra afficher

$ ./harry-potter -T 1
Le bit numéro 3 de 555 est 0 et le bit 6 est 1

Servez-vous de cette fonction pour écrire une fonction

void print_bin(mot u, int n) ;

qui affichera les n bit de poids faible d'un mot sans ajouter de saut de ligne en fin d'affichage. Par exemple:

    m = 0xace;
    printf("le mot '%x' est en fait ",m); print_bin(m,12); printf(".\n");

devra afficher

le mot 'ace' est en fait 101011001110.

Écrivez la fonction

int poids(mot m);

qui renvoie le nombre de 1 dans un mots.

N'oubliez pas de tester votre fonction !

Comme les mots de bits sont représentée par des éléments du type mot (synonyme du type uint32_t) la matrice A doit être représentée par un tableau d'éléments du type mot:

mot golay_A[12] = { 0x571, ... };

1. Complétez la définition des dernières lignes de cette matrice (variable globale) par les constantes appropriées.

2. Vous pouvez maintenant écrire la fonction de codage, qui multiplie un mot par la matrice définie précédemment:

   /*
    * code une suite de 12 bits (bits de poids faible d'un mot) en ajoutant
    * la redondance donnée par la matrice A
    * Le résultat (23 bits) est stocké dans les 23 bits de poids faible du
    * mot renvoyé.
    */
   mot code_golay(mot entree) ;
   

Attention : c'est le bit de poids fort qui correspond à la ligne 0 de la matrice, et le bit de poids faible qui correspond à la ligne 11 de la matrice...

Note: par rapport à ce qui a été vu en cours, seuls les bits de redondance sont obtenus par multiplication de matrice. Le mot initial reste inchangé...

Privilégiez les opérations bit à bit dans votre fonction...

Vous pouvez tester la fonction code_golay depuis la ligne de commande :

$ ./harry-potter -c 110100111
code_golay: 000110100111  =>  00011010011111110000110

Écrivez la fonction

/*
 * décode un mot du code de golay un supprimant les bits de redondance
 */
mot decode_golay(mot m) ;

Le code de Golay étendu code une suite de 12 bits en une suite de 24 bits : il s'agit du code de Golay avec un bit de parité supplémentaire ajouté à droite.

Écrivez la fonction correspondante :

/*
 * code de Golay étendu: 23 bit du code de Golay, avec un bit de parité
 */
mot code_golay_etendu(mot entree) ;

Vous pouvez tester la fonction code_golay depuis la ligne de commande :

$ ./harry-potter -C 110100111
code_golay_etendu: 000110100111  =>  000110100111111100001100

Définissez la matrice de parité

/*
 * matrice de parité pour le code de Golay
 */
unsigned golay_H[23] = {
    ...,
    ...,
};

puis écrivez la fonction qui calcule le syndrome (11 bits) d'un mot

/*
 * syndrome d'un mot du code de Golay (sans bit de parité)
 */
mot syndrome_golay(mot m) ;

Par exemple :

$ ./harry-potter -s 11010111010101111000110
syndrome_golay: 11010111010101111000110  =>  01111011000

Écrivez la fonction qui prend un mot m de n bits en argument et fait le décalage de p bits vers la droite, en remettant les p bits de poids faible à gauche.

/*
 * renvoie le décalage circulaire (à droite) de p bits sur un mot m de n bits
 */
mot decalage_circulaire(mot m, int n, int p) ;

Pour notre application, la valeur de n sera toujours 23.

Privilégiez les opérations bit à bit pour cette fonction.

Par exemple, sur le mot m = 11010101110 avec n=11 bits, le décalage vers la droite de 3 bits donne 11011010101.

Programmez la fonction

/*
 * correction d'erreur pour le code de Golay en utilisant la méthode "error
 * trapping" + cyclicité
 */
mot correction_golay(mot m) ;

Testez votre fonction sur des exemples:

1. choisissez un mot sur 12 bits,

2. codez le avec la fonction code_golay,

3. ajoutez (avec un XOR) une erreur choisie, comme par exemple 00000000000001100001000,

4. essayez de la corriger avec la fonction correction_golay,

5. comparer avec le mot du code sans erreur.

Par exemple :

$ ./harry-potter -d 01110110101110100000010
correction_golay: 01110110101110100000010  =>  111101101011

Note : la fonction appelée grace à l'option -d fait la correction d'erreur puis un décalage afin de ne donner que les bits de données corrigés.

• Donnez un exemple d'erreur de 3 bits que la fonction précédente ne peut pas corriger,

• donnez un exemple d'erreur de 2 bits que la fonction précédente ne peut pas corriger.

Modifiez votre fonction correction_golay pour pouvoir corriger toutes les erreurs de 2 ou 3 bits.

./correction -d 01110110101110100010010
correction_golay: 01110110101110100010010  =>  010100101011

Une autre méthode de correction d'erreurs est la recherche exhaustive : on parcourt tous les mots corrects en les comparant au mot à corriger. Le résultat est le mot correct le plus proche (au sens de la distance de Hamming) du mot à corriger.

1. Programmez la fonction correction_exhaustive_golay,

2. et comparez les temps d'exécution de correction_exhaustive_golay et correction_golay en détaillant votre méthodologie.

Vous pouvez tester cette fonction avec l'option `-e` :

./correction -e 01110110101110100010010
correction_golay_exhaustive: 01110110101110100010010  =>  010100101011

Écrivez une fonction qui lit des octets dans un fichier (fonction fread), les code avec le code Golay étendu, et écrit le résultat dans un autre fichier (fwrite).

Écrivez la fonction réciproque qui lit un fichier et corrige les erreurs avant d'écrire un fichier contenant le décodage correspondant.

Attention: un octet ne contient pas assez de bits pour être codé avec le code de Golay, mais deux octets contiennent trop de bits. Il faudra donc lire trois octets à la suite (24 bits) et les coder sur six octets (48 bits). (Et vice versa pour la fonction réciproque.)

Si le fichier en entrée ne contient pas assez d'octets, il faudra ajouter un "padding", qu'il ne faudra pas oublier d'enlever dans la fonction qui décode...

Lorsqu'un octet d'un fichier codé est modifié, il y a potentiellement 8 bits qui peuvent changer. Le code de Golay ne parviendra donc pas toujours à corriger un octet erroné.

Proposez une méthode qui permet de corriger plus facilement ce types d'erreurs (sur un octet entier), sans ajouter de bits de redondances supplémentaires.

Implémentez ce protocole dans vos fonctions de la question précédente.