Consignes

Le TP est à rendre, par email, avant le dimanche 4 décembre à 23h59...

Pour ce TP comme pour les suivants, la pièce la plus importante sera une archive tp1-nom-prenom.tar contenant votre programme. J'insiste sur les points suivants :

  1. l'archive est au format tar (éventuellement au format tar.gz ou tar.bz2),
  2. l'archive contient un répertoire tp1-nom-prenom contenant votre code (elle ne crée rien d'autre dans le répertoire courant),
  3. l'archive ne contient pas de fichier binaire ou exécutable (seulement des fichiers sources),
  4. l'archive contient un fichier Makefile pour compiler votre programme, avec au minimum les cibles all et clean.

Le non-respect des ces consignes risque de me mettre de mauvaise humeur... (Remarque : un fichier Makefile basique est disponible ici.)

Attention, le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

  1. l'architecture de votre programme (code découpé en fonctions etc.),
  2. la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),
  3. la présence de commentaires aux endroits appropriés,
  4. la présence de documentation pour vos fonctions.

Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans votre fichier principal. Si vous le souhaitez vraiment, vous pouvez aussi m'envoyer un rapport de TP. Le format de ce rapport sera au choix, mais par ordre de préférence :

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

Liens utiles

1. Préliminaires

Le but de ce TP est de comprendre comment fonctionne le code de Hamming...

Nous utiliserons le type unsigned char (mots non signés, sur 8 bits) pour représenter des suites de huit bits (octets) : 

typedef unsigned char octet ;

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

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 :

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

Deux autres opérations sont disponibles :

Écrivez une macro 

#define BIT(u,i)  ...

qui permettra d'obtenir facilement un bit dans un octets. Par exemple : 

  octet o = 0x6b ;  /* càd 01101011 en binaire */
  printf("Le bit 0 est %u et le bit 2 est %u\n", BIT(o,0), BIT(o,2));

devra afficher 

      Le bit 0 est 0 et le bit 2 est 1.

Notez bien que le bit 0 est le bit de poids fort...

Servez-vous de cette macro pour écrire une fonction 

void print_octet(octet u) ;

qui affichera un octet en binaire.

1.2. Distance de Hamming

La distance de Hamming permet de mesurer les différences entre deux suites de bits.

Programmez les fonctions 

/*
 * Calcule le nombre de bits différents entre u et v
 */
int distance_hamming_octet (octet u, octet v) ;

/*
 * Calcule le nombre de bits différents entre u et v
 */
int distance_hamming (const octet *u, const octet *v, int taille) ;

Pour la fonction distance_hamming_octet(), essayez de minimiser le nombre d'instructions du code généré.

2. Le code de Hamming

2.1. Codage

Le code de Hamming étendu (avec bit de parité) permet de coder les mots de 4 bits avec des mots de 8 bits. Une de ses matrices génératrices est la suivante :

0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

Cela veut dire :

Les autres mots sont codés par linéarité. Par exemple, 0110 est codé par le XOR de la troisième et deuxième lignes...

Remarque : le code de Hamming étendu est obtenu de la manière suivante :

Le code de Hamming Ĥ(4) permet de coder 4 bit sur 8 bits. Plutôt que de gérer les demi octets, programmez une fonction pour coder un octet (2 fois 4 bits) sur 2 octets (2 fois 8 bits).

Par exemple, l'octet 00101000 sera codé par 01010101 00001111. 

void hamming_code_octet(octet u, octet v[2]) ;

Déduisez en une fonction pour coder un fichier entier : 

int hamming_code(FILE *in, FILE *out) ;
  1. La fonction hamming_code(...) est très simple : il s'agit uniquement d'une boucle qui utilise la fonction précédente en lisant et écrivant les octets appropriés dans in et out.

  2. Pour lire un octet dans un fichier, il faut utiliser fread(&o, 1, 1, in) et pour écrire 2 octets dans un fichier, il faut utiliser fwrite(&o, 1, 2, out). (Voir man fread pour plus de détails...)

  3. Pour vérifier que votre fonction code correctement, il faut :
    • créer un fichier à coder, par exemple un fichier texte qui contient une seule ligne "Coucou",
    • ouvrir, dans votre fonction main, le fichier créé précédemment (ouverture en lecture seulement, voir man fopen)
    • ouvrir, dans votre fonction main, un nouveau fichier pour enregistrer le code (ouverture en écriture, voir man fopen)
    • appeler la fonction hamming_code(...) sur ces deux fichiers
    • vérifier le contenu des fichiers avec la commande Unix "hexdump" qui afficher les octets (en hexadécimal) des fichiers.

