1.4 Les registres ` a d´ ecalage
19
1.4 Les registres ` a d´ ecalage et le signal du GPS
Les registres ` a d´ ecalage permettent de g´ en´ erer des s´ equences de caract` eres qui
ont d’excellentes propri´ et´ es pour synchroniser l’´ ecoute d’un r´ ecepteur. Ces appareils
simples ` a bricoler (on pourrait en fabriquer un avec des composantes ´ electriques simples)
g´ en` erent un signal pseudo-al´ eatoire, c’est-` a-dire un signal qui a l’air al´ eatoire mˆ eme s’il
est g´ en´ er´ e par un algorithme d´ eterministe.
On va construire un registre ` a d´ ecalage qui g´ en` ere un signal p´ eriodique de longueur
2
r
− 1. Il aura la propri´ et´ e d’ˆ etre tr` es mal corr´ el´ e avec toute translation de lui-mˆ eme et
avec un autre signal p´ eriodique produit par le mˆ eme registre ` a d´ ecalage avec d’autres
coefficients. Cette propri´ et´ e d’avoir une s´ equence mal corr´ el´ ee avec ses translat´ ees ou
avec un autre signal engendr´ e ` a partir de param` etres diff´ erents permet entre autres
au r´ ecepteur GPS d’identifier sans risque d’erreur le satellite dont il re¸ coit le signal et
de mesurer le temps de parcours du signal du satellite en se synchronisant au signal
re¸ cu du satellite. Le signal produit par un registre `
a d´ ecalage est une suite de 0 et
de 1. Le registre ` a d´ ecalage est donn´ e par un ruban de r cases contenant des entr´ ees
a n−1 , . . . , a n−r , lesquelles sont des 0 ou des 1 (figure 1.5). `
A chaque case est associ´ ee un
Fig. 1.5. Un registre `
a d´ ecalage
nombre q i ∈ {0, 1}. Ces r nombres q i sont fix´ es et sont propres ` a un satellite donn´ e. On
g´ en` ere une suite pseudo-al´ eatoire de la fa¸ con suivante :
• On se donne des nombres initiaux a 0 , . . . , a r−1 ∈ {0, 1} non tous nuls.
• ´
Etant donn´ e a n−r , . . . , a n−1 , le registre calcule l’´ el´ ement suivant dans la suite
comme suit
a n ≡ a n−r q 0 + a n−r+1 q 1 + · · · + a n−1 q r−1 =
r−1
i=0
a n−r+i q i (mod 2).
(1.24)
(Pour calculer modulo 2, on fait le calcul habituel. Le r´ esultat est 0 si le nombre
est pair et 1 s’il est impair. On ´ ecrit a ≡ 0 (mod 2) si a est pair et a ≡ 1 (mod 2)
si a est impair.)
19
1.4 Les registres ` a d´ ecalage et le signal du GPS
Les registres ` a d´ ecalage permettent de g´ en´ erer des s´ equences de caract` eres qui
ont d’excellentes propri´ et´ es pour synchroniser l’´ ecoute d’un r´ ecepteur. Ces appareils
simples ` a bricoler (on pourrait en fabriquer un avec des composantes ´ electriques simples)
g´ en` erent un signal pseudo-al´ eatoire, c’est-` a-dire un signal qui a l’air al´ eatoire mˆ eme s’il
est g´ en´ er´ e par un algorithme d´ eterministe.
On va construire un registre ` a d´ ecalage qui g´ en` ere un signal p´ eriodique de longueur
2
r
− 1. Il aura la propri´ et´ e d’ˆ etre tr` es mal corr´ el´ e avec toute translation de lui-mˆ eme et
avec un autre signal p´ eriodique produit par le mˆ eme registre ` a d´ ecalage avec d’autres
coefficients. Cette propri´ et´ e d’avoir une s´ equence mal corr´ el´ ee avec ses translat´ ees ou
avec un autre signal engendr´ e ` a partir de param` etres diff´ erents permet entre autres
au r´ ecepteur GPS d’identifier sans risque d’erreur le satellite dont il re¸ coit le signal et
de mesurer le temps de parcours du signal du satellite en se synchronisant au signal
re¸ cu du satellite. Le signal produit par un registre `
a d´ ecalage est une suite de 0 et
de 1. Le registre ` a d´ ecalage est donn´ e par un ruban de r cases contenant des entr´ ees
a n−1 , . . . , a n−r , lesquelles sont des 0 ou des 1 (figure 1.5). `
A chaque case est associ´ ee un
Fig. 1.5. Un registre `
a d´ ecalage
nombre q i ∈ {0, 1}. Ces r nombres q i sont fix´ es et sont propres ` a un satellite donn´ e. On
g´ en` ere une suite pseudo-al´ eatoire de la fa¸ con suivante :
• On se donne des nombres initiaux a 0 , . . . , a r−1 ∈ {0, 1} non tous nuls.
• ´
Etant donn´ e a n−r , . . . , a n−1 , le registre calcule l’´ el´ ement suivant dans la suite
comme suit
a n ≡ a n−r q 0 + a n−r+1 q 1 + · · · + a n−1 q r−1 =
r−1
i=0
a n−r+i q i (mod 2).
(1.24)
(Pour calculer modulo 2, on fait le calcul habituel. Le r´ esultat est 0 si le nombre
est pair et 1 s’il est impair. On ´ ecrit a ≡ 0 (mod 2) si a est pair et a ≡ 1 (mod 2)
si a est impair.)