|
==Registres à décalage à rétroaction==
La première solution consiste à utiliser des registres à décalages à rétroaction, aussi appelés Feedback Shift Registers, abréviés LSFR. Ce genre de circuit donne un résultat assez proche de l'aléatoire., Maismais on peut cependant remarquer qu'il ne s'agit pas de « vrai » aléatoire. C'estEn effet, un faittel circuit est déterministe : onpour peutle prédiremême résultat en entrée, il donnera toujours le même résultat en sortie. De plus, ce quicompteur vane sortirpeut d'uncompter que de ces<math>0</math> registresà <math>2^n – 1</math>. EnLors effetde son fonctionnement, le compteur finira donc par repasser par une valeur qu'il existeaura undéjà parcourue, vu que le nombre de valeurs possibles est fini. Une fois qu'il repassera par cette valeur, son fonctionnement se reproduira à l'identique comparé à son passage antérieur. Un LSFR ne produit donc pas de « théorèmevrai » quialéatoire, nous ditvu que la sortie d'un tel registre finit par faire des cycles. MaisCeci ildit, nsi la période d'yun acycle pasest besoinassez grande, son contenu semblera varier de sortirmanière touttotalement unaléatoire, théorèmetant pourqu'on comprendrene pourquoiregarde unpas teldurant circuitlongtemps. finitIl fatalements'agit pard'une seapproximation de l'aléatoire particulièrement répéterbonne.
La période N dépend fortement de la fonction utilisée pour calculer le bit de sortie, des bits choisis, etc. Dans le meilleur des cas, le registre à décalage à rétroaction passera par presque toutes les valeurs que le registre peut prendre. Si je dis presque toutes, c'est simplement qu'une valeur n'est pas possible : suivant le registre, le zéro ou sa valeur maximale sont interdits. Si un registre à rétroaction linéaire passe par zéro (ou sa valeur maximale), il y reste bloqué définitivement. La raison à cela est simple : un XOR sur des zéro donnera toujours 0. Le même raisonnement peut être tenu pour les registres à rétroaction affine, sauf que cette fois-ci, le raisonnement ne marche qu'avec la valeur maximale stockable dans le registre. Tout le chalenge consiste donc à trouver quels sont les registres à rétroaction dont la période est maximale : ceux dont la période vaut <math>2^n - 1</math>. Qu'on se rassure, quelle que soit la longueur du registre, il en existe au moins un : cela se prouve mathématiquement, même si nous ne vous donnerons pas la démonstration.
On remarque qu'un tel circuit est déterministe : pour le même résultat en entrée, il donnera toujours le même résultat en sortie. De plus, notre circuit est un registre de n bits : il peut donc compter de 0 à (2^n) – 1. Lors de son fonctionnement, notre circuit finira donc par repasser par une valeur qu'il aura déjà parcourue, vu que le nombre de valeurs possible est fini. Une fois qu'il repassera par cette valeur, son fonctionnement se reproduira à l'identique comparé à son passage antérieur, vu que le circuit est déterministe.
====Combinaisons = de LSFR=== ▼Un tel registre finit donc par faire des cycles : tous les N cycles d'horloges, il effectuera un cycle. Ceci dit, si ce nombre N de cycle (sa période) est assez grand, le circuit donnera l'illusion de l'aléatoire. Son contenu semblera varier de manière totalement aléatoire, tant qu'on ne regarde pas durant longtemps. Il s'agit d'une approximation de l'aléatoire particulièrement bonne.
AutreSi solutionles :LSFR prendresont plusieurstrès intéressants, diverses techniques permettent d'améliorer le fonctionnement de ces registres à décalages à rétroaction . linéairesPar etexemple, on peut décider d'utiliser leursdes LSFR plus compliqués, non linéaires. La fonction appliquée au bit sur l'entrée est alors plus complexe, mais le jeu en vaut la chandelle. Cependant, les techniques les plus efficaces consistent à combiner plusieurs LSFR pour obtenir une meilleure approximation de résultatsl'aléatoire. Avec cette technique, plusieurs registres à décalages à rétroaction sont reliés à un circuit combinatoire non-linéaire. Ce circuit prendra en entrée un (ou plusieurs) bit de chaque registre à décalage à rétroaction, et combinera ces bits pour fournir un bit de sortie. Un circuit conçu avec ce genre de méthode va fournir un bit à la fois. Les bits en sortie de ce circuit seront alors accumulés dans un registre à décalage normal, pour former un nombre aléatoire. ▼La période N dépend fortement de la fonction utilisée pour calculer le bit de sortie, des bits choisis, etc. Dans le meilleur des cas, le registre à décalage à rétroaction passera par presque toutes les (2n)
Problème : ces circuits ne sont pas totalement fiables. Ils peuvent produire plus de bits à 0 que de bits à 1, et des corrections sont nécessaires. Pour cela, ces circuits de production de nombres aléatoires sont souvent couplés à des circuits qui corrigent le flux de bits accumulé dans le registre pour l'aléatoiriser. Une solution consiste à simplement prendre plusieurs de ces circuits, et d'appliquer un XOR sur les bits fournis par ces circuits : on obtient alors un bit un peu moins biaisé, qu'on peut envoyer dans notre registre à décalage . Il faut noter que seule une faible partie des bits de chaque registre à décalage est prise en compte par notre circuit combinatoire. Pratiquement, des circuits avec trop de bits en entrées sont difficilement concevables. ▼valeurs que le registre peut prendre.
Si je dis presque toutes, c'est simplement qu'une valeur n'est pas possible : suivant le registre, le zéro ou sa valeur maximale sont interdits. Si un registre à rétroaction linéaire passe par zéro (ou sa valeur maximale), il y reste bloqué définitivement. Cela vient du fait que x∗An+Y∗An−1+…+Z∗a0
donne toujours zéro. Le même raisonnement peut être tenu pour les registres à rétroaction affine, sauf que cette fois-ci, le raisonnement ne marche qu'avec la valeur maximale stockable dans le registre.
Tout le chalenge consiste donc à trouver quels sont les registres à rétroaction dont la période est maximale : ceux dont la période vaut (2n)–1
. Qu'on se rassure, quelle que soit la longueur du registre, il en existe au moins un : cela se prouve mathématiquement.
Et d'ailleurs, je ne résiste pas à vous donner quels bits choisir pour obtenir cette période maximale en fonction du nombre total de bits. Voici cette liste, pour des registres à décalage affines :
Bits Bits à choisir Période
2 2,1 3
3 3,2 7
4 4,3 15
5 5,3 31
6 6,5 63
7 7,6 127
8 8, 6, 5, 4 255
9 9,5 511
10 10,7 1023
Les plus curieux pourront compléter cette liste en allant regarder ce lien.
===Variations sur les registres à décalage à rétroaction===
Nos registres à décalage à rétroaction affine sont très intéressants. Mais un registre à décalage à rétroaction affine ou linéaire n'est pas forcément très fiable. Trouver des moyens plus efficaces pour produire des suites de nombres proches de l'aléatoire est parfois une nécessité. Aussi, diverses techniques permettent d'améliorer le fonctionnement de ces registres à décalages à rétroaction.
Registres à décalages à rétroaction non-affine
Il n'y a pas vraiment de raisons de changer une équipe qui gagne. Nos registres à décalages à rétroaction sont facilement prédictibles à cause de leur circuit combinatoire, qui calcule le bit à faire rentrer dans le registre : ce circuit est linéaire, ou affine. Pour rendre celui-ci plus imprévisible, on peut décider d'utiliser des circuits plus compliqués, non linéaires. La fonction appliquée au bit sur l'entrée est alors plus complexe, mais le jeu en vaut la chandelle.
▲Autre solution : prendre plusieurs registres à décalages à rétroaction linéaires et utiliser leurs résultats. Avec cette technique, plusieurs registres à décalages à rétroaction sont reliés à un circuit combinatoire non-linéaire. Ce circuit prendra en entrée un (ou plusieurs) bit de chaque registre à décalage à rétroaction, et combinera ces bits pour fournir un bit de sortie. Un circuit conçu avec ce genre de méthode va fournir un bit à la fois. Les bits en sortie de ce circuit seront alors accumulés dans un registre à décalage normal, pour former un nombre aléatoire.
▲Problème : ces circuits ne sont pas totalement fiables. Ils peuvent produire plus de bits à 0 que de bits à 1, et des corrections sont nécessaires. Pour cela, ces circuits de production de nombres aléatoires sont souvent couplés à des circuits qui corrigent le flux de bits accumulé dans le registre pour l'aléatoiriser. Une solution consiste à simplement prendre plusieurs de ces circuits, et d'appliquer un XOR sur les bits fournis par ces circuits : on obtient alors un bit un peu moins biaisé, qu'on peut envoyer dans notre registre à décalage.
Il faut noter que seule une faible partie des bits de chaque registre à décalage est prise en compte par notre circuit combinatoire. Pratiquement, des circuits avec trop de bits en entrées sont difficilement concevables.
Une variante de cette technique consiste à prendre la totalité des bits d'un registre à décalage à rétroaction linéaire (ou affine), et à envoyer ces bits dans un circuit non-linéaire. La différence, c'est que dans ce cas, tous les bits du registre sont pris en compte.
|