2.2. Vérification

Pour coder un mot, il suffit de faire une multiplication par une matrice génératrice. Pour vérifier si un mot est correct, il faut également multiplier un mot par une matrice, appelée matrice de parité. Comme le code de Hamming étendu est autodual, la matrice de parité est simplement la transposé de la matrice génératrice :

0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

Le résultat de cette multiplication est appelé le syndrome d'un mot. Si le syndrome est 0000, alors le mot est un mot correct. Si le syndrome est différent de 0000, alors le mot n'est pas un mot correct.

Par exemple :

Écrivez la fonction qui calcule le syndrome d'un octet afin de pouvoir vérifier si cet octet est un mot de Hamming : 

octet hamming_syndrome(octet u) ;

N'oubliez pas de tester votre fonction...

2.3. Correction d'une erreur

Le calcul du syndrome est toujours assez simple et se fait avec une multiplication de matrice. Quand le syndrome est non nul, il y avait une erreur, et la correction des erreurs, bien que possible en théorie, n'est pas toujours facile en pratique.

Heureusement, grâce à sa construction, la correction d'une erreur pour le code de Hamming est relativement aisée :

Pour reprendre l'exemple précédent, le syndrome de 01000101 est 0111, et il suffit effectivement de modifier le bit 3 (11 en binaire) pour retomber sur en mot de Hamming.

Écrivez la fonction correspondante : elle prend en argument un syndrome et renvoie le masque de l'erreur si elle le trouve. (Dans le cas précédent, le masque est simplement 00010000. Quand on détecte deux erreurs, on renvoie 11111111 : 

octet hamming_erreur(octet s) ;

2.4. Décodage

Il ne reste plus qu'à décoder un mot de Hamming pour retrouver le mot original. Encore une fois, il suffit de faire une multiplication par une matrice appropriée.

Dans notre cas, les 4 bits de départ sont cachés dans les bits 0, 1, 2 et 4 du mots de Hamming. (Les bits 3, 5, 6 et 7 sont redondant et permettent de détecter / corriger des erreurs.)

La matrice de décodage est simplement :

1 1 1 1
0 0 1 0
0 1 0 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Comme précisé ci-dessus, seules les lignes 0, 1, 2 et 4 sont intéressantes.

Par exemple : le mot de Hamming 11111111 se décode bien en 0001 car le XOR de toutes les lignes de la matrice vaut 0001.

Remarque : en pratique, on choisit la matrice génératrice en forme standard. Dans ce cas, le décodage est trivial et il suffit simplement de tronquer le mot pour jeter les bits redondant et obtenir le mot original. C'est possible de faire ceci pour le code de Hamming, mais cela cache sa construction...

Heu... Programmez 

void hamming_decode_octet(const octet u[2], octet v[1]) ;

Comme pour le codage, on évite de gérer les demi octets en décodant deux mots de Hamming à la fois pour obtenir un octet entier.

N'oubliez pas de tester...

3. Tests

3.1. Introduire des erreurs dans un message

Pour introduire des erreurs aléatoires dans un message, écrivez la fonction suivante : 

/*
 * Introduit du bruit dans "avant" et met le résultat dans "apres" "p"
 * représente la probabilité qu'un bit soit modifié.
 * Attention, il faut que "apres" soit suffisamment grand pour recevoir le
 * résultat...
 */
int bruite (const octet *avant, octet *apres, int taille, float p) ;

Attention : chaque bit a la même probabilité d'être modifié. Ainsi, il se peut que 2 bits ou plus soient modifiés dans le même octet.

3.2. Tests

En utilisant la fonction précédente, écrivez une petite fonction principale pour générer des statistiques telles que

L'utilisation de getopt peut vous permettre de faire une fonction principale générique et de ne pas avoir besoin de recompiler à chaque fois...

Si vous souhaitez que le message transmis et décodé ait moins de 1% d'erreurs, quel proportion de bruit votre canal de transmission peut-il supporter ?

(Bonus)

Si vous avez le temps, implantez également le code « répétition d'un octet 2 ou 3 fois » pour voir si vous arrivez à améliorer les statistiques de la question précédente.