1.5 La cartographie
27
de deux ´ el´ ements non nuls du corps. Donc β est de la forme x
k o` u k ∈ {0, . . . 2
r
− 2},
ce qui entraˆ ıne que l’ensemble {βx
i+m , 0 ≤ i ≤ M − 1} forme une permutation de
F 2 r \ {0} = {1, x, . . . , x
2
r −2
}. La fonction trace T prend la valeur 1 sur la moiti´ e des
´ el´ ements de F 2 r et 0 sur l’autre moiti´ e. Comme elle prend la valeur 0 en 0, elle prend la
valeur 1 sur 2
r−1 des ´ el´ ements de F 2 r \ {0} et la valeur 0 sur 2
r−1
− 1 des ´ el´ ements de
F 2 r \ {0}. D’o` u Cor(B, C) = −1.
Corollaire 1.14 La p´ eriode de la suite pseudo-al´ eatoire g´ en´ er´ ee par le registre `
a d´ ecalage est exactement M = 2
r
− 1.
Preuve Si la p´ eriode ´ etait ´ egale `
a K < M, alors la suite co¨ ınciderait avec sa translat´ ee
de K composantes, et les deux auraient une corr´ elation ´ egale `
a M , en contradiction avec
la proposition 1.13.
Si, maintenant, on veut g´ en´ erer d’autres suites pseudo-al´ eatoires de mˆ eme longueur
correspondant aux signaux des autres satellites, on peut utiliser le mˆ eme principe et
changer de polynˆ ome P (x). (On veut une suite diff´ erente pour chaque satellite !) La
th´ eorie de Galois permet dans certains cas de calculer la corr´ elation de cette nouvelle
suite avec la pr´ ec´ edente et ses translat´ ees. Les ing´ enieurs pour leur part se contentent
d’utiliser des tables.
1.5 La cartographie
Comme nous l’avons mentionn´ e dans l’introduction, la cartographie pose des probl` emes non triviaux si l’on veut repr´ esenter fid` element la Terre. En effet, une carte doit
nous servir ` a nous diriger. On pourrait vouloir qu’elle pr´ eserve les distances r´ eelles pour
que, si l’on choisit sur la carte le plus court chemin entre deux points, ce chemin soit
effectivement le plus court. Pour une carte terrestre, ce genre de contrainte a un peu
moins d’importance, car on est soumis `
a la contrainte de demeurer sur une route si
l’on se prom` ene en v´ ehicule motoris´ e. Si l’on se prom` ene ` a pied, les distortions sont
suffisamment petites pour ˆ etre n´ eglig´ ees. Par contre, pour choisir la trajectoire d’un
avion, ou encore, pour un navigateur, le probl` eme est r´ eel. De plus, pour un navigateur
` a la voile qui dispose d’outils rudimentaires, il ne suffit pas de dessiner un chemin sur la
carte. Encore faut-il pouvoir s’y tenir. Jusqu’` a l’arriv´ ee r´ ecente du GPS, il ´ etait courant
de se servir du champ magn´ etique terrestre. En utilisant un compas magn´ etique, on
peut s’assurer que le bateau suive une trajectoire qui fait un angle constant avec les
lignes du champ magn´ etique terrestre. Une telle trajectoire n’est pas n´ ecessairement le
plus court chemin entre deux points, mais, comme c’est une trajectoire naturelle, ce
serait commode qu’une telle trajectoire soit repr´ esent´ ee par une droite sur une carte.
Les cartes marines ont cette propri´ et´ e. Par contre, sur une carte marine, les aires ne
sont pas pr´ eserv´ ees : deux r´ egions du globe qui ont la mˆ eme superficie ne sont pas
n´ ecessairement repr´ esent´ ees sur la carte par des portions de surface de mˆ eme aire.
27
de deux ´ el´ ements non nuls du corps. Donc β est de la forme x
k o` u k ∈ {0, . . . 2
r
− 2},
ce qui entraˆ ıne que l’ensemble {βx
i+m , 0 ≤ i ≤ M − 1} forme une permutation de
F 2 r \ {0} = {1, x, . . . , x
2
r −2
}. La fonction trace T prend la valeur 1 sur la moiti´ e des
´ el´ ements de F 2 r et 0 sur l’autre moiti´ e. Comme elle prend la valeur 0 en 0, elle prend la
valeur 1 sur 2
r−1 des ´ el´ ements de F 2 r \ {0} et la valeur 0 sur 2
r−1
− 1 des ´ el´ ements de
F 2 r \ {0}. D’o` u Cor(B, C) = −1.
Corollaire 1.14 La p´ eriode de la suite pseudo-al´ eatoire g´ en´ er´ ee par le registre `
a d´ ecalage est exactement M = 2
r
− 1.
Preuve Si la p´ eriode ´ etait ´ egale `
a K < M, alors la suite co¨ ınciderait avec sa translat´ ee
de K composantes, et les deux auraient une corr´ elation ´ egale `
a M , en contradiction avec
la proposition 1.13.
Si, maintenant, on veut g´ en´ erer d’autres suites pseudo-al´ eatoires de mˆ eme longueur
correspondant aux signaux des autres satellites, on peut utiliser le mˆ eme principe et
changer de polynˆ ome P (x). (On veut une suite diff´ erente pour chaque satellite !) La
th´ eorie de Galois permet dans certains cas de calculer la corr´ elation de cette nouvelle
suite avec la pr´ ec´ edente et ses translat´ ees. Les ing´ enieurs pour leur part se contentent
d’utiliser des tables.
1.5 La cartographie
Comme nous l’avons mentionn´ e dans l’introduction, la cartographie pose des probl` emes non triviaux si l’on veut repr´ esenter fid` element la Terre. En effet, une carte doit
nous servir ` a nous diriger. On pourrait vouloir qu’elle pr´ eserve les distances r´ eelles pour
que, si l’on choisit sur la carte le plus court chemin entre deux points, ce chemin soit
effectivement le plus court. Pour une carte terrestre, ce genre de contrainte a un peu
moins d’importance, car on est soumis `
a la contrainte de demeurer sur une route si
l’on se prom` ene en v´ ehicule motoris´ e. Si l’on se prom` ene ` a pied, les distortions sont
suffisamment petites pour ˆ etre n´ eglig´ ees. Par contre, pour choisir la trajectoire d’un
avion, ou encore, pour un navigateur, le probl` eme est r´ eel. De plus, pour un navigateur
` a la voile qui dispose d’outils rudimentaires, il ne suffit pas de dessiner un chemin sur la
carte. Encore faut-il pouvoir s’y tenir. Jusqu’` a l’arriv´ ee r´ ecente du GPS, il ´ etait courant
de se servir du champ magn´ etique terrestre. En utilisant un compas magn´ etique, on
peut s’assurer que le bateau suive une trajectoire qui fait un angle constant avec les
lignes du champ magn´ etique terrestre. Une telle trajectoire n’est pas n´ ecessairement le
plus court chemin entre deux points, mais, comme c’est une trajectoire naturelle, ce
serait commode qu’une telle trajectoire soit repr´ esent´ ee par une droite sur une carte.
Les cartes marines ont cette propri´ et´ e. Par contre, sur une carte marine, les aires ne
sont pas pr´ eserv´ ees : deux r´ egions du globe qui ont la mˆ eme superficie ne sont pas
n´ ecessairement repr´ esent´ ees sur la carte par des portions de surface de mˆ eme aire.