188
6 Codes correcteurs
Dans le choix de la matrice G 3 que nous avons fait, chacune des lignes correspond `
a
un des mots ` a transmettre suivants : (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0) et (0, 0, 0, 1). Pour
obtenir le mot g´ en´ eral (u 1 , u 2 , u 3 , u 4 ), il suffit de faire une combinaison lin´ eaire des
quatre lignes de G 3 :
u 1 u 2 u 3 u 4
G 3 ∈ F
7
2 .
(Exercice : v´ erifier que le produit matriciel
u 1 u 2 u 3 u 4
G 3 donne bien une matrice
1 × 7.) L’encodage de u ∈ F
2
k −k−1
2
du code C(2
k
− 1, 2
k
− k − 1) se fait exactement de
la mˆ eme fa¸ con :
v = uG ∈ F
2
k −1
2
.
L’encodage est donc une simple multiplication matricielle sur le corps ` a deux ´ el´ ements
F 2 .
Le d´ ecodage est plus subtil ! Les deux observations suivantes sont au cœur de cette
´ etape. La premi` ere est assez directe : un mot du code v ∈ F
2
k −1
2
sans erreur est annihil´ e
par la matrice de contrˆ ole :
Hv
t = H(uG)
t = HG
t u
t = (GH
t )
t u
t = 0
du fait de l’orthogonalit´ e des lignes de G et H.
La seconde observation est plus difficile. Soit v ∈ F
2
k −1
2
un mot (sans erreur) du
code et v
(i)
∈ F
2
k −1
2
le mot obtenu de v en additionnant 1 `
a la i-i` eme composante de v.
Ainsi, v
(i) est un mot erron´ e en position i. Notons que H(v
(i) )
t
∈ F
k
2 est ind´ ependant
de v ! En effet,
v
(i) = v + (0, 0, . . . , 0,
1
position i
, 0, . . . , 0)
et
H(v
(i) )
t = Hv
t + H
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
0
0
. . .
0
1
0
. . .
0
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
= H
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
0
0
. . .
0
1
0
. . .
0
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
← position i,
puisque v est un mot du code. Ainsi, H(v (i) )
t est la i-i` eme colonne de H. Puisque toutes
les colonnes de H sont distinctes, par d´ efinition de H, une erreur sur la lettre i dans le
mot re¸ cu w ∈ F
2
k −1
2
revient ` a obtenir la i-i` eme colonne de H par le produit Hw
t .
6 Codes correcteurs
Dans le choix de la matrice G 3 que nous avons fait, chacune des lignes correspond `
a
un des mots ` a transmettre suivants : (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0) et (0, 0, 0, 1). Pour
obtenir le mot g´ en´ eral (u 1 , u 2 , u 3 , u 4 ), il suffit de faire une combinaison lin´ eaire des
quatre lignes de G 3 :
u 1 u 2 u 3 u 4
G 3 ∈ F
7
2 .
(Exercice : v´ erifier que le produit matriciel
u 1 u 2 u 3 u 4
G 3 donne bien une matrice
1 × 7.) L’encodage de u ∈ F
2
k −k−1
2
du code C(2
k
− 1, 2
k
− k − 1) se fait exactement de
la mˆ eme fa¸ con :
v = uG ∈ F
2
k −1
2
.
L’encodage est donc une simple multiplication matricielle sur le corps ` a deux ´ el´ ements
F 2 .
Le d´ ecodage est plus subtil ! Les deux observations suivantes sont au cœur de cette
´ etape. La premi` ere est assez directe : un mot du code v ∈ F
2
k −1
2
sans erreur est annihil´ e
par la matrice de contrˆ ole :
Hv
t = H(uG)
t = HG
t u
t = (GH
t )
t u
t = 0
du fait de l’orthogonalit´ e des lignes de G et H.
La seconde observation est plus difficile. Soit v ∈ F
2
k −1
2
un mot (sans erreur) du
code et v
(i)
∈ F
2
k −1
2
le mot obtenu de v en additionnant 1 `
a la i-i` eme composante de v.
Ainsi, v
(i) est un mot erron´ e en position i. Notons que H(v
(i) )
t
∈ F
k
2 est ind´ ependant
de v ! En effet,
v
(i) = v + (0, 0, . . . , 0,
1
position i
, 0, . . . , 0)
et
H(v
(i) )
t = Hv
t + H
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
0
0
. . .
0
1
0
. . .
0
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
= H
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
0
0
. . .
0
1
0
. . .
0
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
← position i,
puisque v est un mot du code. Ainsi, H(v (i) )
t est la i-i` eme colonne de H. Puisque toutes
les colonnes de H sont distinctes, par d´ efinition de H, une erreur sur la lettre i dans le
mot re¸ cu w ∈ F
2
k −1
2
revient ` a obtenir la i-i` eme colonne de H par le produit Hw
t .