206
6 Codes correcteurs
G =
I (n−k)×(n−k) | M
t
(n−k)×k
.
b) ´
Ecrire G 4 et H 4 pour le code de Hamming C(15, 11), c’est-` a-dire pour k = 4.
(Commencer par H 4 .)
c) Quel est le message u que l’´ emetteur voulait envoyer si celui-ci utilisait le code
C(15, 11) et si le message re¸ cu se lit (1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1)?
8. Soit p =
1
1000 la probabilit´ e qu’un bit soit transmis erron´ ement.
a) Quelle est la probabilit´ e d’avoir pr´ ecis´ ement deux bits fautifs lors de la transmission de sept bits, comme lors de la transmission d’un mot du code de Hamming
C(7, 4) ?
b) Quelle est la probabilit´ e d’avoir plus d’une erreur lors de la transmission de
sept bits ?
c) Plutˆ ot que le code de Hamming, on transmet un bit en le r´ ep´ etant trois fois.
On d´ ecode ` a la majorit´ e. Calculer la probabilit´ e qu’on d´ ecode correctement le bit
envoy´ e.
d) On transmet quatre bits en r´ ep´ etant chacun trois fois. Quelle est la probabilit´ e
que les quatre bits soient d´ ecod´ es correctement ? En comparant les r´ esultats de cette
question avec b) ci-dessus, on voit que le code simple poss` ede un l´ eger avantage sur
le code de Hamming C(7, 4), mais au prix de transmettre 12 bits plutˆ ot que sept.
9. Chaque livre a un code ISBN (pour International Standard Book Number) qui lui
est propre. Celui-ci est compos´ e de dix chiffres. Par exemple, ISBN 2-12345-678-0.
Les trois premiers segments identifient le groupe linguistique, la maison d’´ edition
et le volume. Le dernier symbole est un symbole d´ etecteur d’erreur choisi parmi
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X}, o` u X repr´ esente 10 en chiffres romains. Appelons a i ,
i = 1, . . . , 10, les 10 symboles. Alors, a 10 est choisi comme le reste de la division de
b =
9
i=1 ia i par 11. Ainsi, dans notre exemple, b = 1 × 2 + 2 × 1 + 3 × 2 + 4 × 3 +
5 × 4 + 6 × 5 + 7 × 6 + 8 × 7 + 9 × 8 = 242 = 11 × 22 + 0.
a) Montrer que ce code d´ etecte une erreur.
b) Montrer que la somme
10
i=1 ia i est divisible par 11.
c) Trouver le dernier chiffre du code ISBN commen¸ cant par
ISBN 0-7267-3514- ?.
d) Un type d’erreur commun est l’inversion de deux chiffres. Par exemple, le code
0-1311-0362-8 sera entr´ e erron´ ement comme 0-1311-0326-8. Montrer que le code
permet de d´ etecter une telle erreur si les deux chiffres cons´ ecutifs ne sont pas identiques (auquel cas l’inversion n’est pas une erreur !).
e) Dans d’autres r´ ef´ erences, on dit que a 10 est choisi de telle sorte que la somme
10
i=1
(11 − i)a i
6 Codes correcteurs
G =
I (n−k)×(n−k) | M
t
(n−k)×k
.
b) ´
Ecrire G 4 et H 4 pour le code de Hamming C(15, 11), c’est-` a-dire pour k = 4.
(Commencer par H 4 .)
c) Quel est le message u que l’´ emetteur voulait envoyer si celui-ci utilisait le code
C(15, 11) et si le message re¸ cu se lit (1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1)?
8. Soit p =
1
1000 la probabilit´ e qu’un bit soit transmis erron´ ement.
a) Quelle est la probabilit´ e d’avoir pr´ ecis´ ement deux bits fautifs lors de la transmission de sept bits, comme lors de la transmission d’un mot du code de Hamming
C(7, 4) ?
b) Quelle est la probabilit´ e d’avoir plus d’une erreur lors de la transmission de
sept bits ?
c) Plutˆ ot que le code de Hamming, on transmet un bit en le r´ ep´ etant trois fois.
On d´ ecode ` a la majorit´ e. Calculer la probabilit´ e qu’on d´ ecode correctement le bit
envoy´ e.
d) On transmet quatre bits en r´ ep´ etant chacun trois fois. Quelle est la probabilit´ e
que les quatre bits soient d´ ecod´ es correctement ? En comparant les r´ esultats de cette
question avec b) ci-dessus, on voit que le code simple poss` ede un l´ eger avantage sur
le code de Hamming C(7, 4), mais au prix de transmettre 12 bits plutˆ ot que sept.
9. Chaque livre a un code ISBN (pour International Standard Book Number) qui lui
est propre. Celui-ci est compos´ e de dix chiffres. Par exemple, ISBN 2-12345-678-0.
Les trois premiers segments identifient le groupe linguistique, la maison d’´ edition
et le volume. Le dernier symbole est un symbole d´ etecteur d’erreur choisi parmi
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X}, o` u X repr´ esente 10 en chiffres romains. Appelons a i ,
i = 1, . . . , 10, les 10 symboles. Alors, a 10 est choisi comme le reste de la division de
b =
9
i=1 ia i par 11. Ainsi, dans notre exemple, b = 1 × 2 + 2 × 1 + 3 × 2 + 4 × 3 +
5 × 4 + 6 × 5 + 7 × 6 + 8 × 7 + 9 × 8 = 242 = 11 × 22 + 0.
a) Montrer que ce code d´ etecte une erreur.
b) Montrer que la somme
10
i=1 ia i est divisible par 11.
c) Trouver le dernier chiffre du code ISBN commen¸ cant par
ISBN 0-7267-3514- ?.
d) Un type d’erreur commun est l’inversion de deux chiffres. Par exemple, le code
0-1311-0362-8 sera entr´ e erron´ ement comme 0-1311-0326-8. Montrer que le code
permet de d´ etecter une telle erreur si les deux chiffres cons´ ecutifs ne sont pas identiques (auquel cas l’inversion n’est pas une erreur !).
e) Dans d’autres r´ ef´ erences, on dit que a 10 est choisi de telle sorte que la somme
10
i=1
(11 − i)a i