TP1

Dans ce TP nous allons, pas à pas, implémenter un code de Hamming afin de mieux en assimiler le fonctionnement.

Installation et prise en main

  1. Téléchargez et décompressez l'archive disponible sur Moodle.
  2. Exécutez le script afin d'installer la bonne version de Python, et les bibliothèques nécessaires au TP.
  3. Ouvrez le dossier du projet dans VSCode.

Les structures de données

💡 La Programmation Orientée Object étant encore une notion relativement récente pour vous, nous éviterons d'utiliser des classes dans le cadre de ce TP.
Les différents ECC seront implémentés dans le dossier . Dans le fichier , la fonction permettra de créer votre propre ECC à partir de :
Les fonctions d'encodages et de décodages prennent en paramètre et retournent un , qui est une séquence de bits (≈ une liste de 0 et de 1). Un exemple d'ECC ne faisant rien vous est donné dans le fichier .
  1. Créez une copie du fichier que vous nommerez .
  2. Dans ce fichier, remplacez toutes les occurrences de par ().

Les tests

Au fur et à mesure que vous implémenterez le code de Hamming, vous devrez écrire puis exécuter des tests afin de vérifier la validité de votre implémentation. Pour cela VSCode fournit une interface permettant d'exécuter l'ensemble des tests du projet, ainsi que d'en visualiser les résultats :
  1. Exécutez la première série de test pour , correspondant à un code correcteur ne faisant rien.
Pour écrire les tests, nous utiliserons la bibliothèque . Les tests seront enregistrés dans le dossier . En principe les tests prennent la forme suivante :
💡 permet d'exécuter plusieurs fois le même test avec des valeurs différentes :
⚠ VSCode supportant mal le fait d'avoir plusieurs milliers de tests, un h4ck est utilisé dans afin de fusionner certains tests. Il n'est cependant pas utile que vous vous appesantissiez dessus.
💡 Nous étudierons les tests plus en détail au semestre suivant dans le cours Automatisation et Tests en Programmation.
  1. Créez une copie du fichier que vous nommerez .
  2. Dans ce fichier, remplacez les occurrences de par ().
  3. Re-exécutez les tests.

Hamming (implémentation naïve)

Calculer la taille des mots d'informations et de code.

