TP1 : code de Golay

info-602 : mathématiques pour l'informatique

Hivers 2022

• Consignes

• Liens utiles

• 1. Préliminaires

  • Utilisation du code

  • 1.1. Opérations bit à bit

  • 1.2. Poids d'un mot

• 2. Le code de Golay

  • 2.1. Codage

  • 2.2. Vérification

  • 2.3. Correction des erreur -- 1

  • 2.4. Correction des erreur -- 2

  • 2.5. Correction d'erreurs : recherche exhaustive

  • 2.6. Statistiques sur la correction

Consignes

Le rendu de TP se fera uniquement à travers l'interface web TPLab. Vous devrez fournir un fichier .c contenant le code des fonctions demandées et éventuellement des fichiers annexes pour la question 12.

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

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 qui sont définies dans le fichier Makefile. (Vous pouvez également ajouter les options -Wno-unused-parameter -Wno-unused-function.)

Liens utiles

• le code de Golay sur wikipedia

• l'article original de Marcel Golay

• l'archive du TP.

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.

Utilisation du code

1. Le code fourni contient une fonction main dans un fichier main.c que vous ne devez pas modifier. Cette fonction permet de lancer le programme compilé depuis la ligne de commande.

2. Votre code devra être écrit dans le fichier harry-potter.c. (Sauf les tests, qui seront dans tests-harry-potter.c.)

3. Une des options disponibles est -T qui permet d'exécuter la fonction perform_tests du fichier test-harry-potter.c. La fonction fournie gère un ou deux tests. À vous de l'étendre de manière pertinente.

4. Le code définit une fonction DEBUG qui s'utilise comme la fonction printf. Elle a simplement un premier argument supplémentaire qui permet de contrôler l'affichage :

   • si cet argument est à 0, le message est toujours affiché,

   • si cet argument est à 1, le message est seulement affiché si le programme est lancé avec l'option -v,

   • si cet argument est à 2, le message est seulement affiché si le programme est lancé avec l'option -vv,

   • etc.

5. L'exécutable propose d'autres options qui permettent de tester directement certaines fonctions (code_golay, code_golay_etendu, correction_golay+decode_golay).

Voila un exemple d'exécution :

$ make clean
rm -f *.o a.out
$ make
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function -c -o main.o main.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function -c -o correction.o correction.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function -c -o tests-correction.o tests-correction.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function main.o correction.o tests-correction.o -o golay
$ 
$ ./golay -h
Utilisation :
  ./golay options
actions sur un mot :
    -c MOT  code le mot de 12 bits sur 23 bits
    -C MOT  code le mot de 12 bits sur 24 bits
    -s MOT  calcule le syndrome du mot 23 bits
    -d MOT  décode (avec correction d'erreurs) le mot de 23 bits sur 12 bits
    -D MOT  décode (avec correction d'erreurs) le mot de 24 bits sur 12 bits
    -e MOT  décode (avec correction d'erreurs exhaustive) le mot de 23 bits sur 12 bits
    -E MOT  décode (avec correction d'erreurs exhaustive) le mot de 24 bits sur 12 bits

tests aléatoires :
    -n NB   nombre de mots à tester
    -p X    probabilité d'erreur sur chaque bit

divers :
    -x      utilise la base hexadécimal plutôt que la base 2
    -v      augmente le niveau des affichages de débogage
    -T ARG  lance la fonction de test
    -h      ce message
$ 
$ ./golay -T binaire 12648430
en binaire, le mot 0x00c0ffee s'écrit 0b00000000110000001111111111101110
$ 

1.1. Opérations bit à bit

Nous utiliserons le type uint32_t (entiers 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 (ou 3339 en décimal).

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

Les opérations sont le « et », le « ou» et le « ou-exclusif » :

• le « et », donné par l'opérateur binaire & :

  &	0	1
  0	0	0
  1	0	1

• le « ou », donné par l'opérateur binaire | :

  |	-1	1
  0	0	1
  1	1	1

• le « ou exclusif » (aussi appelé XOR), donné par l'opérateur binaire ^ :

  ^	0	1
  0	0	1
  1	1	0

• la négation est donnée par l'opérateur unaire ~ :

  ~	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.

int bit(int i, mot m);

void print_bin(mot u, int n) ;

$ ./golay -T binaire 12648430
en binaire, le mot 0x00c0ffee s'écrit 0b00000000110000001111111111101110

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 (12+11) bits. Comme la partie gauche de la matrice est la matrice identité, cela signifie que le codage de w commence par w lui même et est suivi de 11 bits de redondance. Le décodage est 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, les bits de redondance de 011000000000 sont obtenus avec le XOR de la troisième et deuxième lignes de la matrice A.

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

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

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

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

$ ./golay -C 110100110
code_golay_etendu: 000110100110  =>  000110100110101011001011

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 utilisé 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 initial est correct. Si le syndrome est différent de 000000000, alors le mot initial 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) ;

$ ./golay -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) et permet donc de corriger 3 erreurs parmi les 23 bits reçus.

Nous allons implémenter une méthode de correction basée sur les propriétés suivantes du code.

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

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

$ ./golay -d 01110110101110100000010
correction_golay: 01110110101110100000010  =>  111101101011

2.4. Correction des erreur -- 2

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. Correction d'erreurs : recherche exhaustive

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

2.6. Statistiques sur la correction

Le code de Golay a une capacité de 12/23 ≈ 0.522 : il envoie en moyenne 52.2% d'information et 47.8% de redondance.

On peut démontrer qu'avec une telle capacité, le meilleur taux d'erreur possible en sortie (en fonction du taux d'erreur en entrée) suit la courbe suivante :

données	données
(fichier gnuplot)

$ ./golay -n 10000 -p 3
Tests sur un canal symétrique binaire avec taux d'erreur de 3.00%.
10000 mots ont été codés et envoyés
5202 mots ont étés modifiés (52.0200%)
7216 bits ont étés modifiés (3.1374%)
39 mots n'ont pas étés corrigés correctement (0.3900%)
132 bits n'ont pas étés corrigés correctement (0.1100%)

Remarques sur la page (ou le sujet) : contact.
mentions légales

,

Dernière révision: le 09-02-2022 à 08:51.