Comment les LFSR sont-ils utilisés dans des applications réelles en tant que PRNG?

Je programme un LFSR (Linear Feedback Shift Register) dans un logiciel à des fins d'apprentissage et j'ai rencontré certaines limitations dans son utilisation en tant que générateur de nombres pseudo-aléatoires (PRNG).

• Si la graine a peu de bits «1» et que peu de tapotements sont utilisés, elle nécessite un «temps de démarrage» important pour produire une sortie apparemment aléatoire, avec une distribution presque égale entre les «1» et les «0» ou de courts «0». Je suppose qu'avec plus de tapotements, un tel démarrage serait beaucoup plus rapide, mais tous les tableaux précalculés que je trouve donnent deux ou quatre tapotements.
• Les nombres séquentiels sont fortement corrélés, ce qui est normal, étant donné que si le bit de sortie est 0, le nombre suivant sera la moitié du précédent. Pour un LFSR 15 bits avec prises [15, 14], le traçage d'une paire de nombres séquentiels en tant que points dans un plan donne ce qui suit. Un PRNG idéal devrait répartir ces points partout.

Je sais que les LFSR sont utilisés comme compteur matériel rapide, mais j'ai également vu qu'il était utilisé comme PRNG pour créer du bruit blanc. Comment est-il utilisé dans des applications du monde réel avec une si mauvaise qualité?

Une excellente source pour tout ce qui concerne PRNG est "Séquences de registre à décalage" par Solomon Golomb. Il aborde les différentes classes et techniques.

Commencer par réinitialiser tous les registres est un moyen. Ou une charge parallèle d'une graine en est une autre. Mais n'oubliez pas qu'une piqûre de tous les zéros est un état valide.

Le choix des bons codes est important car tous les paramètres de rétroaction sur un registre à décalage ne garantissent pas d'obtenir une séquence PRNG maximale.

La façon dont vous utilisez un PRNG affecte ses performances.

Pour un registre de 15 bits et la recherche des codes, [15,4] est maximal tel quel [15,1] mais [15,14] n'est pas répertorié. -> Source - "Systèmes et applications à spectre étalé" - Robert Dixon 3e éd. Pg 94. Ce livre est une très bonne référence sur la mise en œuvre.

En général, les LFSR font des PRNG pauvres et la pratique générale consiste à n'utiliser que les bits inférieurs. Alternativement, vous pouvez générer deux PRNG de longueurs et codes différents et xor les bits inférieurs pour générer le nouveau code. Il faut probablement utiliser moins de la moitié de la longueur de bit. Donc un registre de longueur de 30 et 31 bits et XOR les 15 LSB.

Le NIST a un excellent code de test ici . Alors oui, ça craint, pour les PRNG.

Les nombres séquentiels sont fortement corrélés, ce qui est normal, étant donné que si le bit de sortie est 0, le nombre suivant sera la moitié du précédent. Pour un LFSR 15 bits avec prises [15, 14], le traçage d'une paire de nombres séquentiels en tant que points dans un plan donne ce qui suit. Un PRNG idéal devrait répartir ces points partout.

Si vous souhaitez générer des nombres aléatoires avec un LFSR 15 bits, vous ne tirez pas un nouveau nombre aléatoire à chaque cycle d'horloge. Comme vous l'avez dit puisque vous n'ajoutez qu'un nouveau bit au registre à chaque cycle d'horloge, la valeur en cycle Net N+1sera très fortement corrélée. Si vous souhaitez générer des valeurs aléatoires (en supposant que vous avez des prises appropriées), vous devez uniquement extraire une nouvelle valeur toutes les 15 horloges.

Un LFSR ne vous garantit qu'un bit aléatoire à chaque cycle, pas 15 bits aléatoires.

Un exemple réel peut être trouvé dans le manuel de référence de la famille de microprocesseurs RISC MPC7450. Le 7450 a utilisé un pRNG pour le remplacement de L2 et L3 qui est composé de 16 verrous ayant trois registres à décalage simples avec les bits 0 à 4, les bits 5 à 9 et les bits 10 à 15. Le bit 0 provient d'un XOR de bits 4 et 15, le bit 5 provient d'un XOR des bits 4 et 9, et le bit 10 provient d'un XOR des bits 6 et 15. La voie de remplacement dans les caches à 8 voies est indiquée par les bits 4, 9 et 15 pour L2 et par les bits 0 , 5 et 10 pour L3. Les bits étaient décalés à chaque cycle, mais il est évident que les remplacements de cache ne se produisaient pas aussi fréquemment. (Un autre mécanisme de remplacement basé sur des compteurs a également été fourni.)

Cela a été reconnu comme potentiellement problématique:

En raison de la latence de la recherche de cache L2, il y a 3 cycles d'horloge entre un échec de lecture et l'allocation de la ligne de remplacement. Ainsi, il serait possible que la même voie puisse être choisie pour le remplacement de deux, voire trois ratés de lecture consécutifs avec l'algorithme tel que décrit ci-dessus. Afin d'éviter cela, l'algorithme réel compare une ligne de remplacement sélectionnée avec les trois lignes de remplacement précédentes. Si la ligne sélectionnée correspond à l'une des trois précédentes, une valeur de un, deux ou trois est automatiquement ajoutée à la valeur qui sélectionne le chemin de remplacement.