8.3 G´ en´ erateurs Fp-lin´ eaires
255
D´ efinition 8.5 Un g´ en´ erateur F 2 -lin´ eaire est un g´ en´ erateur de la forme
x n+1 = Ax n ,
y n = x n ,
u n =
k
i=1
y n,i 2
−i ,
o` u A et B sont des matrices ` a coefficients dans F 2 , A est une matrice r × r et B est une
matrice k × r. La matrice A est la matrice de transition pour passer de x n ` a x n+1 , alors
que la matrice B transforme le vecteur x n de longueur r en un vecteur de sortie y n de
longueur k, y n = (y n,1 , . . . , y n,k ), dont les entr´ ees sont les ´ el´ ements du d´ eveloppement
en binaire d’un nombre u n ∈ [0, 1]. La derni` ere ´ etape transforme le vecteur y n en le
nombre u n .
Exemple 8.6 On peut agencer le registre ` a d´ ecalage consid´ er´ e ci-dessus avec un tel
g´ en´ erateur. Pour cela, il faut transformer des sous-suites de longueur k de la suite a n ,
k < r, en ´ el´ ements de [0, 1]. Prendre des sous-suites de longueur k revient `
a prendre la
matrice B dont les k lignes sont les k premi` eres lignes de la matrice identit´ e r × r.
Apr` es application de B, toutes les sous-suites de longueur k deviennent des sorties.
Ainsi,
y n = (x n,0 , . . . , x n,k−1 ) = (a n , . . . , a n+k−1 ).
Revenons ` a l’exemple 8.4, soit le registre `
a d´ ecalage de quatre cases, de coefficients
(q 0 , q 1 , q 2 , q 3 ) = (1, 1, 0, 0), et dot´ e des conditions initiales (a 0 , a 1 , a 2 , a 3 ) = (0, 0, 0, 1),
qui g´ en` ere la suite 000100110101111 . . . de p´ eriode 15, et prenons k = 2. Alors, les
sorties seront les sous-suites (a n , a n+1 ) de longueur 2 r´ ep´ et´ ees selon une une p´ eriode de
15, soit
00 00 01 10 00 01 11 10 01 10 01 11 11 11 10.
On peut maintenant transformer chacune de ces sous-suites de longueur 2, (y n,1 , y n,2 ),
en un nombre u n ∈ {0,
1
4 ,
1
2 ,
3
4 } tel que u n =
yn,1
2 +
yn,2
4 . Ceci nous donne la suite de
p´ eriode 15 u 0 , . . . , u 14 :
0 0
1
4
1
2
0
1
4
3
4
1
2
1
4
1
2
1
4
3
4
3
4
3
4
1
2
.
Tout ´ el´ ement de {0,
1
4 ,
1
2 ,
3
4 } apparaˆ ıt quatre fois sauf 0 qui apparaˆ ıt trois fois.
La grande particularit´ e des g´ en´ erateurs F 2 -lin´ eaires est qu’ils sont tr` es ´ economiques.
Par contre, si on veut am´ eliorer leurs propri´ et´ es statistiques, il faut allonger la p´ eriode,
ce qui leur fait perdre leur avantage ´ economique. Dans ce cas, on peut faire mieux.
Nous allons commencer par ´ etudier en d´ etail les g´ en´ erateurs F 2 -lin´ eaires pour ensuite les
g´ en´ eraliser aux g´ en´ erateurs F p -lin´ eaires. Ensuite, plutˆ ot que de prendre des g´ en´ erateurs
255
D´ efinition 8.5 Un g´ en´ erateur F 2 -lin´ eaire est un g´ en´ erateur de la forme
x n+1 = Ax n ,
y n = x n ,
u n =
k
i=1
y n,i 2
−i ,
o` u A et B sont des matrices ` a coefficients dans F 2 , A est une matrice r × r et B est une
matrice k × r. La matrice A est la matrice de transition pour passer de x n ` a x n+1 , alors
que la matrice B transforme le vecteur x n de longueur r en un vecteur de sortie y n de
longueur k, y n = (y n,1 , . . . , y n,k ), dont les entr´ ees sont les ´ el´ ements du d´ eveloppement
en binaire d’un nombre u n ∈ [0, 1]. La derni` ere ´ etape transforme le vecteur y n en le
nombre u n .
Exemple 8.6 On peut agencer le registre ` a d´ ecalage consid´ er´ e ci-dessus avec un tel
g´ en´ erateur. Pour cela, il faut transformer des sous-suites de longueur k de la suite a n ,
k < r, en ´ el´ ements de [0, 1]. Prendre des sous-suites de longueur k revient `
a prendre la
matrice B dont les k lignes sont les k premi` eres lignes de la matrice identit´ e r × r.
Apr` es application de B, toutes les sous-suites de longueur k deviennent des sorties.
Ainsi,
y n = (x n,0 , . . . , x n,k−1 ) = (a n , . . . , a n+k−1 ).
Revenons ` a l’exemple 8.4, soit le registre `
a d´ ecalage de quatre cases, de coefficients
(q 0 , q 1 , q 2 , q 3 ) = (1, 1, 0, 0), et dot´ e des conditions initiales (a 0 , a 1 , a 2 , a 3 ) = (0, 0, 0, 1),
qui g´ en` ere la suite 000100110101111 . . . de p´ eriode 15, et prenons k = 2. Alors, les
sorties seront les sous-suites (a n , a n+1 ) de longueur 2 r´ ep´ et´ ees selon une une p´ eriode de
15, soit
00 00 01 10 00 01 11 10 01 10 01 11 11 11 10.
On peut maintenant transformer chacune de ces sous-suites de longueur 2, (y n,1 , y n,2 ),
en un nombre u n ∈ {0,
1
4 ,
1
2 ,
3
4 } tel que u n =
yn,1
2 +
yn,2
4 . Ceci nous donne la suite de
p´ eriode 15 u 0 , . . . , u 14 :
0 0
1
4
1
2
0
1
4
3
4
1
2
1
4
1
2
1
4
3
4
3
4
3
4
1
2
.
Tout ´ el´ ement de {0,
1
4 ,
1
2 ,
3
4 } apparaˆ ıt quatre fois sauf 0 qui apparaˆ ıt trois fois.
La grande particularit´ e des g´ en´ erateurs F 2 -lin´ eaires est qu’ils sont tr` es ´ economiques.
Par contre, si on veut am´ eliorer leurs propri´ et´ es statistiques, il faut allonger la p´ eriode,
ce qui leur fait perdre leur avantage ´ economique. Dans ce cas, on peut faire mieux.
Nous allons commencer par ´ etudier en d´ etail les g´ en´ erateurs F 2 -lin´ eaires pour ensuite les
g´ en´ eraliser aux g´ en´ erateurs F p -lin´ eaires. Ensuite, plutˆ ot que de prendre des g´ en´ erateurs