Consignes

Le rendu de TP se fera uniquement à travers l'interface web TPLab. Vous devrez fournir un unique fichier .c contenant le code des fonctions demandées.

Vous pouvez utiliser le fichier Makefile fournit pour faciliter la compilation.

Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans votre fichier principal.

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

• votre fichier devra s'appeler "nom.c",
• chaque fichier devra comporter un commentaire au début avec vos nom, prénom, filière et numéro du TP,
• votre code doit compiler avec les options -Wall -Werror -Wextra -pedantic -std=c99,

Liens utiles

• le code de Golay sur wikipedia
• l'article original de Marcel Golay
• l'archive du TP.

Estimation du temps

• question 1 : 15 minutes (en comptant la mise en route)
• question 2 : 10 minutes
• question 3 : 10 minutes
• question 4 : 20 minutes
• question 5 : 5 minutes
• question 6 : 20 minutes
• question 7 : 5 minutes
• question 8 : 35 minutes
• question 9 : 5 minutes
• question 10 : 5 minutes
• question 11 : 35 minutes
• question 12 : 5 minutes

1. Préliminaires

Le but de ce TP est de comprendre le fonctionnement du code de Golay et d'en implémenter une version en C...

Nous utiliserons le type uint32_t (mots non signés, sur 4 octets, défini dans stdint.h) pour représenter en interne les suites de 12 bits et 24 bits :

typedef uint32_t mot ;

(Cette définition se trouve déjà dans le fichier tp1.h.)

Par exemple, la suite de 12 bits 110100001011 sera en fait représentée par 00000000000000000000110100001011, c'est à dire 0xd0b.

1.1. Opérations bit à bit

Il est possible de manipuler directement les bits des types du langage C grâce aux opérations bit-à-bit.

Les opérations sont :

• le « et » :
  • 0 & 0 = 0
  • 0 & 1 = 1 & 0 = 0
  • 1 & 1 = 1
• le « ou » :
  • 0 | 0 = 0
  • 0 | 1 = 1 | 0 = 1
  • 1 | 1 = 1
• le « ou exclusif » (XOR) :
  • 0 ^ 0 = 0
  • 0 ^ 1 = 1 ^ 0 = 1
  • 1 ^ 1 = 0
• la négation :
  • ~0 = 1
  • ~1 = 0

Appliqués à des entiers (ou des char), les opérateurs &, |, ^ et ~ agissent sur chaque bit indépendamment.

Deux autres opérations sont disponibles :

• le décalage à droite, qui supprime des bits de poids faible et mets des 0 dans les bits de poids forts. Sur des entiers non signés, ça correspond à une division entière par une puissance de 2 :
  • en binaire : 00010000 >> 2 = 00000100, c'est à dire 16>>2 = 4 en décimal, ou 0x10>>2 = 0x04 en hexadécimal,
  • en binaire : 01101100 >> 3 = 00001101, c'est à dire 0x6a>>3 = 0x0d en hexadécimal,
• le décalage à gauche, qui ... décale vers la gauche. Sur des entiers non signés, ça correspond à une multiplication par une puissance de 2, en tronquant le résultat s'il y a dépassement de capacité :
  • en binaire : 00010000 << 2 = 01000000, c'est à dire 16<<2 = 64 en décimal, ou 0x10<<2 = 0x40 en hexadécimal,
  • en binaire (sur des char) : 01101100 << 3 = 01100000, c'est à dire 0x6a<<3 = 0x60 en hexadécimal.

#define BIT(i,m) ((m) & 1)

    // 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));

Le bit numéro 3 de 555 est 0 et le bit 6 est 1

void print_bin(mot u, int n) ;

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

le mot 'ace' est en fait 101011001110

1.2. Poids d'un mot

int poids(mot m) ;

2. Le code de Golay

2.1. Codage

Une des matrices génératrices du code de Golay est [ I | A] où I est la matrice identité sur 12 lignes / 12 colonnes et A est la matrice sur 12 lignes / 11 colonnes suivante :

On code donc un mot de 12 bits en un mot de 23 bits. Comme la partie gauche de la matrice est la matrice identité, cela signifie que le codage de w est w.r où r contient les 11 bits de redondances ajoutés par le code. Le décodage est donc trivial: il s'agit d'un décalage à droite.

Cette matrice signifie que :

• les bits de redondance du mot 100000000000 sont 10101110001 (première ligne),
• les bits de redondance du mot 010000000000 sont 11111001001 (deuxième ligne),
• ...

Les bits de redondance des autres mots sont codés par linéarité. Par exemple, pour 011000000000 on fait le XOR de la troisième et deuxième lignes de la matrice A.

mot golay_A[12] = { 0x571, 0x7c9, 0x695, 0x63b, 0x66c, 0x336,
                    0,0,0,0,0,0};
};

/*
 * 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) ;

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

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

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

2.2. Vérification

Pour vérifier si un mot de 23 bits est correct, il faut multiplier ce mot par une matrice de parité. La matrice de parité correspondant à la matrice génératrice est obtenue en collant une matrice identité 11 lignes / 11 colonnes sous la matrice A précédente :

Le résultat de cette multiplication est appelé le syndrome d'un mot. Si le syndrome (sur 11 bits) est 00000000000, alors le mot est un mot correct. Si le syndrome est différent de 000000000, alors le mot n'est pas correct.

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

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

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

2.3. Correction des erreur -- 1

Le code de Golay permet de détecter 6 erreurs (7 pour la version étendue). Il permet donc de corriger 3 erreurs parmi les 23 bits reçus. La méthode de correction est basée sur les propriétés suivantes du code :

• la matrice génératrice est donnée sous forme standard (avec une matrice identité à gauche),
• la matrice génératrice donne un code cyclique : si w est un mot correct, alors toutes les permutations circulaires de w sont également correctes.

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

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

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

2.4. Correction des erreur -- 2

Lorsqu'il n'y a qu'un bit d'erreur, la méthode précédente fonctionne toujours !

Lorsque les bits d'erreurs sont trop éloignés, la méthode précédente ne fonctionne pas : aucun décalage circulaire n'amènera toutes les erreurs dans les 11 bits de poids faible du mot.

Parce que le code de Golay est parfait, cette méthode trouvera toujours une correction pour le mot.

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

2.5. Décodage

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

2.6. Pour aller plus loin