TD 6, Codes correcteur d'erreurs – Code de Nordstrom-Robinson

Introduction à la théorie de l'information

14 février 2020


Le code de Nordstrom-Robinson est un code en bloc (non linéaire) de longueur 16 contenant 256 mots. La liste des mots de code est donnée ici. On envoie 8 bits vers 16 bits, c'est un code de rendement 1/2.
Attention, à partir de maintenant, on travaille avec des "vrais bits", et non plus avec les caractères '0' et '1'. Voir les annexes plus bas pour les opérations bit-à-bit.

1  Distance minimale

La distance minimale de ce code est de 6 (c'est mieux que tout code linéaire de même paramètres).

Écrire un programme qui calcule l'énumérateur des distances du code, c'est-à-dire pour tout poids w entre 0 et 16, le nombre de paires de mots de codes à distance de Hamming w.

2  Décodage au maximum de vraisemblance

Écrire un codeur, un simulateur de canal binaire symétrique et un décodeur à maximum de vraisemblance. C'est l'algorithme qui retourne le mot de code le plus proche, non nécessairement unique. On testera avec le fichier hamlet.txt. Une exécution type ressemblera à
  java Coder hamlet.txt >hamlet.code
  java Canal hamlet.code 0.01 > hamlet.canal 
  java Decoder hamlet.canal > hamlet.decode
  java Distance hamlet.decode hamlet.txt
avec une probabilité d'erreur variant entre 10−2 et 10−4.
Il y a dans l'annexe B une astuce pour accélérer le calcul de la distance.

3  Décodage strictement borné

Le code a une distance minimale de 6, la meilleure borne pour un décodeur est 2. Modifier le décodeur pour qu'il corrige les erreurs binaires de poids de Hamming 1 ou 2 dans un bloc (de 16 bits), mais qui ne prend pas de décision au delà (on retournera '*' par exemple).

Faire des tests en imprimant le nombre d'erreurs résiduelles ainsi que le nombre de '*'.
On aura une syntaxe dy type
  seth $ java DecoderB hamlet.canal  hamlet.txt > hamlet.decodeB
  n_star= 88
  dist= 2
C'est à dire qu'on écrit les données auxiliaires sur la sortie d'erreur standard, et on utilise la sortie standard pour écrire le fichier décodé.

Annexe A: Sur la méthode read()

Rappelez vous que la méthode read() retourne un int, qui est en fait un octet compris entre 0 et 255, -1 pour la fin du fichier. Pour obtenir un mot de longueur 16, il faut deux lectures consécutives, et les concaténer dans un même mot.

Annexe B : opérations bit-à-bit sur les mots machine