« Fonctionnement d'un ordinateur/Les circuits de génération d'aléatoire » : différence entre les versions

 

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, mais on peut cependant remarquer qu'il ne s'agit pas de vrai aléatoire. En effet, 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, ce compteur ne peut compter que de <math>0</math> à <math>2^n - 1</math>. Lors de son fonctionnement, le compteur finira donc par repasser par une valeur qu'il aura dé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 « vrai » aléatoire, vu que la sortie d'un tel registre finit par faire des cycles. Ceci dit, si la période d'un cycle est assez grande, 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.

 

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.