208
6 Codes correcteurs
14. a) Soient q(x) et p(x) deux polynˆ omes de F[x]. Montrer qu’il existe des polynˆ omes s(x) et r(x) ∈ F[x] tels que q(x) = s(x)p(x) + r(x) avec 0 ≤ degr´ e de r <
degr´ e de p.
b) En conclure que q(x) = r(x) (mod p(x)).
15. Soit M n l’ensemble des matrices n × n, et d´ enotons par + et · l’addition et la
multiplication matricielles usuelles. Est-ce que (M n , +, ·) est un corps ? Justifier.
16. Soient E un ensemble fini et U (E) l’ensemble de ses sous-ensembles. Par exemple,
si E = {a, b, c}, alors U (E) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. On
d´ efinit sur U (E) des op´ erations + et × respectivement par l’union et par l’intersection ensemblistes usuelles. Pour +, le neutre est ∅, et pour ×, le neutre est E.
Est-ce que U (E) muni de + et de × forme un corps ? Le montrer ou donner les
propri´ et´ es qui ne sont pas satisfaites.
17. a) Soit F 3 le corps ` a trois ´ el´ ements. Il y a neuf polynˆ omes de degr´ e 2 de la forme
x
2 +ax+b o` u a, b ∈ F 3 . ´
Enum´ erer ces neuf polynˆ omes et identifier les trois qui sont
irr´ eductibles. (Suggestion : commencer par ´ enum´ erer les polynˆ omes de la forme
(x + c)(x + d).)
b) Afin de construire le corps `
a neuf ´ el´ ements, on consid` ere le quotient F 3 [x]/q(x)
o` u q(x) = x
2 + 2x + 2. Montrer que x est une racine primitive en exprimant les
huit ´ el´ ements x
i , i = 1, 2, . . . , 8, comme polynˆ omes de degr´ e un ou z´ ero.
c) Dans la notation de b), pour quel i l’´ egalit´ e x
3 + x
5 = x
i est-elle juste ?
d) Le corps F 9 a maintenant ´ et´ e construit de deux fa¸ cons diff´ erentes, la premi` ere
dans l’exemple 6.14 ` a la section 6.5 et ci-dessus ` a la question b). Pouvez-vous
construire l’isomorphisme entre le r´ esultat de ces deux constructions (voir le
th´ eor` eme 6.18 pour la d´ efinition d’isomorphisme) ?
e) En a), vous avez identifi´ e trois polynˆ omes irr´ eductibles. Soient p(x) celui qui
est utilis´ e dans l’exemple 6.14, q(x) celui qui l’est ci-dessus en b), et r(x), le
troisi` eme. Est-ce que le polynˆ ome i(x) = x est une racine primitive de F 3 [x]/r(x) ?
Que faudrait-il faire pour obtenir les tables d’addition et de multiplication de
F 3 [x]/r(x) ?
18. a) Trouver le seul polynˆ ome irr´ eductible sur F 2 de degr´ e 2, les deux de degr´ e 3
et les trois de degr´ e 4.
b) Construire les tables d’addition et de multiplication du corps F 8 ` a huit
´ el´ ements.
19. a) Pour les ambitieux : construire F 16 .
b) ´
Egalement pour les ambitieux : trouver un polynˆ ome irr´ eductible de degr´ e
8 sur F 2 . Ce polynˆ ome vous permettrait de construire un corps ` a combien
d’´ el´ ements ?
20. a) On consid` ere le code correcteur d’erreurs qui consiste ` a r´ ep´ eter trois fois
chaque bit. Pour envoyer un mot de sept bits, on commence par l’allonger `
a 21
bits. Par exemple, pour envoyer 0100111 on envoie
000 111 000 000 111 111 111
6 Codes correcteurs
14. a) Soient q(x) et p(x) deux polynˆ omes de F[x]. Montrer qu’il existe des polynˆ omes s(x) et r(x) ∈ F[x] tels que q(x) = s(x)p(x) + r(x) avec 0 ≤ degr´ e de r <
degr´ e de p.
b) En conclure que q(x) = r(x) (mod p(x)).
15. Soit M n l’ensemble des matrices n × n, et d´ enotons par + et · l’addition et la
multiplication matricielles usuelles. Est-ce que (M n , +, ·) est un corps ? Justifier.
16. Soient E un ensemble fini et U (E) l’ensemble de ses sous-ensembles. Par exemple,
si E = {a, b, c}, alors U (E) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. On
d´ efinit sur U (E) des op´ erations + et × respectivement par l’union et par l’intersection ensemblistes usuelles. Pour +, le neutre est ∅, et pour ×, le neutre est E.
Est-ce que U (E) muni de + et de × forme un corps ? Le montrer ou donner les
propri´ et´ es qui ne sont pas satisfaites.
17. a) Soit F 3 le corps ` a trois ´ el´ ements. Il y a neuf polynˆ omes de degr´ e 2 de la forme
x
2 +ax+b o` u a, b ∈ F 3 . ´
Enum´ erer ces neuf polynˆ omes et identifier les trois qui sont
irr´ eductibles. (Suggestion : commencer par ´ enum´ erer les polynˆ omes de la forme
(x + c)(x + d).)
b) Afin de construire le corps `
a neuf ´ el´ ements, on consid` ere le quotient F 3 [x]/q(x)
o` u q(x) = x
2 + 2x + 2. Montrer que x est une racine primitive en exprimant les
huit ´ el´ ements x
i , i = 1, 2, . . . , 8, comme polynˆ omes de degr´ e un ou z´ ero.
c) Dans la notation de b), pour quel i l’´ egalit´ e x
3 + x
5 = x
i est-elle juste ?
d) Le corps F 9 a maintenant ´ et´ e construit de deux fa¸ cons diff´ erentes, la premi` ere
dans l’exemple 6.14 ` a la section 6.5 et ci-dessus ` a la question b). Pouvez-vous
construire l’isomorphisme entre le r´ esultat de ces deux constructions (voir le
th´ eor` eme 6.18 pour la d´ efinition d’isomorphisme) ?
e) En a), vous avez identifi´ e trois polynˆ omes irr´ eductibles. Soient p(x) celui qui
est utilis´ e dans l’exemple 6.14, q(x) celui qui l’est ci-dessus en b), et r(x), le
troisi` eme. Est-ce que le polynˆ ome i(x) = x est une racine primitive de F 3 [x]/r(x) ?
Que faudrait-il faire pour obtenir les tables d’addition et de multiplication de
F 3 [x]/r(x) ?
18. a) Trouver le seul polynˆ ome irr´ eductible sur F 2 de degr´ e 2, les deux de degr´ e 3
et les trois de degr´ e 4.
b) Construire les tables d’addition et de multiplication du corps F 8 ` a huit
´ el´ ements.
19. a) Pour les ambitieux : construire F 16 .
b) ´
Egalement pour les ambitieux : trouver un polynˆ ome irr´ eductible de degr´ e
8 sur F 2 . Ce polynˆ ome vous permettrait de construire un corps ` a combien
d’´ el´ ements ?
20. a) On consid` ere le code correcteur d’erreurs qui consiste ` a r´ ep´ eter trois fois
chaque bit. Pour envoyer un mot de sept bits, on commence par l’allonger `
a 21
bits. Par exemple, pour envoyer 0100111 on envoie
000 111 000 000 111 111 111