210
6 Codes correcteurs
Dans quels corps, parmi R, F 2 , F 3 , ce syst` eme poss` ede-t-il une unique solution ?
(Les coefficients entiers du syst` eme sont compris modulo 2 ou 3 si la r´ esolution
est dans F 2 ou F 3 respectivement.)
e) R´ esoudre () dans F 3 .
23. Cet exercice a pour but d’encoder et de d´ ecoder un message ` a l’aide du code de
Reed–Solomon avec m = 3 et k = 3. On doit avoir construit le corps F 8 auparavant
(voir l’exercice 18 ci-dessus). Les calculs sont assez directs, mais ils sont nombreux :
travaillez en ´ equipe. (Tous les participants doivent choisir la mˆ eme racine primitive
α et avoir les mˆ emes tables de F 8 !)
a) Combien d’erreurs au maximum le code de Reed–Solomon C(7, 3) peut-il corriger ?
b) Quel est l’encodage du mot (0, 1, α) ∈ F
3
2 ?
c) L’´ equation (6.12) peut ˆ etre r´ e´ ecrite
p = Cu,
o` u p ∈ F
2
m −1
2 m
, u ∈ F
k
2 m et C ∈ F
(2
m −1)×k
2 m
. Obtenir la matrice C pour le code
C(7, 3).
d) Supposons que le message re¸ cu soit
w = (1, α
4 , α
2 , α
4 , α
2 , α
4 , α
2 ) ∈ F
2
m −1
2 m
.
Choisir les lignes 0, 1 et 4 du syst` eme (6.12) et r´ esoudre afin de trouver le vecteur
(u 0 , u 1 , u 2 ) ∈ F
3
8 .
e) Combien y a-t-il de choix possibles de trois ´ equations distinctes parmi celles
de (6.12) ? Combien faudra-t-il r´ esoudre de syst` emes comme celui de la question
pr´ ec´ edente pour ˆ etre sˆ ur que la r´ eponse pr´ ec´ edente est le message original ?
f) Est-ce que la solution de d) est le message original ?
24. Soit p un nombre premier. Cet exercice prouve que Z p est un corps. On dit que
a et b sont congrus modulo p si leur diff´ erence a − b est un multiple entier de p
(voir l’exemple 6.5).
a) Montrer que « ˆ etre congru » est une relation d’´ equivalence, appel´ ee congruence
modulo p.
b) On identifie Z p ` a l’ensemble des classes d’´ equivalence des entiers modulo p.
Soit ¯
a, ¯ b ∈ Z p . Soient i, j ∈ ¯
a et m, n ∈ ¯ b. Montrer que si i + m ∈ ¯
c et j + n ∈ ¯
d,
alors ¯
c = ¯
d. Mˆ eme question pour i × m et j × n. Cet exercice montre que les
d´ efinitions de + et de × donn´ ees ` a l’exemple 6.5 ne d´ ependent pas de l’´ el´ ement
des classes ¯
a et ¯ b choisi.
c) Montrer que la classe ¯ 0 est le neutre pour + et que ¯ 1 est le neutre pour ×.
d) Soit ¯
a ∈ Z p un ´ el´ ement diff´ erent de ¯ 0. Utiliser l’algorithme d’Euclide (corollaire
7.4 du chapitre 7) pour montrer qu’il existe ¯ b ∈ Z p tel que ¯
a ¯ b = ¯ 1.
e) Finir de d´ emontrer que Z p est un corps.
6 Codes correcteurs
Dans quels corps, parmi R, F 2 , F 3 , ce syst` eme poss` ede-t-il une unique solution ?
(Les coefficients entiers du syst` eme sont compris modulo 2 ou 3 si la r´ esolution
est dans F 2 ou F 3 respectivement.)
e) R´ esoudre () dans F 3 .
23. Cet exercice a pour but d’encoder et de d´ ecoder un message ` a l’aide du code de
Reed–Solomon avec m = 3 et k = 3. On doit avoir construit le corps F 8 auparavant
(voir l’exercice 18 ci-dessus). Les calculs sont assez directs, mais ils sont nombreux :
travaillez en ´ equipe. (Tous les participants doivent choisir la mˆ eme racine primitive
α et avoir les mˆ emes tables de F 8 !)
a) Combien d’erreurs au maximum le code de Reed–Solomon C(7, 3) peut-il corriger ?
b) Quel est l’encodage du mot (0, 1, α) ∈ F
3
2 ?
c) L’´ equation (6.12) peut ˆ etre r´ e´ ecrite
p = Cu,
o` u p ∈ F
2
m −1
2 m
, u ∈ F
k
2 m et C ∈ F
(2
m −1)×k
2 m
. Obtenir la matrice C pour le code
C(7, 3).
d) Supposons que le message re¸ cu soit
w = (1, α
4 , α
2 , α
4 , α
2 , α
4 , α
2 ) ∈ F
2
m −1
2 m
.
Choisir les lignes 0, 1 et 4 du syst` eme (6.12) et r´ esoudre afin de trouver le vecteur
(u 0 , u 1 , u 2 ) ∈ F
3
8 .
e) Combien y a-t-il de choix possibles de trois ´ equations distinctes parmi celles
de (6.12) ? Combien faudra-t-il r´ esoudre de syst` emes comme celui de la question
pr´ ec´ edente pour ˆ etre sˆ ur que la r´ eponse pr´ ec´ edente est le message original ?
f) Est-ce que la solution de d) est le message original ?
24. Soit p un nombre premier. Cet exercice prouve que Z p est un corps. On dit que
a et b sont congrus modulo p si leur diff´ erence a − b est un multiple entier de p
(voir l’exemple 6.5).
a) Montrer que « ˆ etre congru » est une relation d’´ equivalence, appel´ ee congruence
modulo p.
b) On identifie Z p ` a l’ensemble des classes d’´ equivalence des entiers modulo p.
Soit ¯
a, ¯ b ∈ Z p . Soient i, j ∈ ¯
a et m, n ∈ ¯ b. Montrer que si i + m ∈ ¯
c et j + n ∈ ¯
d,
alors ¯
c = ¯
d. Mˆ eme question pour i × m et j × n. Cet exercice montre que les
d´ efinitions de + et de × donn´ ees ` a l’exemple 6.5 ne d´ ependent pas de l’´ el´ ement
des classes ¯
a et ¯ b choisi.
c) Montrer que la classe ¯ 0 est le neutre pour + et que ¯ 1 est le neutre pour ×.
d) Soit ¯
a ∈ Z p un ´ el´ ement diff´ erent de ¯ 0. Utiliser l’algorithme d’Euclide (corollaire
7.4 du chapitre 7) pour montrer qu’il existe ¯ b ∈ Z p tel que ¯
a ¯ b = ¯ 1.
e) Finir de d´ emontrer que Z p est un corps.