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

Introduction à la théorie de l'information

10 février 2023

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⁻² et 10⁻⁴.
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

Addition bit-à-bit modulo 2 (ou exclusif) : x ^ y
Multiplication bit-à-bit modulo 2 (et) : x & y
Par exemple (x & 0xFF) met à 0 tous les bits de x sauf les 8 les moins significatifs (équivalent à (x % 256)).
Multiplication par une puissance de 2 (décalage à gauche de l'écriture en base 2) : (x << i)
Division par une puissance de 2 (décalage à droite de l'écriture en base 2) : (x >> i)
Constantes Java en hexadécimal : elles sont précédées de 0x les lettres de A à F valent de 10 à 15. Par 0x0137 vaut 311 (1 0011 0111 en base 2) ou 0x02E6 vaut 742 (10 1110 0110 en base 2).
On peut accélérer le calcul du poids de Hamming. Quel est l'effet sur x de l'instruction x &= (x - 1) ? Au bout de combien d'itérations x<=0 ? Vous pouvez aussi utiliser la méthode Java Integer.bitCount(int) .