Travaux pratiques
Enfin, écrire une procédure Encode:=proc(M,n,g) renvoyant le message codé
m (x) = g(x)M (x). Tester avec un M généré aléatoirement comme suit :
>RandMot:=proc(k) local mot,i;
mot:=rand(0..1);
return([seq(mot(),i=1..k)]);
end:
Nous allons maintenant expliquer comment décoder. On suppose que
m = c ∈ C est transmis et que m est reçu. Le polynôme d’erreur est
e(x) =
n
i=1 e i x i−1 , correspondant au vecteur d’erreur e = m − c. On suppose
qu’au plus t = E((δ − 1)/2) erreurs se sont produites, i.e. w(e) t et l’on définit :
– l’ensemble I = {i, e i = 0} des positions des erreurs ;
– le polynôme u(x) =
i∈I (1 − β i x) ∈ F g (β)[x] appelé localisateur d’erreur ;
– le polynôme v =
i∈I e i β i x
j∈I\{i} (1 − β j x) évaluateur d’erreur.
Les polynômes u et v vérifient deg u t et deg v < t. Ils déterminent à eux
deux l’emplacement et la valeur des erreurs : il suffit d’évaluer en β −i pour obtenir
I ; on calcule e i à l’aide de u =
i∈I −β i
j∈I\{i} (1 − β j x), d’où
v(β
−i ) = e i
j∈I\{i}
(1 − β
j−i ) = −e i β
−i u
(β
−i )
puis e i = −v(β −i )β i /u (β −i ).
Il existe différentes façons de calculer u et v. On peut, par exemple, formuler
le problème en termes d’équations linéaires à résoudre. On va donner une autre
méthode, plus performante en pratique.
On définit
w =
v
u
=
i∈I
e i β i x
1 − β i x
=
i∈I
j1
e i (β
i x)
j =
j1
x
k
i∈I
e i β
ji =
j1
e(β
j )x
j .
Comme c(β j ) = 0 pour 1 j δ − 1, on a e(β j ) = m (β j ) pour 1 j δ − 1.
On connaît donc w modulo x δ−1 : c’est S(x) =
δ−1
j=1 = m (β j )x j , appelé parfois
polynôme syndrôme.
La congruence
v(x) ≡ u(x)S(x) mod x
2t
(XV.2)
(noter que 2t δ − 1) peut se résoudre en utilisant une variante de l’algorithme d’Euclide étendu, appelé algorithme de Berlekamp-Massey : on calcule
395