26
1 Positionnement
T (x
r b) = T ((q r−1 x
r−1 + · · · + q 1 x + q 0 )b)
= q r−1 T (x
r−1 b) + · · · + q 1 T (xb) + q 0 T (b)
= q r−1 a r−1 + · · · + q 1 a 1 + q 0 a 0
= a r .
(1.34)
Supposons maintenant, par induction, que les ´ el´ ements de la suite g´ en´ er´ ee v´ erifient tous
a i = T (x
i b) pour i ≤ n − 1. Alors :
T (x
n b) = T (x
r x
n−r b) = T ((q r−1 x
r−1 + · · · + q 1 x + q 0 )x
n−r b)
= q r−1 T (x
n−1 b) + · · · + q 1 T (x
n−r+1 b) + q 0 T (x
n−r b)
= q r−1 a n−1 + · · · + q 1 a n−r+1 + q 0 a n−r
= a n .
(1.35)
Donc, la multiplication par x correspond exactement ` a l’action du registre ` a d´ ecalage.
On voit que la suite est p´ eriodique de p´ eriode 2
r
− 1 puisque x
2
r −1 = 1.
On peut se demander quelle est la p´ eriode minimale de cette suite. A priori, ce
pourrait ˆ etre un diviseur de 2
r
− 1 (voir exercice 11). En fait, nous allons montrer que,
si P est primitif, la p´ eriode minimale est exactement 2
r
− 1. La preuve sera indirecte.
Si la p´ eriode ´ etait donn´ ee par s ∈ N tel que 2
r
− 1 = sm et 1 < s < 2
r
− 1, alors la
suite infinie {a n } n≥0 et la suite {a n+s } n≥0 devraient ˆ etre identiques. Nous montrerons
qu’il n’en est rien. N’oublions pas que nous voulons g´ en´ erer des suites qui sont tr` es mal
corr´ el´ ees avec une translation d’elles mˆ emes. Nous allons donc calculer en mˆ eme temps
la corr´ elation entre deux fenˆ etres B = {a n }
n=m+M−1
n=m
et C = {a n }
n=p+M−1
n=p
de longueur
M = 2
r
− 1.
Proposition 1.13 Si B = {a n }
n=m+M−1
n=m
et C = {a n }
n=p+M−1
n=p
, alors Cor(B, C) =
−1 si M ne divise pas p − m.
Preuve On peut supposer m ≤ p.
Cor(B, C) =
M−1
i=0 (−1)
am+i (−1)
ap+i
=
M−1
i=0 (−1)
T (x
m+i b) (−1)
T (x
p+i b)
=
M−1
i=0 (−1)
T (x
m+i b)+T (x
p+i b)
=
M−1
i=0 (−1)
T (x
m+i b+x
p+i b)
=
M−1
i=0 (−1)
T (bx
i+m (1+x
p−m ))
=
M−1
i=0 (−1)
T (x
i+m β) ,
(1.36)
o` u β = b(1 + x
p−m ). On sait que, dans notre corps, x est une racine primitive et donc,
que x
M = 1 et x
N
= 1 si 1 ≤ N < M. On en d´ eduit que x
N = 1 si et seulement si M
divise N . Si M divise p − m, alors x
p−m = 1 et β = b(1 + 1) = b · 0 = 0. Dans ce cas,
Cor(B, C) = M . Si M ne divise pas p−m, le polynˆ ome (1+x
p−m ) n’est pas le polynˆ ome
nul ; ainsi β = b(1 + x
p−m ) est non nul comme ´ el´ ement de F 2 r , puisqu’il est le produit
1 Positionnement
T (x
r b) = T ((q r−1 x
r−1 + · · · + q 1 x + q 0 )b)
= q r−1 T (x
r−1 b) + · · · + q 1 T (xb) + q 0 T (b)
= q r−1 a r−1 + · · · + q 1 a 1 + q 0 a 0
= a r .
(1.34)
Supposons maintenant, par induction, que les ´ el´ ements de la suite g´ en´ er´ ee v´ erifient tous
a i = T (x
i b) pour i ≤ n − 1. Alors :
T (x
n b) = T (x
r x
n−r b) = T ((q r−1 x
r−1 + · · · + q 1 x + q 0 )x
n−r b)
= q r−1 T (x
n−1 b) + · · · + q 1 T (x
n−r+1 b) + q 0 T (x
n−r b)
= q r−1 a n−1 + · · · + q 1 a n−r+1 + q 0 a n−r
= a n .
(1.35)
Donc, la multiplication par x correspond exactement ` a l’action du registre ` a d´ ecalage.
On voit que la suite est p´ eriodique de p´ eriode 2
r
− 1 puisque x
2
r −1 = 1.
On peut se demander quelle est la p´ eriode minimale de cette suite. A priori, ce
pourrait ˆ etre un diviseur de 2
r
− 1 (voir exercice 11). En fait, nous allons montrer que,
si P est primitif, la p´ eriode minimale est exactement 2
r
− 1. La preuve sera indirecte.
Si la p´ eriode ´ etait donn´ ee par s ∈ N tel que 2
r
− 1 = sm et 1 < s < 2
r
− 1, alors la
suite infinie {a n } n≥0 et la suite {a n+s } n≥0 devraient ˆ etre identiques. Nous montrerons
qu’il n’en est rien. N’oublions pas que nous voulons g´ en´ erer des suites qui sont tr` es mal
corr´ el´ ees avec une translation d’elles mˆ emes. Nous allons donc calculer en mˆ eme temps
la corr´ elation entre deux fenˆ etres B = {a n }
n=m+M−1
n=m
et C = {a n }
n=p+M−1
n=p
de longueur
M = 2
r
− 1.
Proposition 1.13 Si B = {a n }
n=m+M−1
n=m
et C = {a n }
n=p+M−1
n=p
, alors Cor(B, C) =
−1 si M ne divise pas p − m.
Preuve On peut supposer m ≤ p.
Cor(B, C) =
M−1
i=0 (−1)
am+i (−1)
ap+i
=
M−1
i=0 (−1)
T (x
m+i b) (−1)
T (x
p+i b)
=
M−1
i=0 (−1)
T (x
m+i b)+T (x
p+i b)
=
M−1
i=0 (−1)
T (x
m+i b+x
p+i b)
=
M−1
i=0 (−1)
T (bx
i+m (1+x
p−m ))
=
M−1
i=0 (−1)
T (x
i+m β) ,
(1.36)
o` u β = b(1 + x
p−m ). On sait que, dans notre corps, x est une racine primitive et donc,
que x
M = 1 et x
N
= 1 si 1 ≤ N < M. On en d´ eduit que x
N = 1 si et seulement si M
divise N . Si M divise p − m, alors x
p−m = 1 et β = b(1 + 1) = b · 0 = 0. Dans ce cas,
Cor(B, C) = M . Si M ne divise pas p−m, le polynˆ ome (1+x
p−m ) n’est pas le polynˆ ome
nul ; ainsi β = b(1 + x
p−m ) est non nul comme ´ el´ ement de F 2 r , puisqu’il est le produit