8.2 Le registre ` a d´ ecalage
253
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
00 0100110101111
0
00 100110101111
0001
00 110101111,
et les trois autres, soit 01, 10 et 11, sont sorties exactement quatre fois. Dans le cas de
la sous-suite 10, la quatri` eme occurrence est `
a cheval sur deux p´ eriodes :
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
000
10 0110101111
0001001
10 101111
000100110
10 1111
00010011010111
1 0 001 . . .
De mˆ eme, nous laissons le lecteur v´ erifier que chaque sous-suite de trois symboles est
sortie deux fois sauf 000 qui n’est sortie qu’une fois. Quant aux sous-suites de quatre
symboles, elles sont toutes sorties exactement une fois sauf 0000. Pouvons-nous continuer avec des sous-suites de cinq symboles ? Non, notre registre n’a que quatre cases, si
bien que chaque fois que les quatre premiers symboles sont d´ etermin´ es, le cinqui` eme et
les suivants le sont aussi. Nous pouvons aussi expliquer pourquoi les sous-suites n’ayant
que des 0 apparaissent moins souvent : nous ne pouvons nous permettre d’avoir une
sous-suite de la forme 0000 parce que la r` egle de fonctionnement du registre `
a d´ ecalage
forcerait tous les symboles suivants de la suite `
a ˆ etre des z´ eros.
Cet exemple montre que ce registre a de bonnes propri´ et´ es statistiques tant qu’on ne
consid` ere pas des sous-suites trop longues (ici, on se limite `
a des sous-suites de quatre
symboles). Ceci n’est pas un hasard, et nous le montrerons plus bas au th´ eor` eme 8.13.
Si l’on veut pouvoir b´ en´ eficier des bonnes propri´ et´ es de ce type de registre pour des
sous-suites plus longues, il faudra prendre un nombre r de cases assez grand.
Nous allons d´ ecrire le fonctionnement du registre `
a d´ ecalage sous une autre forme
qui se prˆ etera ` a des g´ en´ eralisations. `
A un instant donn´ e, que l’on appellera l’instant
j, les entr´ ees dans les cases sont a j , . . . , a j+r−1 . R´ e´ ecrivons ces entr´ ees sous la forme
x j,0 , . . . , x j,r−1 , o` u x j,i = a i+j . L’avantage de cette ´ ecriture est que l’indice j indique
l’instant et l’indice i, la case o` u se trouve le symbole. Appelons x j le vecteur-colonne
dont les entr´ ees sont x j,0 , . . . , x j,r−1 , c’est-` a-dire les symboles apparaissant dans les cases
` a l’instant j. Soit A la matrice
A =
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
0 1 0 0 . . .
0
0 0 1 0 . . .
0
0 0 0 1 . . .
0
. . .
. . .
. . .
. . .
. . .
. . .
0 0 0 0 . . .
1
q 0 q 1 q 2 q 3 . . . q r−1
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
(8.3)
253
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
00 0100110101111
0
00 100110101111
0001
00 110101111,
et les trois autres, soit 01, 10 et 11, sont sorties exactement quatre fois. Dans le cas de
la sous-suite 10, la quatri` eme occurrence est `
a cheval sur deux p´ eriodes :
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
000
10 0110101111
0001001
10 101111
000100110
10 1111
00010011010111
1 0 001 . . .
De mˆ eme, nous laissons le lecteur v´ erifier que chaque sous-suite de trois symboles est
sortie deux fois sauf 000 qui n’est sortie qu’une fois. Quant aux sous-suites de quatre
symboles, elles sont toutes sorties exactement une fois sauf 0000. Pouvons-nous continuer avec des sous-suites de cinq symboles ? Non, notre registre n’a que quatre cases, si
bien que chaque fois que les quatre premiers symboles sont d´ etermin´ es, le cinqui` eme et
les suivants le sont aussi. Nous pouvons aussi expliquer pourquoi les sous-suites n’ayant
que des 0 apparaissent moins souvent : nous ne pouvons nous permettre d’avoir une
sous-suite de la forme 0000 parce que la r` egle de fonctionnement du registre `
a d´ ecalage
forcerait tous les symboles suivants de la suite `
a ˆ etre des z´ eros.
Cet exemple montre que ce registre a de bonnes propri´ et´ es statistiques tant qu’on ne
consid` ere pas des sous-suites trop longues (ici, on se limite `
a des sous-suites de quatre
symboles). Ceci n’est pas un hasard, et nous le montrerons plus bas au th´ eor` eme 8.13.
Si l’on veut pouvoir b´ en´ eficier des bonnes propri´ et´ es de ce type de registre pour des
sous-suites plus longues, il faudra prendre un nombre r de cases assez grand.
Nous allons d´ ecrire le fonctionnement du registre `
a d´ ecalage sous une autre forme
qui se prˆ etera ` a des g´ en´ eralisations. `
A un instant donn´ e, que l’on appellera l’instant
j, les entr´ ees dans les cases sont a j , . . . , a j+r−1 . R´ e´ ecrivons ces entr´ ees sous la forme
x j,0 , . . . , x j,r−1 , o` u x j,i = a i+j . L’avantage de cette ´ ecriture est que l’indice j indique
l’instant et l’indice i, la case o` u se trouve le symbole. Appelons x j le vecteur-colonne
dont les entr´ ees sont x j,0 , . . . , x j,r−1 , c’est-` a-dire les symboles apparaissant dans les cases
` a l’instant j. Soit A la matrice
A =
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
0 1 0 0 . . .
0
0 0 1 0 . . .
0
0 0 0 1 . . .
0
. . .
. . .
. . .
. . .
. . .
. . .
0 0 0 0 . . .
1
q 0 q 1 q 2 q 3 . . . q r−1
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
(8.3)