190
6 Codes correcteurs
Exemple 6.3 Les trois corps les plus familiers sont Q, R et C, c’est-` a-dire les nombres
rationnels, r´ eels et complexes. Ils ne sont pas finis. La liste des propri´ et´ es ci-dessus
est probablement famili` ere au lecteur. Le but de donner la d´ efinition de corps est donc
d’axiomatiser les propri´ et´ es de ces trois ensembles. L’avantage est de pouvoir ´ etendre ` a
des corps moins intuitifs les techniques de calcul d´ evelopp´ ees pour Q, R et C et qui ne
reposent que sur (P1), (P2), (P3), (P4) et (P5).
Exemple 6.4 F 2 muni des op´ erations + et × donn´ ees ` a la section 6.2 est un corps.
Les calculs faits durant l’´ etude des codes de Hamming vous ont sans doute convaincu
que (F 2 , +, ×) est bien un corps. Une v´ erification syst´ ematique est propos´ ee ` a l’exercice
4 en fin de chapitre.
Exemple 6.5 F 2 n’est que le premier d’une famille de corps finis. Soit p un nombre
premier. On dit que deux nombres a et b sont congrus modulo p si p divise a − b. La
congruence est une relation d’´ equivalence sur les entiers. On a exactement p classes
d’´ equivalence repr´ esent´ ees par ¯ 0, ¯ 1, . . . , p − 1. Par exemple, pour p = 3, les entiers Z
sont partitionn´ es en trois sous-ensembles :
¯ 0 = {. . . , −6, −3, 0, 3, 6, . . .},
¯ 1 = {. . . , −5, −2, 1, 4, 7, . . .},
¯ 2 = {. . . , −4, −1, 2, 5, 8, . . .}.
L’ensemble Z p = { ¯ 0, ¯ 1, ¯ 2, . . . , p − 1} est l’ensemble de ces classes d’´ equivalence. On
d´ efinit, entre ces classes, les op´ erations + et × comme l’addition et la multiplication
modulo p. Pour faire l’addition modulo p des classes ¯
a et ¯ b, on choisit un ´ el´ ement de la
classe ¯
a et un autre de la classe ¯ b. Le r´ esultat de ¯
a + ¯ b est a + b, c’est-` a-dire la classe
de Z p ` a laquelle appartient la somme des deux ´ el´ ements choisis. (Exercice : pourquoi
cette classe ne d´ epend-elle pas du choix des ´ el´ ements, mais seulement des classes ¯
a et
¯ b ? Cette d´ efinition co¨ ıncide-t-elle avec celle donn´ ee pr´ ec´ edemment en 6.2 pour le cas
F 2 ?) La multiplication entre classes est d´ efinie de la mˆ eme fa¸ con. Il est usuel d’omettre
le « ¯ » qui d´ enote la classe d’´ equivalence. L’exercice 24 d´ emontre que (Z p , +, ×) est un
corps.
Exemple 6.6 L’ensemble des entiers Z n’est pas un corps, car l’´ el´ ement 2, par exemple,
n’y a pas d’inverse multiplicatif.
Exemple 6.7 Soit F un corps. D´ enotons par ˜
F l’ensemble de tous les quotients de
polynˆ omes en une variable x ` a coefficients dans F ; ainsi, tous les ´ el´ ements de ˜
F sont de la
forme
p(x)
q(x) , p(x) et q(x) ´ etant des polynˆ omes (de degr´ e fini par d´ efinition) ` a coefficients
dans F et q ´ etant diff´ erent du polynˆ ome identiquement nul. Si nous munissons ˜
F de
l’addition et de la multiplication usuelles pour les fonctions, alors ( ˜
F, +, ×) est un corps.
Les quotients de polynˆ omes 0/1 = 0 (c’est-` a-dire le quotient tel que p(x) = 0 et q(x) = 1)
et 1/1 (c’est-` a-dire tel que p(x) = q(x) = 1) sont les neutres additif et multiplicatif. On
peut ais´ ement v´ erifier les propri´ et´ es (P1) ` a (P5).
6 Codes correcteurs
Exemple 6.3 Les trois corps les plus familiers sont Q, R et C, c’est-` a-dire les nombres
rationnels, r´ eels et complexes. Ils ne sont pas finis. La liste des propri´ et´ es ci-dessus
est probablement famili` ere au lecteur. Le but de donner la d´ efinition de corps est donc
d’axiomatiser les propri´ et´ es de ces trois ensembles. L’avantage est de pouvoir ´ etendre ` a
des corps moins intuitifs les techniques de calcul d´ evelopp´ ees pour Q, R et C et qui ne
reposent que sur (P1), (P2), (P3), (P4) et (P5).
Exemple 6.4 F 2 muni des op´ erations + et × donn´ ees ` a la section 6.2 est un corps.
Les calculs faits durant l’´ etude des codes de Hamming vous ont sans doute convaincu
que (F 2 , +, ×) est bien un corps. Une v´ erification syst´ ematique est propos´ ee ` a l’exercice
4 en fin de chapitre.
Exemple 6.5 F 2 n’est que le premier d’une famille de corps finis. Soit p un nombre
premier. On dit que deux nombres a et b sont congrus modulo p si p divise a − b. La
congruence est une relation d’´ equivalence sur les entiers. On a exactement p classes
d’´ equivalence repr´ esent´ ees par ¯ 0, ¯ 1, . . . , p − 1. Par exemple, pour p = 3, les entiers Z
sont partitionn´ es en trois sous-ensembles :
¯ 0 = {. . . , −6, −3, 0, 3, 6, . . .},
¯ 1 = {. . . , −5, −2, 1, 4, 7, . . .},
¯ 2 = {. . . , −4, −1, 2, 5, 8, . . .}.
L’ensemble Z p = { ¯ 0, ¯ 1, ¯ 2, . . . , p − 1} est l’ensemble de ces classes d’´ equivalence. On
d´ efinit, entre ces classes, les op´ erations + et × comme l’addition et la multiplication
modulo p. Pour faire l’addition modulo p des classes ¯
a et ¯ b, on choisit un ´ el´ ement de la
classe ¯
a et un autre de la classe ¯ b. Le r´ esultat de ¯
a + ¯ b est a + b, c’est-` a-dire la classe
de Z p ` a laquelle appartient la somme des deux ´ el´ ements choisis. (Exercice : pourquoi
cette classe ne d´ epend-elle pas du choix des ´ el´ ements, mais seulement des classes ¯
a et
¯ b ? Cette d´ efinition co¨ ıncide-t-elle avec celle donn´ ee pr´ ec´ edemment en 6.2 pour le cas
F 2 ?) La multiplication entre classes est d´ efinie de la mˆ eme fa¸ con. Il est usuel d’omettre
le « ¯ » qui d´ enote la classe d’´ equivalence. L’exercice 24 d´ emontre que (Z p , +, ×) est un
corps.
Exemple 6.6 L’ensemble des entiers Z n’est pas un corps, car l’´ el´ ement 2, par exemple,
n’y a pas d’inverse multiplicatif.
Exemple 6.7 Soit F un corps. D´ enotons par ˜
F l’ensemble de tous les quotients de
polynˆ omes en une variable x ` a coefficients dans F ; ainsi, tous les ´ el´ ements de ˜
F sont de la
forme
p(x)
q(x) , p(x) et q(x) ´ etant des polynˆ omes (de degr´ e fini par d´ efinition) ` a coefficients
dans F et q ´ etant diff´ erent du polynˆ ome identiquement nul. Si nous munissons ˜
F de
l’addition et de la multiplication usuelles pour les fonctions, alors ( ˜
F, +, ×) est un corps.
Les quotients de polynˆ omes 0/1 = 0 (c’est-` a-dire le quotient tel que p(x) = 0 et q(x) = 1)
et 1/1 (c’est-` a-dire tel que p(x) = q(x) = 1) sont les neutres additif et multiplicatif. On
peut ais´ ement v´ erifier les propri´ et´ es (P1) ` a (P5).