6.3 Le code de Hamming C(7, 4)
183
et
x × y + x × z = 1 × 0 + 1 × 1 = 0 + 1 = 1.
Comme dans Q, R et C, 0 est le neutre pour + et 1, le neutre pour ×. Tous les ´ el´ ements
poss` edent un inverse additif. (Exercice : quel est l’inverse additif de 1 ?) Et tous les
´ el´ ements de F 2 \{0} poss` edent un inverse multiplicatif. Dans ce dernier cas, l’affirmation
est tr` es simple, car il n’y a qu’un ´ el´ ement dans F 2 \ {0} = {1}, et l’inverse multiplicatif
de 1 est 1 puisque 1 × 1 = 1.
Tout comme il est possible de d´ efinir des espaces vectoriels R
3 , R
n ou C
2 , il est
possible de parler des espaces vectoriels ` a trois composantes, chacune d’entre elles ´ etant
un ´ el´ ement de F 2 . Il est possible d’additionner deux vecteurs de F
3
2 et d’en faire des
combinaisons lin´ eaires (avec coefficients dans F 2 ´ evidemment !). Par exemple :
(1, 0, 1) + (0, 1, 0) = (1, 1, 1),
(1, 0, 1) + (0, 1, 1) = (1, 1, 0),
et
0 · (1, 0, 1) + 1 · (0, 1, 1) + 1 · (1, 1, 0) = (1, 0, 1).
Puisque les composantes doivent ˆ etre dans F 2 et que seules les combinaisons lin´ eaires
avec coefficients dans F 2 sont permises, le nombre de vecteurs dans F
3
2 (et dans tout
F
n
2 , n < ∞) est fini ! Attention, mˆ eme si la dimension de R
3 est 3 (et donc finie), le
nombre de vecteurs dans R
3 est infini. Pour F
3
2 , ce nombre de vecteurs est huit, et la
liste compl` ete des vecteurs de cet espace vectoriel est
{(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1)}.
(Exercice : rappeler la d´ efinition de dimension d’un espace vectoriel et calculer la dimension de F
3
2 .) Les espaces vectoriels sur des corps finis tel F 2 sont d´ eroutants, car
leurs vecteurs sont en nombre fini, et les cours d’alg` ebre lin´ eaire n’en parlent pas ou
peu mˆ eme si beaucoup des m´ ethodes qui y sont d´ evelopp´ ees (le calcul matriciel, entre
autres) s’appliquent ` a eux.
6.3 Le code de Hamming C(7, 4)
Voici un premier exemple de code correcteur moderne. Plutˆ ot que les lettres usuelles
(a, b, c, ...), il utilise un alphabet constitu´ e de deux lettres (F 2 ) que nous d´ esignerons par
0 et 1
4 . Nous nous limiterons de plus `
a transmettre des mots ayant pr´ ecis´ ement quatre
lettres (u 1 , u 2 , u 3 , u 4 ). (Exercice : est-ce une restriction grave ?) Notre vocabulaire ou
4 Comme nous l’avons vu dans l’introduction, ceci n’est pas une restriction puisqu’il existe
des « dictionnaires » traduisant notre alphabet latin en une s´ erie de caract` eres 0 et 1.
183
et
x × y + x × z = 1 × 0 + 1 × 1 = 0 + 1 = 1.
Comme dans Q, R et C, 0 est le neutre pour + et 1, le neutre pour ×. Tous les ´ el´ ements
poss` edent un inverse additif. (Exercice : quel est l’inverse additif de 1 ?) Et tous les
´ el´ ements de F 2 \{0} poss` edent un inverse multiplicatif. Dans ce dernier cas, l’affirmation
est tr` es simple, car il n’y a qu’un ´ el´ ement dans F 2 \ {0} = {1}, et l’inverse multiplicatif
de 1 est 1 puisque 1 × 1 = 1.
Tout comme il est possible de d´ efinir des espaces vectoriels R
3 , R
n ou C
2 , il est
possible de parler des espaces vectoriels ` a trois composantes, chacune d’entre elles ´ etant
un ´ el´ ement de F 2 . Il est possible d’additionner deux vecteurs de F
3
2 et d’en faire des
combinaisons lin´ eaires (avec coefficients dans F 2 ´ evidemment !). Par exemple :
(1, 0, 1) + (0, 1, 0) = (1, 1, 1),
(1, 0, 1) + (0, 1, 1) = (1, 1, 0),
et
0 · (1, 0, 1) + 1 · (0, 1, 1) + 1 · (1, 1, 0) = (1, 0, 1).
Puisque les composantes doivent ˆ etre dans F 2 et que seules les combinaisons lin´ eaires
avec coefficients dans F 2 sont permises, le nombre de vecteurs dans F
3
2 (et dans tout
F
n
2 , n < ∞) est fini ! Attention, mˆ eme si la dimension de R
3 est 3 (et donc finie), le
nombre de vecteurs dans R
3 est infini. Pour F
3
2 , ce nombre de vecteurs est huit, et la
liste compl` ete des vecteurs de cet espace vectoriel est
{(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1)}.
(Exercice : rappeler la d´ efinition de dimension d’un espace vectoriel et calculer la dimension de F
3
2 .) Les espaces vectoriels sur des corps finis tel F 2 sont d´ eroutants, car
leurs vecteurs sont en nombre fini, et les cours d’alg` ebre lin´ eaire n’en parlent pas ou
peu mˆ eme si beaucoup des m´ ethodes qui y sont d´ evelopp´ ees (le calcul matriciel, entre
autres) s’appliquent ` a eux.
6.3 Le code de Hamming C(7, 4)
Voici un premier exemple de code correcteur moderne. Plutˆ ot que les lettres usuelles
(a, b, c, ...), il utilise un alphabet constitu´ e de deux lettres (F 2 ) que nous d´ esignerons par
0 et 1
4 . Nous nous limiterons de plus `
a transmettre des mots ayant pr´ ecis´ ement quatre
lettres (u 1 , u 2 , u 3 , u 4 ). (Exercice : est-ce une restriction grave ?) Notre vocabulaire ou
4 Comme nous l’avons vu dans l’introduction, ceci n’est pas une restriction puisqu’il existe
des « dictionnaires » traduisant notre alphabet latin en une s´ erie de caract` eres 0 et 1.