1.4 Les registres ` a d´ ecalage
21
Th´ eor` eme 1.4 ´
Etant donn´ e un registre ` a d´ ecalage comme sur la figure 1.5, il existe
des q 0 , . . . , q r−1 ∈ {0, 1} et des conditions initiales a 0 , . . . , a r−1 ∈ {0, 1} tels que la suite
g´ en´ er´ ee par le registre est p´ eriodique de longueur 2
r
− 1. On consid` ere deux fenˆ etres de
cette suite de mˆ eme longueur M = 2
r
−1, soit B = {a n }
n=m+M−1
n=m
et C = {a n }
n=p+M−1
n=p
avec p > m. Si M ne divise pas p − m alors
Cor(B, C) = −1,
(1.26)
c’est-` a-dire que le nombre de bits en d´ esaccord est toujours exactement 1 de plus que le
nombre de bits en accord.
La preuve du th´ eor` eme fait appel aux corps finis. Nous allons donc commencer par
illustrer au moyen d’un exemple la signification du th´ eor` eme. La preuve suivra dans la
section 1.4.2.
Exemple 1.5 Dans notre exemple, r = 4, (q 0 , q 1 , q 2 , q 3 ) = (1, 1, 0, 0) et (a 0 , a 1 , a 2 , a 3 ) =
(0, 0, 0, 1). Nous laissons le lecteur v´ erifier que ceci g´ en` ere une suite p´ eriodique de
p´ eriode 2
4
− 1 = 15 dans laquelle on r´ ep` ete le bloc
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
Si l’on fait une translation de 1, on envoie le premier 0 ` a la fin, ce qui donne le bloc
0 0 1 0 0 1 1 0 1 0 1 1 1 1 0
On voit que les deux suites (blocs) diff` erent aux positions 3, 4, 6, 8, 9, 10, 11, 15, soit en
huit positions et concordent aux sept positions restantes, soit une corr´ elation de −1.
Pour calculer la corr´ elation avec les autres translations, nous allons les ´ ecrire directement en dessous de la premi` ere suite et laisser le lecteur v´ erifier que deux lignes
quelconques diff` erent en exactement huit entr´ ees :
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
0 0 1 0 0 1 1 0 1 0 1 1 1 1 0
0 1 0 0 1 1 0 1 0 1 1 1 1 0 0
1 0 0 1 1 0 1 0 1 1 1 1 0 0 0
0 0 1 1 0 1 0 1 1 1 1 0 0 0 1
0 1 1 0 1 0 1 1 1 1 0 0 0 1 0
1 1 0 1 0 1 1 1 1 0 0 0 1 0 0
1 0 1 0 1 1 1 1 0 0 0 1 0 0 1
0 1 0 1 1 1 1 0 0 0 1 0 0 1 1
1 0 1 1 1 1 0 0 0 1 0 0 1 1 0
0 1 1 1 1 0 0 0 1 0 0 1 1 0 1
1 1 1 1 0 0 0 1 0 0 1 1 0 1 0
1 1 1 0 0 0 1 0 0 1 1 0 1 0 1
1 1 0 0 0 1 0 0 1 1 0 1 0 1 1
1 0 0 0 1 0 0 1 1 0 1 0 1 1 1
21
Th´ eor` eme 1.4 ´
Etant donn´ e un registre ` a d´ ecalage comme sur la figure 1.5, il existe
des q 0 , . . . , q r−1 ∈ {0, 1} et des conditions initiales a 0 , . . . , a r−1 ∈ {0, 1} tels que la suite
g´ en´ er´ ee par le registre est p´ eriodique de longueur 2
r
− 1. On consid` ere deux fenˆ etres de
cette suite de mˆ eme longueur M = 2
r
−1, soit B = {a n }
n=m+M−1
n=m
et C = {a n }
n=p+M−1
n=p
avec p > m. Si M ne divise pas p − m alors
Cor(B, C) = −1,
(1.26)
c’est-` a-dire que le nombre de bits en d´ esaccord est toujours exactement 1 de plus que le
nombre de bits en accord.
La preuve du th´ eor` eme fait appel aux corps finis. Nous allons donc commencer par
illustrer au moyen d’un exemple la signification du th´ eor` eme. La preuve suivra dans la
section 1.4.2.
Exemple 1.5 Dans notre exemple, r = 4, (q 0 , q 1 , q 2 , q 3 ) = (1, 1, 0, 0) et (a 0 , a 1 , a 2 , a 3 ) =
(0, 0, 0, 1). Nous laissons le lecteur v´ erifier que ceci g´ en` ere une suite p´ eriodique de
p´ eriode 2
4
− 1 = 15 dans laquelle on r´ ep` ete le bloc
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
Si l’on fait une translation de 1, on envoie le premier 0 ` a la fin, ce qui donne le bloc
0 0 1 0 0 1 1 0 1 0 1 1 1 1 0
On voit que les deux suites (blocs) diff` erent aux positions 3, 4, 6, 8, 9, 10, 11, 15, soit en
huit positions et concordent aux sept positions restantes, soit une corr´ elation de −1.
Pour calculer la corr´ elation avec les autres translations, nous allons les ´ ecrire directement en dessous de la premi` ere suite et laisser le lecteur v´ erifier que deux lignes
quelconques diff` erent en exactement huit entr´ ees :
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
0 0 1 0 0 1 1 0 1 0 1 1 1 1 0
0 1 0 0 1 1 0 1 0 1 1 1 1 0 0
1 0 0 1 1 0 1 0 1 1 1 1 0 0 0
0 0 1 1 0 1 0 1 1 1 1 0 0 0 1
0 1 1 0 1 0 1 1 1 1 0 0 0 1 0
1 1 0 1 0 1 1 1 1 0 0 0 1 0 0
1 0 1 0 1 1 1 1 0 0 0 1 0 0 1
0 1 0 1 1 1 1 0 0 0 1 0 0 1 1
1 0 1 1 1 1 0 0 0 1 0 0 1 1 0
0 1 1 1 1 0 0 0 1 0 0 1 1 0 1
1 1 1 1 0 0 0 1 0 0 1 1 0 1 0
1 1 1 0 0 0 1 0 0 1 1 0 1 0 1
1 1 0 0 0 1 0 0 1 1 0 1 0 1 1
1 0 0 0 1 0 0 1 1 0 1 0 1 1 1