Niveau autre

MLS, polynomes irréductibles, séquence pseudo-aléatoire

Posté par
erio 29-05-09 à 15:39

Bonjour,

Je m'intéresse aux séquences MLS (Maximum Length Sequence), et à leur relation avec les corps finis, plus particulièrement $\mathbb{F}_2$ .

Voici les liens sur lequel je me suis basé :

... bien maigre pour l'instant

J'ai 2 questions :
1/ ... d'ordre général : quelqu'un connaitrait-il par hasard une référence mathématique sur le sujet?

2/ Dans les articles que j'ai mis en liens, on considère un polynome irréductible sur $\mathbb{F}_2$ , de degré n : $P(X) = X^n+\sum_{i=0}^{n-1}a_i X^i$ , qui permet donc via le passage au quotient de construire $\mathbb{F}_{2^n}$ .
Dans les articles sur les MLS, il est indiqué que si l'on se donne alors une amorce :
$(u_0,u_1,...,u_{n-1})$
il est possible de construire par la récurrence :
$u_{n+k} = \sum_{i=0}^{n-1}a_i u_{i+k}$
une séquence de période $2^n-1$ telle qu'on ne trouve qu'une fois chaque séquence consécutive de n termes, plus d'autres propriétés d'autocorrélation, etc...
Je vois bien le rapport avec la cyclicité et le cardinal de $\mathbb{F}_{2^n}^\times$ , et que d'une façon ou d'une autre on génère par cette méthode tous les éléments du groupe multiplicatif, mais je ne vois pas comment le montrer.

D'avance merci de votre aide

Posté par re : MLS, polynomes irréductibles, séquence pseudo-aléatoire 29-05-09 à 15:41

Précision : les $u_n$ sont dans $\mathbb{F}_2$

Posté par re : MLS, polynomes irréductibles, séquence pseudo-aléatoire 01-06-09 à 16:03

Visiblement, ma question a un succès inespéré

En fouillant un peu, j'ai trouvé une explication. Je ne suis pas sûr que ce soit la plus immédiate :
Au départ je croyais que la façon de partir était de considérer $(u_0,u_1,...,u_{n-1})$ comme les coordonnées d'un élément de $\mathbb{F}_{2^n}^\times$ , mais les calculs ne correspondaient pas.
En fait, j'ai trouvé la solution en considérant $(u_0,u_1,...,u_{n-1})$ comme l'image par une forme linéaire f non nulle des vecteurs de base $(1,X,...,X^{n-1})$ . Pour que l'image soit la même que celle des vecteurs $(X^k,X^{k+1},...,X^{k+n-1})$ , il faut que f s'annule sur $(X^k-1,(X^k-1)X,...,(X^k-1)X^{n-1})$ qui est une base ssi $X^k-1 \neq 0$ ssi k n'est pas un multiple de $2^n-1$ ... In fine, la période minimale de f est bien $2^n-1$ .

Merci pour vos nombreuses réponses

Il ne reste plus qu'à m'attaquer à la corrélation...

Ce topic

Imprimer
Réduire / Agrandir
Pour plus d'options, connectez vous !
Fiches de maths

algèbre en post-bac
28 fiches de mathématiques sur "algèbre" en post-bac disponibles.

Rechercher

Espace membre

Zone membre

Pas de compte ?
Je m'inscris

Changer d'île

Cours et Exercices de maths

Forum de maths

college

lycee

Outils de maths

Pages les plus populaires

MLS, polynomes irréductibles, séquence pseudo-aléatoire

Seuls les membres peuvent poster sur le forum !

Ce topic

Fiches de maths