TD 7, Codes concaténés

1  Introduction : simuler un schéma de codage linéaire

Lorsque l’on veut mesurer les performances d’un schéma de codage et que le code est linéaire, il n’est pas nécessaire de coder et de décoder de vraies données. En pratique on supposera que le mot tout à zéro est émis, puis pour chaque bloc

• on génére un motif d’erreurs aléatoire correspondant au canal de communication
• on examine ce motif pour déterminer s’il peut être corrigé. Il y a trois possibilités: soit l’algorithme donne le mot zéro (décodage juste), soit l’algorithme de décodage donne un autre mot (décodage faux), soit il décide qu’il ne sait pas décoder.

Ce procédé possède de nombreux avantages :

• on peut mesurer les performances à grande échelle sans avoir à gérer les entrées/sorties
• il est inutile de programmer le codeur,
• tester si un motif d’erreurs est corrigible ne nécessite pas la programmation de la totalité du décodeur, par exemple dans le cas des codes concaténés.

2  Décodage du code de Golay par tableau standard

La méthode du décodage par tableau standard est d’associer à tout syndrome possible son coset leader (ou chef de file). Vous implanterez le décodage par tableau standard pour le code de Golay G₂₄ [24,12,8], dont la matrice génératrice est

    static int [] G = {
        0xa3b001, 0xc76002, 0x8ed004, 0x9da008, 0xbb4010, 0xf68020,
        0xed1040, 0xda3080, 0xb47100, 0xe8e200, 0xd1d400, 0x7ff800
    };

Noter que cette matrice génératrice est aussi une matrice de parité. En effet chaque ligne de G est aussi dans le noyau de G. Les étapes à programmer sont

• INIT: construction du tableau: pour chaque syndrome s mettre en table le mot e_s de poids de Hamming minimal qui a ce syndrome ;
• pour chaque erreur simulée e, déterminer son syndrome s ;
• retourner e−e_s.

Notez bien qu’on travaille tout le temps dans l’espace du code F₂²⁴ (trois octets, on prendra un int), et jamais dans l’espace des messages F₂¹². Vous pouvez utiliser la classe java suivante Golay.java

3  Les codes concaténés

Nous allons considérer des codes concaténés en blocs

• Code interne : le code de Golay, dont les mots tiennent sur trois octets soit un int.
• Code externe de Reed-Solomon, q-aire, avec q=2¹², de longueur n<q, de distance minimale d<n (dimension k=n−d+1). On prendra n=255, d=33 (donc 16 correcteur).

Pour le code interne (le Golay), l’appel Golay.decoder(y) retournera

• (true, w) si y se décode en 0 et est à distance w du code,
• (false, w) si y se décode en x != 0 et est à distance w du code,

Dans le cas d’un code concaténé, on peut préférer déclarer, au niveau du code interne un effacement, qui sera décodé par le code externe, plutôt que de produire une erreur qui est plus difficile à décoder.

On définit un seuil e: s’il y a plus d’erreur que e, on décide qu’il y a un effacement.

Un code de Reed-Solomon peut corriger un motif composé de t erreurs et s effacements si et seulement si 2t+s<d. Ceci doit suffire pour effectuer la simulation.

4  Le programme

Il prendra en arguments

• probabilité d’erreur binaire
• seuil d’effacement d’un symbole
• nombre de blocs (concaténés) à générer

Le code externe sera un Reed-Solomon (255,223,33). Vous utiliserez le programme pour répondre aux questions suivantes :

• Quel taux d’erreur binaire peut-on corriger ?
• Quel est le meilleur seuil d’effacement pour chacun des codes internes ?

This document was translated from L^AT_EX by H^EV^EA.