Re: Polynôme générateur

Bonsoir Thomas,

Grâce à la réponse d'Emile, nous avons un développement prestigieux de
votre part, étayée avec un argumentaire que l'on ne trouvera nulle
part. Merci pour tout votre temps, il nous est très utile. Il est rare
de converser de la sorte.

> On peut imaginer dire que "G est un polyn�me g�n�rateur" mais c'est un
> abus de langage, le terme technique correct �tant "primitif".

Mon domaine est plutôt le transport des signaux télécoms. Le polynôme
pris pour exemple dans cette étude concerne l'Ethernet classique
100Base-TX à 100 Mbit/s. Le LFSR fait partie d'un embrouilleur dont le
rôle est de répartir uniformément l'énergie sur le spectre bande de
base du signal, lequel avec le codage de canal 4B/5B s'étage de 0 à
125 MHz environ.

Sans embrouillage, des raies spectrales apparaîtraient (notamment vers
31,25 MHz) et concentreraient l'énergie au point de créer une
pollution électromagnétique sur les paires de câbles avoisinantes. Le
100Base-TX utilise 2 paires torsadées sur un câble qui en comporte 4,
les 2 autres sont inutilisées. Dans les 2 paires utilisées, l'une est
spécifique à l'émission, l'autre à la réception.

Si la diaphonie de la paire émission était trop importante, le bruit
engendré sur la paire réception gênerait le décodage du signal,
produisant un taux d'erreur important, prohibitif.

L'embrouillage avec le polynôme de degré 11 (technologie de 1990 issue
de FDDI et reprise par l'IEEE), ceci avant émission, a pour but
d'éviter cette diaphonie inter-paire. C'est son rôle pour le 100Base-
TX.

Dans d'autres circonstances, pour d'autres technologies, les
embrouilleurs ont d'autres intérêts, comme assurer le transport du
rythme du signal, éviter la reproduction de mots de contrôles,
faciliter la décorrélation de signaux en les embrouillant
différemment. Nous sommes donc dans des utilisations autres que la
cryptologie, mais avec des théories similaires.

Une question, est-il facile en observant la structure f(X) d'un
polynôme, de déterminer s'il est primitif ou pas ? Ou, alors, le seul
moyen est de pouvoir recourir au polynôme g(X) déterminé par l'état
initial du registre, et diviser g(X) par f(X) pour savoir si le
rapport peut etre réduit.

D'après ce que vous avez écrit, on aurait f(X) = X^11 + X^9  + X^8 +
X^5 + X^4 + X^2 + X + 1 polynôme primitif. Est-ce visible au 1er coup
d'oeil ?



Puis-je vous entraîner un peu sur le dispositif d'embrouillage,
construit à partir du LFSR. Pour fixer les idées, prenons le LSFR
générique d'équation : s(i+L) = c(1) s(i+L-1) + .... + c(L-1) s(i+1) +
c(L) s(i).

Sur ce LFSR on ouvre la connexion s(i+L) qui sort du XOR pour
retourner à l'entrée de la cellule D dont la sortie est s(i+L-1).

La sortie du XOR rendue libre, est alors reliée à un nouvel XOR qui
reçoit sur une autre entrée les données d'information Ye(i) à
embrouiller. Le XOR de ces 2 entrées est, d'une part, reconnecté à
l'entrée de la cellule D et, d'autre part, à la sortie de
l'embrouilleur qui fournit les iinformations embrouillées Ys(i).

Pour le polynôme de degré 11 que nous connaissons f(X) = 1 + X^9 +
X^11, l'équation de l'embrouilleur est : Ys(i) = Ye(i) + Ys(i-9) +
Ys(i-11).

On a presque envie d'écrire que l'embrouilleur réalise une division,
du style :

Ys(X) = g(X) / f(X) + Ye(X) avec g(X) le polynôme d'état initial
(introduit précédemment) et f(X) le polynôme primitif. Mais je ne sais
pas du tout si cela est exact.

Je voudrais refaire jaillir le fonctionnement du LFSR au travers de
l'embrouilleur. Mais l'information d'entrée Ye, quelconque, casse la
périodicité du LFSR.

Merci pour votre avis,
cordialement,
Michelot