Ex-Code de Golay [PDF]

Zitiervorschau

Exercice On considère le code de Golay G12 ternaire (ie. sur V = z3 ) de distance 6 et de matrice génératrice G = [I6 ; A] avec 2 3 0 1 1 1 1 1 61 0 1 2 2 17 6 7 61 1 0 1 2 27 6 7 A=6 7 1 2 1 0 1 2 6 7 41 2 2 1 0 15 1 1 2 2 1 0 1. Donner les caractéristiques de ce code (longeur n, dimension k et jG12 j) et sa matrice de contrôle H: 2. Montrer que G12 n’est pas un code parfait. 3. Soit G11 le code obtenu à partir de G12 en supprimant sa dernière composante. Comment sera codé le mot m = 102102 par G11 ? 4. Expliciter la matrice de contrôle associée à G11 . Quelle est sa distance ? En déduire son taux de correction. 5. Calculer le cardinal du sous recouvrement de z3 formé par les boules de rayon 2 centrées sur les mots de G11 : 6. Calculer jc3 j : Que peut on conclure ?

1

Solution Exercice

1. 2 n = 12; 0 2 2 62 0 2 6 62 2 0 6 62 1 2 6 42 1 1 2 2 1

k 2 1 2 0 2 1

= 2 1 1 2 0 2

6;3 jG12 j = 36 et 2 27 7 17 7 17 7 25 0

H = [ At ; In k ] avec

At =

2. Le code G12 ne peut as être parfait car il est de distance pair (d = 6). En e¤et, soient x et y deux mots de code situés à distance 6, on peut 12

trouver facilement un mot de z 3 à distance 3 de x et de y, donc impossible de corriger de manière unique. Une autre méthode plus laborieuse, consiste à montrer que la borne de Haming n’est pas atteinte. Pour celà, il faut calculer la cardinalité du sous recouvrement induit par les boules après avoir déterminé le taux de correction du code et le comparer avec le cardinal de l’espace vectoriel. 3. Le code G11 a pour matrice génératrice 2 0 1 1 61 0 1 6 61 1 0 0 A =6 61 2 1 6 41 2 2 1 1 2

G0 = [I6 ; A0 ] avec 3 1 1 2 27 7 1 27 7 0 17 7 1 05 2 1

le mot m = 102102 sera codé m0 = (102102)t G0 2 0 62 6 4. Matrice de contrôle H associée à G11 : H = 6 62 42 2

2

= 102102 21012: 3 2 2 2 2 2 0 2 1 1 27 7 2 0 2 1 17 7 I5 : 1 2 0 2 15 1 1 2 0 2

Comme G12 est de distance 6, G11 est de distance au moins 5. La première ligne de la matrice est de poids 5, or toutes les lignes sont des éléments du code, on en déduit que le code possède un mot de poids 5. Donc il est de distance 5 et il est 5 2 1 = 2 correcteur. 5. Les boules de rayon 2 centrées sur les mots de G11 sont disjointes et 11

forment un sous recouvrement de z 3 de cardinal: 36 (1 + 2:

2 1 ) = 177147 + 22 11 11

11

Comme z 3 = 311 = 177147, le sous recouvrement est en fait un recouvrement et le code est donc parfait.

3