Discussion :

[Array]

Bonjour,

Je m'intéresse à la théorie qui entoure les registres à rétroaction linéaire, afin de construire un générateur de nombres pseudo aléatoires.

Je lisais donc ce http://iml.univ-mrs.fr/~rodier/Cours/LFSR.pdf en ligne.

Je pourrais avoir plusieurs questions sur le sujet... je vais commencer par la première : la représentation d'un LFSR dans une matrice...

À la 20ème page du PDF on dit qu'il est possible de déclarer une matrice A tel que R(i+1) = AR(i)

J'ai de la difficulté à comprendre comment on construit cette matrice... Je veux dire... chaque colonne de la matrice A représente quoi? Les R(i) successifs ou autre chose?

Si quelqu'un pourrait me donner un exemple avec un LFSR de 4 bits par exemple...

Vraiment merci pour l'aide

Array

[pseudocode]

À la 20ème page du PDF on dit qu'il est possible de déclarer une matrice A tel que R(i+1) = AR(i)

J'ai de la difficulté à comprendre comment on construit cette matrice... Je veux dire... chaque colonne de la matrice A représente quoi? Les R(i) successifs ou autre chose?

Il s'agit de calculer R(i+1) à partir de R(i) en utilisant un produit matriciel.

Si R(i) = {a,b,c,d}
et R(i+1) = {b,c,a+d,0} (décalage à gauche, et ajout du bit sortant en 3ème pos)

| b |   |0 1 0 0|   |a|
| c |   |0 0 1 0|   |b|
|a+d| = |1 0 0 1| * |c|
| e |   |0 0 0 0|   |d|

[Array]

Wow... je ne comprend pas pourquoi je n'avais pas compris ce bout.
Néanmoins c'est maintenant clair à mes yeux.

Mais une question s'impose à moi...
Si cL = 1, alors le lfsr ne passera pas par 0. À la page 20 du document en question, ils disent que le le déterminant de la matrice sera égal à cL... jusque là je comprend. Ensuite si le déterminant est non-nul, alors la matrice est réversible, ce que je sais aussi. en suivant les propriétés des déterminants.

Cependant, en quoi le fait que la matrice soit réversible empêche d'obtenir un LFSR nul?

Merci,
Array

[pseudocode]

Wow... je ne comprend pas pourquoi je n'avais pas compris ce bout.
Néanmoins c'est maintenant clair à mes yeux.

Mais une question s'impose à moi...
Si cL = 1, alors le lfsr ne passera pas par 0. À la page 20 du document en question, ils disent que le le déterminant de la matrice sera égal à cL... jusque là je comprend. Ensuite si le déterminant est non-nul, alors la matrice est réversible, ce que je sais aussi. en suivant les propriétés des déterminants.

Cependant, en quoi le fait que la matrice soit réversible empêche d'obtenir un LFSR nul?

Merci,
Array

Si le déterminant est non-nul, alors le noyau de la matrice (ker) est réduit à {0}.

=> le seul élément X tel que M.X=0, c'est X=0.
=> le seul élément X tel que M.(M.X)=0, c'est X=0
=> le seul élément X tel que M.(M.(M.X))=0, c'est X=0.
...

[Array]

Y a-t-il une preuve à ceci (i.e. si la matrice est inversible alors la seule possibilité pour la rendre nulle par multiple est X=0)?

[pseudocode]

Y a-t-il une preuve à ceci (i.e. si la matrice est inversible alors la seule possibilité pour la rendre nulle par multiple est X=0)?

Bah, heu... c'est la caractérisation des matrices inversibles.

• det(M)<>0 <==> M inversible
• det(M)<>0 <==> l'équation M.X=0 admet une unique solution

Et, trivialement,

• X=0 est solution de l'équation M.X=0

[Array]

Merci beaucoup pour l'aide pseudo.
J'aurais deux autres questions...

La première, à la page 18 on parle de série génératrice...
sigma[n >= 0](snX^n) associée à la suite (sn)n >= 0
Qu'est-ce que cela veut dire? (je suis au lycée, dsl)

Une deuxième question, p. 18:
"Son polynôme de rétroaction f est le polynôme de F2[X]"
Qu'est-ce que F2[X] désigne??!

Merci!
P.S. Si c'est trop long ou trop poussé pour expliquer, auriez-vous de la doc?

EDIT: En passant je connais le rôle de sigma, l'opérateur de sommation et tout mais... j'ai de la difficulté à comprendre ce qu'il veut dire par (sn)n et qu'est-ce que X dans snX^n??? Voilà... je voulais préciser