20
1 Positionnement
• On d´ ecale chacune des entr´ ees vers la droite en oubliant le a n−r . Le a n calcul´ e
occupe donc la case de gauche.
• On it` ere le proc´ ed´ e.
Comme le proc´ ed´ e est parfaitement d´ eterministe et que le nombre de conditions initiales
est fini, on g´ en` ere une suite qui va devenir p´ eriodique et on voit tout de suite que sa
p´ eriode est inf´ erieure ou ´ egale `
a 2
r , car on a au maximum 2
r suites distinctes de longueur
r. En fait, on peut se convaincre que, si ` a un moment donn´ e, on a a n−r = · · · = a n−1 = 0,
alors, pour tout m ≥ n, on a a m = 0. Donc, une suite p´ eriodique int´ eressante ne
doit jamais contenir une suite cons´ ecutive de r z´ eros. Par suite, elle aura une p´ eriode
maximale de 2
r
− 1. Pour g´ en´ erer une suite qui ait des propri´ et´ es int´ eressantes, il suffit
de bien choisir les q 0 , . . . , q r−1 ∈ {0, 1} et les conditions initiales a 0 , . . . , a r−1 ∈ {0, 1}.
Nous ne regardons jamais toute la suite, mais une fenˆ etre de M = 2
r
− 1 nombres
cons´ ecutifs {a n }
n=m+M−1
n=m
, que nous pouvons appeler B = {b 1 , . . . , b M }. Nous voulons
la comparer avec une autre fenˆ etre C = {c 1 , . . . , c M } de la forme {a n }
n=p+M−1
n=p
. Par
exemple, la suite B est envoy´ ee par le satellite, et la suite C est une permutation cyclique
de la mˆ eme suite g´ en´ er´ ee par le r´ ecepteur. Pour d´ eterminer le d´ ecalage entre les deux,
le r´ ecepteur translate (d´ ecale) d’une entr´ ee la suite qu’il g´ en` ere (en faisant p → p + 1)
de mani` ere r´ ep´ et´ ee jusqu’` a ce qu’elle soit identique `
a B.
D´ efinition 1.2 On appellera corr´ elation entre les deux suites B et C de longueur M
le nombre d’entr´ ees i o` u b i = c i moins le nombre d’entr´ ees i o` u b i = c i . On la notera
Cor(B, C).
Remarque Si le registre est constitu´ e de r-tuples, alors la corr´ elation de toute paire
de suites B et C satisfait −M ≤ Cor(B, C) ≤ +M avec M = 2
r
− 1. Nous dirons que
les suites sont mal corr´ el´ ees si Cor(B, C) est proche de 0.
Proposition 1.3 La corr´ elation entre les deux suites est donn´ ee par
Cor(B, C) =
M
i=1
(−1)
bi (−1)
ci .
(1.25)
Preuve Le nombre Cor(B, C) est calcul´ e ainsi : chaque fois que b i = c i , on doit
additionner 1. Chaque fois que b i = c i , on doit soustraire 1. Rappelons que les b i et
c i ne prennent que les valeurs 0 ou 1. Si b i = c i , alors soit (−1)
bi = (−1)
ci = 1, soit
(−1)
bi = (−1)
ci = −1. Dans les deux cas, (−1)
bi (−1)
ci = 1. De mˆ eme, si b i = c i ,
exactement un des nombres (−1)
bi et (−1)
ci est ´ egal `
a 1, et l’autre est ´ egal `
a −1. Donc
(−1)
bi (−1)
ci = −1.
Le th´ eor` eme qui suit montre qu’on peut initialiser un registre `
a d´ ecalage de mani` ere
` a ce qu’il g´ en` ere une suite tr` es mal corr´ el´ ee avec une translation d’elle-mˆ eme.
1 Positionnement
• On d´ ecale chacune des entr´ ees vers la droite en oubliant le a n−r . Le a n calcul´ e
occupe donc la case de gauche.
• On it` ere le proc´ ed´ e.
Comme le proc´ ed´ e est parfaitement d´ eterministe et que le nombre de conditions initiales
est fini, on g´ en` ere une suite qui va devenir p´ eriodique et on voit tout de suite que sa
p´ eriode est inf´ erieure ou ´ egale `
a 2
r , car on a au maximum 2
r suites distinctes de longueur
r. En fait, on peut se convaincre que, si ` a un moment donn´ e, on a a n−r = · · · = a n−1 = 0,
alors, pour tout m ≥ n, on a a m = 0. Donc, une suite p´ eriodique int´ eressante ne
doit jamais contenir une suite cons´ ecutive de r z´ eros. Par suite, elle aura une p´ eriode
maximale de 2
r
− 1. Pour g´ en´ erer une suite qui ait des propri´ et´ es int´ eressantes, il suffit
de bien choisir les q 0 , . . . , q r−1 ∈ {0, 1} et les conditions initiales a 0 , . . . , a r−1 ∈ {0, 1}.
Nous ne regardons jamais toute la suite, mais une fenˆ etre de M = 2
r
− 1 nombres
cons´ ecutifs {a n }
n=m+M−1
n=m
, que nous pouvons appeler B = {b 1 , . . . , b M }. Nous voulons
la comparer avec une autre fenˆ etre C = {c 1 , . . . , c M } de la forme {a n }
n=p+M−1
n=p
. Par
exemple, la suite B est envoy´ ee par le satellite, et la suite C est une permutation cyclique
de la mˆ eme suite g´ en´ er´ ee par le r´ ecepteur. Pour d´ eterminer le d´ ecalage entre les deux,
le r´ ecepteur translate (d´ ecale) d’une entr´ ee la suite qu’il g´ en` ere (en faisant p → p + 1)
de mani` ere r´ ep´ et´ ee jusqu’` a ce qu’elle soit identique `
a B.
D´ efinition 1.2 On appellera corr´ elation entre les deux suites B et C de longueur M
le nombre d’entr´ ees i o` u b i = c i moins le nombre d’entr´ ees i o` u b i = c i . On la notera
Cor(B, C).
Remarque Si le registre est constitu´ e de r-tuples, alors la corr´ elation de toute paire
de suites B et C satisfait −M ≤ Cor(B, C) ≤ +M avec M = 2
r
− 1. Nous dirons que
les suites sont mal corr´ el´ ees si Cor(B, C) est proche de 0.
Proposition 1.3 La corr´ elation entre les deux suites est donn´ ee par
Cor(B, C) =
M
i=1
(−1)
bi (−1)
ci .
(1.25)
Preuve Le nombre Cor(B, C) est calcul´ e ainsi : chaque fois que b i = c i , on doit
additionner 1. Chaque fois que b i = c i , on doit soustraire 1. Rappelons que les b i et
c i ne prennent que les valeurs 0 ou 1. Si b i = c i , alors soit (−1)
bi = (−1)
ci = 1, soit
(−1)
bi = (−1)
ci = −1. Dans les deux cas, (−1)
bi (−1)
ci = 1. De mˆ eme, si b i = c i ,
exactement un des nombres (−1)
bi et (−1)
ci est ´ egal `
a 1, et l’autre est ´ egal `
a −1. Donc
(−1)
bi (−1)
ci = −1.
Le th´ eor` eme qui suit montre qu’on peut initialiser un registre `
a d´ ecalage de mani` ere
` a ce qu’il g´ en` ere une suite tr` es mal corr´ el´ ee avec une translation d’elle-mˆ eme.