6.4 Les codes de Hamming C(2
k − 1, 2
k − k − 1)
187
G 3 =
⎛
⎜
⎜
⎝
1 0 0 0 1 1 0
0 1 0 0 1 0 1
0 0 1 0 0 1 1
0 0 0 1 1 1 1
⎞
⎟
⎟
⎠ .
Par exemple, la premi` ere ligne de G 3 correspond au mot du code tel que u 1 = 1 et
u 2 = u 3 = u 4 = 0. Alors, par les r` egles que nous avons choisies, v 1 = 1, v 2 = v 3 = v 4 = 0,
et v 5 = u 1 + u 2 + u 4 = 1, v 6 = u 1 + u 3 + u 4 = 1 et v 7 = u 2 + u 3 + u 4 = 0. Ce sont les
´ el´ ements de la premi` ere ligne. Les 16 mots du code C seront d´ eduits des 16 diff´ erentes
combinaisons lin´ eaires possibles des quatre lignes de G 3 . Puisque G est d´ efinie `
a l’aide
du choix d’une base, G n’est pas d´ efinie uniquement.
La matrice de contrˆ ole H est une matrice k × (2
k
− 1) dont les k lignes forment une
base du compl´ ement orthogonal du sous-espace engendr´ e par les lignes de G. Le produit
scalaire est le produit usuel : si v, w ∈ F
n
2 , alors (v, w) =
n
i=1 v i w i ∈ F 2 . (L’appendice
` a la fin de ce chapitre rappelle la d´ efinition de produit scalaire et souligne les diff´ erences
importantes entre cette structure sur les corps usuels (Q, R et C) et sur les corps finis.
Certaines de ces diff´ erences ne sont pas tr` es intuitives !) Pour C(7, 4) et le choix de G 3
ci-dessus, la matrice de contrˆ ole H 3 peut ˆ etre choisie ainsi :
H 3 =
⎛
⎝
1 1 0 1 1 0 0
1 0 1 1 0 1 0
0 1 1 1 0 0 1
⎞
⎠ .
Puisque les lignes de G et de H sont orthogonales deux `
a deux, les matrices G et H
satisfont `
a
GH
t = 0.
(6.3)
Par exemple, pour k = 3 :
G 3 H
t
3 =
⎛
⎜
⎜
⎝
1 0 0 0 1 1 0
0 1 0 0 1 0 1
0 0 1 0 0 1 1
0 0 0 1 1 1 1
⎞
⎟
⎟
⎠
4×7
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
1 1 0
1 0 1
0 1 1
1 1 1
1 0 0
0 1 0
0 0 1
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
7×3
=
⎛
⎜
⎜
⎝
0 0 0
0 0 0
0 0 0
0 0 0
⎞
⎟
⎟
⎠
4×3
.
Le code de Hamming g´ en´ eral C(2
k
− 1, 2
k
− k − 1) est d´ efini par la donn´ ee de la
matrice de contrˆ ole H. Cette matrice poss` ede comme vecteurs colonnes tous les vecteurs
non nuls de F
k
2 . Puisque F
k
2 contient 2
k vecteurs (dont le vecteur nul), H est bien une
matrice k × (2
k
− 1). La matrice H 3 en est un exemple. Comme nous l’avons dit, les
lignes de la matrice g´ en´ eratrice G engendrent le compl´ ement orthogonal des lignes de
H. Ceci termine la d´ efinition du code de Hamming C(2
k
− 1, 2
k
− k − 1).
Voici comment l’encodage et le d´ ecodage sont faits.
k − 1, 2
k − k − 1)
187
G 3 =
⎛
⎜
⎜
⎝
1 0 0 0 1 1 0
0 1 0 0 1 0 1
0 0 1 0 0 1 1
0 0 0 1 1 1 1
⎞
⎟
⎟
⎠ .
Par exemple, la premi` ere ligne de G 3 correspond au mot du code tel que u 1 = 1 et
u 2 = u 3 = u 4 = 0. Alors, par les r` egles que nous avons choisies, v 1 = 1, v 2 = v 3 = v 4 = 0,
et v 5 = u 1 + u 2 + u 4 = 1, v 6 = u 1 + u 3 + u 4 = 1 et v 7 = u 2 + u 3 + u 4 = 0. Ce sont les
´ el´ ements de la premi` ere ligne. Les 16 mots du code C seront d´ eduits des 16 diff´ erentes
combinaisons lin´ eaires possibles des quatre lignes de G 3 . Puisque G est d´ efinie `
a l’aide
du choix d’une base, G n’est pas d´ efinie uniquement.
La matrice de contrˆ ole H est une matrice k × (2
k
− 1) dont les k lignes forment une
base du compl´ ement orthogonal du sous-espace engendr´ e par les lignes de G. Le produit
scalaire est le produit usuel : si v, w ∈ F
n
2 , alors (v, w) =
n
i=1 v i w i ∈ F 2 . (L’appendice
` a la fin de ce chapitre rappelle la d´ efinition de produit scalaire et souligne les diff´ erences
importantes entre cette structure sur les corps usuels (Q, R et C) et sur les corps finis.
Certaines de ces diff´ erences ne sont pas tr` es intuitives !) Pour C(7, 4) et le choix de G 3
ci-dessus, la matrice de contrˆ ole H 3 peut ˆ etre choisie ainsi :
H 3 =
⎛
⎝
1 1 0 1 1 0 0
1 0 1 1 0 1 0
0 1 1 1 0 0 1
⎞
⎠ .
Puisque les lignes de G et de H sont orthogonales deux `
a deux, les matrices G et H
satisfont `
a
GH
t = 0.
(6.3)
Par exemple, pour k = 3 :
G 3 H
t
3 =
⎛
⎜
⎜
⎝
1 0 0 0 1 1 0
0 1 0 0 1 0 1
0 0 1 0 0 1 1
0 0 0 1 1 1 1
⎞
⎟
⎟
⎠
4×7
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
1 1 0
1 0 1
0 1 1
1 1 1
1 0 0
0 1 0
0 0 1
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
7×3
=
⎛
⎜
⎜
⎝
0 0 0
0 0 0
0 0 0
0 0 0
⎞
⎟
⎟
⎠
4×3
.
Le code de Hamming g´ en´ eral C(2
k
− 1, 2
k
− k − 1) est d´ efini par la donn´ ee de la
matrice de contrˆ ole H. Cette matrice poss` ede comme vecteurs colonnes tous les vecteurs
non nuls de F
k
2 . Puisque F
k
2 contient 2
k vecteurs (dont le vecteur nul), H est bien une
matrice k × (2
k
− 1). La matrice H 3 en est un exemple. Comme nous l’avons dit, les
lignes de la matrice g´ en´ eratrice G engendrent le compl´ ement orthogonal des lignes de
H. Ceci termine la d´ efinition du code de Hamming C(2
k
− 1, 2
k
− k − 1).
Voici comment l’encodage et le d´ ecodage sont faits.