6.8 Exercices
205
w =
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
,
y a-t-il eu une erreur lors de la transmission ?
b) On d´ esire utiliser le code de Hamming C(2
k
− 1, 2
k
− k − 1) pour un certain
k, mais on ne veut pas ajouter plus de 10 % de bits au mot original. Quelle est la
longueur minimale du mot original et quel est le k caract´ erisant le code ` a utiliser ?
3. Les questions suivantes portent sur le code de Hamming C(2
k
− 1, 2
k
− k − 1).
a) Dans ce code, combien de lettres ont les mots u ` a transmettre ? Combien y
a-t-il de mots distincts que l’on peut transmettre ?
b) Combien de lettres ont les mots encod´ es v ?
c) Combien de mots re¸ cus w distincts (erron´ es ou non) seront d´ ecod´ es comme le
mˆ eme message u ?
d) Existe-t-il des messages re¸ cus qui ne peuvent pas ˆ etre d´ ecod´ es ? (Une autre
fa¸ con de poser cette question est : existe-t-il un w ∈ F
2
k −1
2
qui ne soit pas, ` a une
erreur possible pr` es, l’encodage v d’un message u ∈ F
2
k −k−1
2
?)
4. V´ erifier que l’addition + et la multiplication × dans F 2 d´ efinies par les tables de la
section 6.2 remplissent les conditions de la structure de corps d´ efinie en 6.5.
5. Soit (F, +, ×) un corps fini. Montrer que la table de multiplication des ´ el´ ements non
nuls de F a la propri´ et´ e suivante : toutes les lignes et toutes les colonnes contiennent
tous les ´ el´ ements non nuls de F une et une seule fois.
6. a) Dans le code de Hamming C(7, 4), existe-t-il un message re¸ cu (w 1 , w 2 , w 3 , w 4 ,
w 5 , w 6 , w 7 ) ∈ F
7
2 qu’il est impossible de d´ ecoder comme un des 16 ´ el´ ements (mots)
∈ F
4
2 lorsqu’on fait l’hypoth` ese d’un maximum d’une lettre erron´ ee (voir aussi l’exercice 3 d)) ?
b) Montrer qu’un code du mˆ eme type qu’un code de Hamming transformant un
mot de trois bits en un mot de huit bits ne peut corriger deux erreurs.
c) Construire un code transformant un mot de trois bits en un mot de dix bits et
corrigeant deux erreurs.
7. a) Soit H une matrice k × n, n > k, dont les ´ el´ ements appartiennent ` a F 2 . Soit
G une matrice (n − k) × n dont les ´ el´ ements appartiennent ` a F 2 , qu’obtient de H
en demandant que G soit de rang maximal et que ses lignes soient orthogonales ` a
celles de H. Si H a la forme
H =
M
k×(n−k)
| I k×k
o` u M est une matrice k × (n − k) et I k×k est la matrice identit´ e k × k, montrer que
G peut ˆ etre choisie comme
205
w =
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
,
y a-t-il eu une erreur lors de la transmission ?
b) On d´ esire utiliser le code de Hamming C(2
k
− 1, 2
k
− k − 1) pour un certain
k, mais on ne veut pas ajouter plus de 10 % de bits au mot original. Quelle est la
longueur minimale du mot original et quel est le k caract´ erisant le code ` a utiliser ?
3. Les questions suivantes portent sur le code de Hamming C(2
k
− 1, 2
k
− k − 1).
a) Dans ce code, combien de lettres ont les mots u ` a transmettre ? Combien y
a-t-il de mots distincts que l’on peut transmettre ?
b) Combien de lettres ont les mots encod´ es v ?
c) Combien de mots re¸ cus w distincts (erron´ es ou non) seront d´ ecod´ es comme le
mˆ eme message u ?
d) Existe-t-il des messages re¸ cus qui ne peuvent pas ˆ etre d´ ecod´ es ? (Une autre
fa¸ con de poser cette question est : existe-t-il un w ∈ F
2
k −1
2
qui ne soit pas, ` a une
erreur possible pr` es, l’encodage v d’un message u ∈ F
2
k −k−1
2
?)
4. V´ erifier que l’addition + et la multiplication × dans F 2 d´ efinies par les tables de la
section 6.2 remplissent les conditions de la structure de corps d´ efinie en 6.5.
5. Soit (F, +, ×) un corps fini. Montrer que la table de multiplication des ´ el´ ements non
nuls de F a la propri´ et´ e suivante : toutes les lignes et toutes les colonnes contiennent
tous les ´ el´ ements non nuls de F une et une seule fois.
6. a) Dans le code de Hamming C(7, 4), existe-t-il un message re¸ cu (w 1 , w 2 , w 3 , w 4 ,
w 5 , w 6 , w 7 ) ∈ F
7
2 qu’il est impossible de d´ ecoder comme un des 16 ´ el´ ements (mots)
∈ F
4
2 lorsqu’on fait l’hypoth` ese d’un maximum d’une lettre erron´ ee (voir aussi l’exercice 3 d)) ?
b) Montrer qu’un code du mˆ eme type qu’un code de Hamming transformant un
mot de trois bits en un mot de huit bits ne peut corriger deux erreurs.
c) Construire un code transformant un mot de trois bits en un mot de dix bits et
corrigeant deux erreurs.
7. a) Soit H une matrice k × n, n > k, dont les ´ el´ ements appartiennent ` a F 2 . Soit
G une matrice (n − k) × n dont les ´ el´ ements appartiennent ` a F 2 , qu’obtient de H
en demandant que G soit de rang maximal et que ses lignes soient orthogonales ` a
celles de H. Si H a la forme
H =
M
k×(n−k)
| I k×k
o` u M est une matrice k × (n − k) et I k×k est la matrice identit´ e k × k, montrer que
G peut ˆ etre choisie comme