Re: Polynôme générateur

Bonjour Emile,

Merci pour ces commentaires

> > En quoi pourrait-on dire que G(x) = 1 + X^9 + X^11 est un polynôme
> > générateur ?
>
> 2^11-1 = 2047 n'est pas un nombre premier. Il n'est donc pas possible
> de réaliser un LFSR avec ce polynôme. Ceci répond-il à ta question?

Ce polynôme est normalisé dans IEEE 802.3, il constitue le LFSR
utilisé pour l'embrouillage de l'Ethernet 100Base-TX.

Ma petite étude a conduit à cela :

(1) Tout polynôme élément de F2[X], de degré L, est associable à un
LFSR constitué de L cellules

(2) La qualité du LFSR revient à observer la période de la séquence
binaire qu'il génère (lorsqu'il tourne sur lui-même, sans être associé
à un embrouilleur par exemple), et donc d'observer la propriété du
polynôme

(3) Une première condition de qualité est obtenue lorsque le polynôme
G(X) associé est irréductible. On aurait par exemple la même suite
binaire avec G(X) = X^10 + X^7 + X^4 + X^3 + X + 1 non irréductible
qu'avec X^3 + 1 irréductible, diviseur du précédent. Le second LFSR
permet d'économiser 7 cellules par rapport au premier.

(3) Une seconde condition concerne la longueur (ou durée) de la
période. Celle-ci est maximale, égale à T = 2^L - 1, si le polynôme
irréductible est en plus primitif, c'est à dire s'il divise (1 + X^T),
avec T valeur minimum possible.

Par exemple G(X) = X^4 + X^3 + X^2 + X + 1 est irréductible, il divise
(1 + X^15) mais aussi (1 + X^5), la période de la séquence binaire
n'est donc pas 15 mais T = 5.

Je note ce que Thomas nous apprend (...ou réapprend) : il n'est pas
gagné qu'un polynôme irréductible de degré 4 soit aussi primitif, car
(2^4 - 1) = 3 x 5.

Voilà ma vision de cet instant, écrite en termes simples (du moins je
le suppose).

Merci pour vos commentaires ou vos corrections,
Michelot