Nous allons faire en sorte que prenne en paramètre le nombre de bits de redondances (à l'exception du dernier) au lieu du nombre de bits du mot d'information/de code.
  1. Dans , remplacez par .
  2. Soit le nombre de bits de redondances (à l'exception du dernier), quelle est la taille :
    • du mode de code ?
    • du mode d'information ?
  3. Modifiez de sorte à calculer les différentes tailles à partir de (passé en paramètre).
  4. Ajoutez le test suivant à
  5. Exécutez ce nouveau test.

Placer les bits de redondances

Comme nous n'avons pas modifié les fonctions d'encodage et de décodage, les mots d'informations et de codes retournés ont des tailles différentes de celles fournies à .
  1. Utilisez afin d'ajouter les bits de redondances lors de l'encodage (sans les caculer).
  2. Utilisez afin de retirer les bits de redondances lors du décodage.
  3. Exécutez à nouveau les tests.

Calculer les bits de redondances

Nous allons maintenant calculer les bits de redondances. Pour cela nous allons créer une fonction prenant en paramètre le mot de code, et calculant son bit de parité .
  1. Créez calculant la parité des bits 2i (indice : ).
  2. Ajoutez le test suivant à , puis exécutez-le :
  3. N'hésitez pas à rajouter vos propres valeurs à la suite de tests.
  4. Modifiez la fonction , de sorte à ce que corresponde au bit de parité global.
  5. Re-exécutez les tests.

Placer et vérifier les bits de redondances

Maintenant que nous pouvons calculer les parités, nous pouvons placer les bits de redondances lors de l'encodage, et les vérifier lors du décodage.
  1. Modifiez la fonction d'encodage afin de mettre à jour les bits de redondance après qu'ils aient tous été insérés.
  2. Lancez à nouveau les tests.
  3. Modifiez la fonction de décodage afin de calculer le syndrome (un nombre), et d'inverser le bit correspondant.
  4. Exécutez les fonctions de tests.
Vous devriez désormais constater que votre code correcteur est désormais capable de passer le test correspondant à l'injection d'une erreur lors de la transmission d'un mot de code.

Hamming (avec des matrices)

La méthode que nous venons d'implémenter correspond à ce qu'un humain ferait s'il devait effectuer les encodage/décodage à la main. Ces opérations sont en réalité équivalentes à des produits matriciels que les ordinateurs sont capables de faire très rapidement grâce à des instructions spéciales. Par exemple il est possible de traiter 256 à 512 bits en ~1 cycle CPU. En comparaison, les conditions/boucles sont beaucoup plus coûteuses pour un ordinateur (~10-20 cycles CPU).
Nous allons donc créer un version plus rapide de Hamming grâce à des produits matriciels avec la bibliothèque numpy.
⚠ Toutes les matrices/vecteurs devront avoir un .

Création de l'ECC

  1. En copiant les fichiers de , créez un nouvel ECC nommé , ainsi que ses tests.
  2. Réécrivez l'encodage et le décodage de sorte à ce que les bits de redondance soient à la fin (sans les calculer).
  3. Exécutez les tests.

Pre-calcul des matrices

Avant d'encoder et de décoder, nous allons pre-calculer différentes matrices, permettant de calculer :
  1. Créez une fonction créant la matrice C à partir du paramètre n :
    1. Générez une liste de nombre allant de 0 à 2n-1 inclus.
    2. Retirez 0 et toutes les puissances de 2 de cette liste.
    3. Chaque ligne de C sera l'encodage binaire de chaque élément de cette liste.
  2. Créez une fonction créant la matrice G à partir de C :
    1. Générez la colonne R correspondant au dernier bit de parité :
    2. G est alors la concaténation horizontale de R avec C.
  3. Créez une fonction créant la matrice G à partir de C :
    1. H est une concaténation verticale de C, d'une ligne de 0, et d'une matrice identité.
  4. Ajoutez la fonction suivante retournant un tableau convertissant le syndrôme en l'index du bit à modifier :
Donner les matrices plutôt ?

Encodage et décodage

Nous allons maintenant procéder à l'encodage et au décodage en utilisant les matrices calculées précédemment. Vous exécuterez les tests après chaque question.
  1. Dans la fonction d'encodage, rajoutez les bits de redondances (produit matriciel du mot d'information avec G, % 2).
  2. Dans la fonction de décodage, calculez le syndrome (produit matriciel du mot de code avec H, %2).
  3. Convertissez le syndrome en nombre, 0 indique une absence d'erreur.
  4. Convertissez ce nombre grâce au tableau de conversion, puis inversez le bit correspondant.
Vous devriez désormais passer les mêmes tests que votre première implémentation du code de Hamming.

Benchmarks

Afin de tester si la version avec produits matriciels est effectivement plus rapide que la version naïve, nous allons mesurer et comparer les performances de ces deux implémentations.
  1. Lancez le benchmark grâce à la commande .
💡 La première colonne correspond au paramètre . Les colonnes suivantes correspondent à un ECC, et sont découpées en 3 sous-colonnes :
  1. le taux de messages correctement décodé.
  2. la vitesse d'encodage.
  3. la vitesse de décodage.
💡 Vous remarquerez que l'ECC avec produits matriciels est plus lente pour des petits . Ceci s'explique par le fait que :

Pour aller plus loin...

Les vitesses d'encodage et de décodage du benchmark sont calculés en divisant le nombre de bits d'informations correctement transmis par la durée de l'encodage (ou du décodage).
  1. Dans le fichier , modifiez la probabilité d'erreur sur un bit () pour qu'elle vale 0.1.
  2. Que remarquez-vous alors ? Comment expliquez-vous cela ?

Multi-ECC

Plus un mot de code est long, plus la probabilité d'avoir au moins 2 erreurs est grande. Pour éviter cela, on peut découper le message à transmettre en plusieurs mots d'informations qui seront chacuns encodés par un ECC.
  1. Créez un nouvel ECC nommé .
  2. prend en paramètre un ECC, ainsi que la taille en bit d'un mot de code.
  3. Calculez le nombre de mot de code de nécessaires pour atteindre .
  4. L'encodage consistera alors en :
    1. séparation du mot d'information en parties égales
    2. de l'encodage des différentes parties via .
    3. de la concaténation des résultats.
  5. Implémentez cet ECC, puis lancez les tests.
  6. Ajoutez l'ECC au benchmark, puis exécutez-le.
  7. Que remarquez-vous alors ? Comment expliquez-vous cela ?
💡 Nous estimons ici que les erreurs surviennent de manières indépendantes, or ce n'est pas toujours le cas. Pour se prémunir des erreurs consécutives, on peut tout simplement répartir les bits consécutifs dans des mots différents.
Par exemple le bit ira dans le mot .