Introduction
Cette page peut se résumer en une phrase : pour convertir le polynôme d’un LFSR de la forme de Galois vers la forme de Fibonacci, il suffit d’inverser l’ordre des coefficients.
Par exemple, voici le schéma du LFSR souvent utilisé dans les brouilleurs (scramblers) :
Chaque bloc marqué d’un D représente un délai d’un cycle d’horloge. La représentation de ce LFSR sous forme de polynôme de Galois est :
G(x) = x16 + x5 + x4 + x3 + 1
Notons que les exposants du polynôme (3, 4 et 5) correspondent au nombre d’éléments de délai situés à gauche de chaque XOR.
Le même LFSR peut être implémenté sous la forme de Fibonacci, comme le montre ce schéma :
Malgré la ressemblance entre ces deux schémas, le sens des flèches est inversé. Les implémentations des LFSR sont complètement différentes.
Le polynôme de Fibonacci (ou polynôme de rétroaction) est le suivant :
F(x) = x16 + x13 + x12 + x11 + 1
Le degré du polynôme est n=16, si bien que chaque xi dans G(x) est représenté dans F(x) par xn-i. La suite de cette page montre que cela n’a rien d’une coïncidence.
Pour une explication générale sur les LFSR, reportez-vous à la page Wikipedia consacrée à ce sujet.
LFSR et filtres numériques
La théorie des filtres numériques (par exemple les filtres à réponse impulsionnelle finie, ou FIR, et les filtres à réponse impulsionnelle infinie, ou IIR) est habituellement appliquée sur le corps des nombres complexes. Rien n’empêche cependant de l’appliquer sur GF(2), c’est-à-dire le corps fini (corps de Galois) qui ne contient que deux nombres : 0 et 1. Quelques remarques s’imposent :
- L’opérateur d’addition dans ce corps équivaut à un XOR.
- Toutes les multiplications ne font intervenir que des nombres entiers. En fait, multiplier par un nombre pair équivaut à multiplier par 0. De même, multiplier par un nombre impair équivaut à multiplier par 1. Peu importe que le nombre soit positif ou négatif.
- Grâce à cette règle de multiplication, l’addition et la soustraction reviennent au même. L’une comme l’autre peut être remplacée par ⊕ (qui représente le XOR).
La théorie de base des filtres numériques exige seulement que le système soit un système linéaire invariant dans le temps (LTI). Un LFSR satisfait à ces exigences, car le XOR est linéaire et le comportement d’un LFSR est invariant dans le temps.
La conséquence la plus intéressante est que la transformée en z peut être utilisée pour analyser les LFSR. Par exemple, considérons ce schéma :
Cela peut être décrit par l’équation suivante :
y(t) = x(t) ⊕ x(t-1)
t est un nombre entier qui représente le temps.
On peut traiter cela comme un filtre FIR et écrire la transformée en z de cette équation :
Y(z) = X(z) + X(z)z-1 = X(z) (1 + z-1)
La « réponse impulsionnelle » peut alors se définir comme d’habitude : H(z) = Y(z)/X(z), ou plus simplement :
H(z) = 1 + z-1
Mais que se passe-t-il si l’on met deux de ces filtres l’un derrière l’autre ? Quelle est la « réponse impulsionnelle » de cet ensemble ?
La théorie des filtres numériques donne une réponse simple :
H2(z) = H(z)H(z) = (1 + z-1)(1 + z-1) = 1 + 2z-1 + z-2
Rappelons que dans GF(2), multiplier par un nombre pair revient à multiplier par zéro. Par conséquent :
H2(z) = 1 + 2z-1 + z-2 = 1 + 0z-1 + z-2 = 1 + z-2
ce qui correspond à ceci :
Il n’est pas évident de voir que les filtres représentés sur les deux derniers schémas sont équivalents. Pourtant, les deux filtres produisent le même y(t) lorsqu’on leur applique le même x(t). Les filtres sont donc identiques, même si les valeurs stockées dans le deuxième élément de délai ne sont pas les mêmes.
Cet exemple met en évidence l’intérêt de la transformée en z (et des techniques similaires utilisant des polynômes) pour analyser des filtres logiques.
Je devrais mentionner que les symboles D ou D-1 sont souvent utilisés à la place de z-1. En fait, l’emploi de x dans les polynômes de Galois et de Fibonacci a la même signification que z-1. Tous ces symboles représentent un délai.
Le LFSR de Galois
Pour trouver la représentation de Fibonacci, je vais commencer par examiner le LFSR de Galois.
Reprenons le schéma du LFSR de Galois ci-dessus. La rangée d’éléments de délai avec ses sorties intermédiaires peut être vue comme un filtre FIR, que je noterai A(z). Le LFSR de Galois est donc équivalent à ceci :
À cause de la rétroaction, l’équation pour Y(z) est :
Y(z) = Y(z)A(z)
Quel est alors le lien entre les paramètres de ce FIR et le polynôme de Galois ? Écrivons la forme générale du polynôme de Galois :
G(x) = xn + gn-1xn-1+ gn-2xn-2+…+ g0
Notons que gn n’apparaît pas dans cette expression, afin de simplifier les calculs plus bas. De plus, gn vaut toujours 1.
La relation entre G(x) et A(z) est la suivante :
A(z) = gn-1z-1+gn-2z-2+…+g1z1-n+g0z-n
Pourquoi est-ce exact ? Prenons le LFSR de Galois du schéma ci-dessus et montrons comment cette expression fonctionne.
Commençons par regarder le XOR qui correspond à g5. Le nombre 5 signifie qu’il y a cinq éléments de délai sur le côté gauche de ce XOR. Mais l’exposant de z dépend du nombre d’éléments de délai entre le XOR et la sortie du FIR. Ce sont les éléments de délai sur le côté droit du XOR. Il y a 16 éléments de délai au total. Par conséquent, g5 apparaît dans A(z) comme g5z-11. Cela correspond à la structure gn-iz-i.
Une autre façon de l’expliquer est de considérer A(z) comme un FIR dans le domaine temporel. L’entrée de ce FIR est x(t) et sa sortie est y(t) :
y(t) = x(t–16) ⊕ x(t–13) ⊕ x(t–12) ⊕ x(t–11)
Encore une fois, t est un entier qui représente le temps. Cette expression représente le LFSR de Galois sans la rétroaction. La fonction de transfert de ce FIR est :
A(z) = Y(z)/X(z) = z-16 + z-13 + z-12 + z-11
C’est cohérent avec l’expression générale de A(z) pour G(x) = x16 + x5 + x4 + x3 + 1.
L’équivalent de Fibonacci
Un LFSR sous forme de Fibonacci est représenté par le polynôme suivant :
F(x) = fnxn+fn-1xn-1+…+f1x + 1
Notons que f0 n’apparaît pas dans ce polynôme car il vaut toujours 1. C’est analogue à gn qui n’apparaît pas dans G(x).
L’implémentation de ce polynôme est :
y(t) = f1y(t-1) + f2y(t-2) +…+ fny(t-n)
La transformée en z correspondante est :
Y(z) = f1Y(z)z-1+f2Y(z)z-2+…+fnY(z)z-n
Définissons B(z) comme suit :
B(z) = f1z-1+f2z-2+…+fnz-n
Y(z) peut donc s’écrire :
Y(z) = Y(z)B(z)
On rappelle ci-dessus que Y(z) = Y(z)A(z). Par conséquent, si la forme de Fibonacci du LFSR se comporte comme le LFSR donné par le polynôme de Galois, il s’ensuit que A(z) = B(z), ce qui signifie aussi que :
fi=gn-i (i=1,2, … , n)
Donc, comme je l’ai dit dès le début : pour convertir le polynôme d’un LFSR de la forme de Galois vers la forme de Fibonacci, il suffit d’inverser l’ordre des coefficients.
Le filtre inverse du LFSR
Voici de nouveau l’implémentation de Fibonacci du LFSR :
y(t) = f1y(t-1) + f2y(t-2) +…+ fny(t-n)
mais cette expression peut aussi se réécrire comme suit :
y(t) + f1y(t-1) + f2y(t-2) +…+ fny(t-n) = 0
(rappelez-vous que + et – sont identiques dans GF(2))
Les coefficients du polynôme de Fibonacci indiquent donc aussi comment effectuer un XOR sur les valeurs de y(t-i) pour obtenir toujours la valeur zéro. Autrement dit, cela décrit un FIR intéressant.
La transformée en z de la dernière expression est :
Y(z) + f1Y(z)z-1+f2Y(z)z-2+…+fnY(z)z-n = 0
ou, de manière équivalente :
Y(z)(1+ f1z-1+f2z-2+…+fnz-n) = Y(z)H(z) = 0
Y(z)H(z) est la sortie obtenue lorsqu’on applique le filtre H(z) à Y(z). Et cette sortie est nulle.
H(z) est donc la fonction de transfert d’un filtre FIR. Si l’on applique à l’entrée de ce FIR la sortie du LFSR défini par F(x), sa sortie sera nulle en permanence. D’après la définition de B(z) plus haut, la fonction de transfert de ce FIR est la suivante :
H(z) = 1 + f1z-1+f2z-2+…+fnz-n
Ou, dans le domaine temporel, si l’entrée est x(t) et la sortie est y(t) :
y(t) = x(t) ⊕ f1x(t-1) ⊕ f2x(t-2) ⊕ … ⊕ fnx(t-n)
Si x(t) est la sortie du LFSR défini par F(x), alors y(t) est nul pour tout t.