6.5 Corps finis
189
Le d´ ecodage fonctionne comme suit :
w ∈ F
2
k −1
2
re¸ cu −→ calcul du produit Hw
t
∈ F
k
2
−→
Hw
t est nul
⇒ w passe ` a l’´ etape suivante
Hw
t est ´ egal `
a la colonne i de H ⇒
la lettre w i est chang´ ee
−→
recherche de la combinaison lin´ eaire
des lignes de G donnant le w corrig´ e
Quoique ces codes ne corrigent qu’une erreur, ils sont tr` es ´ economiques pour k suffisamment grand. Par exemple, pour k = 7, il suffit d’ajouter sept bits `
a un message
de 120 bits pour ˆ etre sˆ ur de pouvoir corriger une erreur. C’est pr´ ecis´ ement le code de
Hamming C(2
k
− 1, 2
k
− k − 1), k = 7, qui est utilis´ e pour le Minitel.
6.5 Corps finis
Pour pr´ esenter le code de Reed–Solomon, nous aurons besoin de connaˆ ıtre quelques
propri´ et´ es des corps finis. Cette section couvre les ´ el´ ements requis.
D´ efinition 6.1 Un corps F est un ensemble muni de deux op´ erations + et × et contenant au moins deux ´ el´ ements not´ es 0 et 1 ∈ F, tel que les cinq propri´ et´ es suivantes
soient satisfaites :
(P1) commutativit´ e
a + b = b + a et a × b = b × a,
∀a, b ∈ F
(P2) associativit´ e
(a + b) + c = a + (b + c) et (a × b) × c = a × (b × c),
∀a, b, c ∈ F
(P3) distributivit´ e
(a + b) × c = (a × c) + (b × c),
∀a, b, c ∈ F
(P4) neutres additif et multiplicatif
a + 0 = a et a × 1 = a,
∀a ∈ F
(P5) existence des inverses additif et multiplicatif
∀ a ∈ F, ∃ a
∈ F tel que a + a
= 0,
∀ a ∈ F \ {0}, ∃ a
∈ F tel que a × a
= 1.
D´ efinition 6.2 Un corps F est dit fini si le nombre d’´ el´ ements dans F est fini.
189
Le d´ ecodage fonctionne comme suit :
w ∈ F
2
k −1
2
re¸ cu −→ calcul du produit Hw
t
∈ F
k
2
−→
Hw
t est nul
⇒ w passe ` a l’´ etape suivante
Hw
t est ´ egal `
a la colonne i de H ⇒
la lettre w i est chang´ ee
−→
recherche de la combinaison lin´ eaire
des lignes de G donnant le w corrig´ e
Quoique ces codes ne corrigent qu’une erreur, ils sont tr` es ´ economiques pour k suffisamment grand. Par exemple, pour k = 7, il suffit d’ajouter sept bits `
a un message
de 120 bits pour ˆ etre sˆ ur de pouvoir corriger une erreur. C’est pr´ ecis´ ement le code de
Hamming C(2
k
− 1, 2
k
− k − 1), k = 7, qui est utilis´ e pour le Minitel.
6.5 Corps finis
Pour pr´ esenter le code de Reed–Solomon, nous aurons besoin de connaˆ ıtre quelques
propri´ et´ es des corps finis. Cette section couvre les ´ el´ ements requis.
D´ efinition 6.1 Un corps F est un ensemble muni de deux op´ erations + et × et contenant au moins deux ´ el´ ements not´ es 0 et 1 ∈ F, tel que les cinq propri´ et´ es suivantes
soient satisfaites :
(P1) commutativit´ e
a + b = b + a et a × b = b × a,
∀a, b ∈ F
(P2) associativit´ e
(a + b) + c = a + (b + c) et (a × b) × c = a × (b × c),
∀a, b, c ∈ F
(P3) distributivit´ e
(a + b) × c = (a × c) + (b × c),
∀a, b, c ∈ F
(P4) neutres additif et multiplicatif
a + 0 = a et a × 1 = a,
∀a ∈ F
(P5) existence des inverses additif et multiplicatif
∀ a ∈ F, ∃ a
∈ F tel que a + a
= 0,
∀ a ∈ F \ {0}, ∃ a
∈ F tel que a × a
= 1.
D´ efinition 6.2 Un corps F est dit fini si le nombre d’´ el´ ements dans F est fini.