LFSR / Champ de Galois / Sommation dans GF2

[invite5fbf8bef]

Bonjour,

Je regardais en ce moment la théorie des LFSR (registres à décalage à rétroaction) ici http://iml.univ-mrs.fr/~rodier/Cours/LFSR.pdf
À la 23e page du document, on parle d'une sommation, ayant la forme de



Ils donnent un exemple pour un LFSR ayant une valeur de départ égale à 1001001001 donc et ayant un polynôme 1 + X + X^3 + X^4 + X^7 + X^10
Le résultat de l'opération de sommation avec ces paramètres donne le polynôme 1 + X + X^7

Voilà... je ne comprends pas. Ça semble bête, très bête, mais je me demandais si quelqu'un pourrais se donner la peine de faire le calcul parce que franchement...

Pour la sommation

Par exemple pour une table , j'ai, si je comprend bien
i
0 0
1 0
2 0
3 1
4 0
5 0
6 0
7 0
8 0
9 1

Donc si on fait l'addition de cn - isi, je n'obtiendrai jamais X^1... Contrairement à leur réponse.
Quelqu'un étant familier avec les LFSR pourrais m'expliquer... désolé si c'est idiot.

Merci
Yannick
-----

[albanxiii]

Bonjour,

L'expression "champ de Galois" est une mauvaise traduction de l'anglais. En français il s'agit ici du corps .

Si vous avez compris le fonctionnement d'un LFSR (au coup d'horloge, on décale toutes les cases et le contenu de chacune est égale à la somme modulo 2 de ses entrées) et n'avez pas oublié qu'on travaille avec l'addition modulo 2 (0+0=0 ; 1+0=0+1=1 ; 1+1=0 ; les seuls chiffres que vous avez le droit d'écrire sont 0 et 1), il faut juste prendre le temps de faire un exemple à la main, cela ne pose pas de problème.

@+

[invite4842e1dc]

Bonjour

je ne connaissais pas cette notion LFSR

En lisant le polycopié, que tu as joint dans ton message, il est"évident" que quand tu écris dans ton message

une valeur de départ égale à 1001001001 donc et ayant un polynôme 1 + X + X^3 + X^4 + X^7 + X^10

tu expliques très mal ou tu as oublié de préciser une donnée importante dans ta question...

Es tu d'accord avec moi ? que dans l'exemple dans le polycopié on a :

sinon

Ensuite
Il faut remarquer que donc la suite est périodique

Ensuite
Il faut faire beaucoup de calculs pour vérifier ce que tu cherches à vérifier :

c'est à dire à vérifier A LA MAIN que le polynôme vérifie la formule :



ps1)
A mon avis ce qu'il faut comprendre/retenir ce ne sont pas les formules
c'est plutôt que :
et sont des polynômes de F2[] tels que


ps2)
Si tu veux vérifier des formules en faisant des calculs "à la main" : prends un exemple plus simple

[invite5fbf8bef]

Merci pour votre aide mais... vous ne répondez pas vraiment à la question en fait.
Je vais vous expliquer le motif de mon désarroi..

Il y a aussi une raison pour laquelle je veux comprendre la formule, elle me sera utile plus tard dans la recherche assitée par ordinateur d'un polynôme.
Mais je suis juste frustré de ne pas arriver au même résultat également, et pour moi c'est bien suffisant.

Avec l'exemple donné
Était initial : 1001001001
Polynôme : 1011001001
si+L-1 est à gauche, si à droite (toujours, si j'ai bien compris)...
Donc, j'en conclus que l'état initial vas de s0 (à droite) à s9 (à gauche).
Les coefficients "c" sont numérotés dans le sens inverse, soit c1 à gauche et c10 à droite.


Voilà donc...
Si je fais une liste des i x si
j'ai

i isi
0 0
1 0
2 0
3 1
4 0
5 0
6 0
7 0
8 0
9 1

Maintenant, pour cn - isi...
Pour n = 0 ---> c0 je suppose est toujours équivalent à 1, il correspond au +1 que l'on ajoute lorsqu'on détermine le polynôme f(X), et donc cela donne 1 - 0 = 1
Pour n = 1 ---> c1 = 1, donc... la sommation va de i = 0 à i = 1, donc deux sommes... c1 - isi quand i = 0 donne 1 - 0 = 1 et quand i = 1, c1 - isi donne 1 - 0 = 1, donc la sommation 1 + 1 = 0, et on a 0 x X^1

Le résultat ne concorde donc pas et le désespoir refait surface. Je m'arrête donc à n = 1 puisque dès lors j'obtiens des résultats différents.
Deuxièmement, j'utilise cet exemple parce que c'est le seul que j'ai vu dont j'ai la réponse.

Si vous pouviez m'aider, s'il vous plaît, je vous en serais très reconnaissant.

Yannick

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

Je me demande si vous ne faites pas une confusion, la formule est :

[Médiat]

Je précise que je trouve bien

[invite5fbf8bef]

Bonjour,


Je me demande si vous ne faites pas une confusion, la formule est :

Effectivement, j'ai mal lu... ahh j'en suis gêné. Merci de tout coeur, j'arrive bien a la valeur attendue cette fois.