Wie werden LFSRs in realen Anwendungen als PRNGs verwendet?

8

Ich programmiere ein LFSR (Linear Feedback Shift Register) in Software für Lernzwecke und habe einige Einschränkungen bei der Verwendung als Pseudozufallszahlengenerator (PRNG) festgestellt.

  • Wenn der Startwert nur wenige '1'-Bits hat und nur wenige Abgriffe verwendet werden, ist eine große "Startzeit" erforderlich, um eine scheinbar zufällige Ausgabe mit nahezu gleicher Verteilung zwischen' 1 'und' 0 'oder kurzen' 0 'zu erzeugen. Ich denke, mit mehr Taps wäre ein solcher Start viel schneller, aber alle vorberechneten Tabellen, die ich finde, geben zwei oder vier Taps.
  • Folgenummern sind stark korreliert, was zu erwarten ist, da bei einem Ausgangsbit von 0 die nächste Nummer die Hälfte der vorherigen ist. Für ein 15-Bit-LFSR mit Abgriffen [15, 14] ergibt das Zeichnen eines Paares von fortlaufenden Zahlen als Punkte in einer Ebene Folgendes. Ein idealer PRNG sollte diese Punkte überall verteilen.

Bild

Ich weiß, dass LFSRs als schneller Hardwarezähler verwendet werden, aber ich habe auch gesehen, dass sie als PRNG verwendet werden, um weißes Rauschen zu erzeugen. Wie wird es in solchen realen Anwendungen mit solch schlechter Qualität verwendet?

Bruno Kim
quelle
Wie @rawbrawb hervorhebt, eignen sich LFSRs nicht sehr gut zum Generieren von Pseudozufallszahlen. Wenn Sie nur einen Teil des Inhalts des Schieberegisters (z. B. 16 niedrigstwertige Bits in einem LFSR mit einer Länge von 32 Bit) als Zufallszahl verwenden, sind die Dinge viel schlimmer. Weitere Informationen hierzu finden Sie in den letzten Fragen und Antworten zu crypto.SE.
Dilip Sarwate

Antworten:

4

Eine ausgezeichnete Quelle für PRNG ist "Shift Register Sequences" von Solomon Golomb. Es werden die verschiedenen Klassen und Techniken erörtert.

Das Zurücksetzen aller Register ist eine Möglichkeit. Oder eine parallele Ladung eines Samens ist eine andere. Denken Sie jedoch daran, dass ein Stich aller Nullen ein gültiger Zustand ist.

Die Auswahl der richtigen Codes ist wichtig, da nicht jede Rückkopplungseinstellung in einem Schieberegister sicherstellt, dass Sie eine maximale PRNG-Sequenz erhalten.

Wie Sie ein PRNG betreiben, wirkt sich auf dessen Leistung aus.

Für ein 15-Bit-Register und das Nachschlagen der Codes ist [15,4] wie [15,1] maximal, aber [15,14] ist nicht aufgeführt. -> Quelle - "Spread Spectrum Systeme und Anwendungen" - Robert Dixon 3rd Ed. S. 94. Dieses Buch ist eine sehr gute Referenz zur Implementierung.

Im Allgemeinen machen LFSRs schlechte PRNGs und die allgemeine Praxis besteht darin, nur die unteren Bits zu verwenden. Alternativ können Sie zwei PRNGs mit unterschiedlichen Längen und Codes generieren und die unteren Bits xor, um den neuen Code zu generieren. Wahrscheinlich sollte weniger als die Hälfte der Bitlänge verwendet werden. Also ein 30 und 31 Bit Längenregister und XOR die 15 LSBs.

NIST hat ausgezeichneten Testcode hier . Also ja, es ist scheiße für PRNGs.

Platzhalter
quelle
Wenn Sie die Menge der Hähne [nbits, a, b, c], einen anderen Satz, der maximal ist [nbits, nbits-a, nbits-b, nbits-c]. Auf diese Weise sind sowohl [15,14] als auch [15,1] maximal.
Bruno Kim
Abhängig von Ihrem Register-Setup ist entweder All-Zero oder All-One ungültig. In den meisten Sachen, die ich mache, ist all-zero ungültig, aber Sie haben es oben als gültig notiert und wollten sicherstellen, dass dies dort rausgeworfen wurde. ;)
Aaron D. Marasco
Es wurden Details hinzugefügt, wie eine bessere Leistung erzielt werden kann. Aber das macht es nicht gut. Ich habe diese in SSDS verwendet - die selbstkorrelierende Natur. Ich hatte Duals vergessen.
Platzhalter
Interessante Idee, XOR verschiedene LFSRs, aber ich denke, die Zahlen würden immer noch korreliert. Wahrscheinlich ist es besser, Tims Antwort zu verwenden und einen vollständigen Zyklus durchzuführen, bevor Sie eine andere Nummer auswählen.
Bruno Kim
@BrunoKim es ist nicht original, es ist rechen- oder bereichseffizienter. Die Wiederholungslänge wäre ebenfalls 2 ^ 30.
Platzhalter
7

Folgenummern sind stark korreliert, was zu erwarten ist, da bei einem Ausgangsbit von 0 die nächste Nummer die Hälfte der vorherigen ist. Für ein 15-Bit-LFSR mit Abgriffen [15, 14] ergibt das Zeichnen eines Paares von fortlaufenden Zahlen als Punkte in einer Ebene Folgendes. Ein idealer PRNG sollte diese Punkte überall verteilen.

Wenn Sie Zufallszahlen mit einem 15-Bit-LFSR generieren möchten, ziehen Sie nicht bei jedem Taktzyklus eine neue Zufallszahl. Wie Sie sagten, da Sie pro Registerzyklus nur ein neues Bit zum Register hinzufügen, ist der Wert im Zyklus Nund N+1sehr stark korreliert. Wenn Sie zufällige Werte generieren möchten (vorausgesetzt, Sie haben die richtigen Abgriffe), müssen Sie nur alle 15 Takte einen neuen Wert ziehen.

Ein LFSR garantiert Ihnen nur ein Zufallsbit pro Zyklus, nicht 15 Zufallsbits.

Tim
quelle
1
Ich codiere für beliebige Bitnummern. Wenn ich eine zufällige Ganzzahl (64 Bit) möchte, sollte ich im Allgemeinen ein 128-Bit-LFSR (gemäß dem Vorschlag von rawbrawb) verwenden und 64 Iterationen durchführen, bevor ich eine Zahl auswähle. Würde nicht eine Nummer übersehen werden und andere öfter als erwartet für eine "gleichmäßige" Verteilung ausgewählt?
Bruno Kim
2

Ein Beispiel aus der Praxis finden Sie im Referenzhandbuch zur RISC-Mikroprozessorfamilie MPC7450. Der 7450 verwendete ein pRNG für das Ersetzen von L2 und L3, das aus 16 Latches mit drei einfachen Schieberegistern mit den Bits 0 bis 4, den Bits 5 bis 9 und den Bits 10 bis 15 besteht. Bit 0 stammt aus einem XOR der Bits 4 und 15. Bit 5 kommt von einem XOR der Bits 4 und 9, und Bit 10 kommt von einem XOR der Bits 6 und 15. Der Ersetzungsweg in den 8-Wege-Caches wird durch die Bits 4, 9 und 15 für L2 und durch die Bits 0 angezeigt , 5 und 10 für L3. Die Bits wurden in jedem Zyklus verschoben, aber offensichtlich traten Cache-Ersetzungen nicht so häufig auf. (Ein alternativer Gegenmechanismus auf Gegenbasis wurde ebenfalls bereitgestellt.)

Dies wurde als potenziell problematisch erkannt:

Aufgrund der Latenz der L2-Cache-Suche gibt es 3 Taktzyklen zwischen einem Lesefehler und der Zuweisung der Ersatzleitung. Somit wäre es möglich, dass der gleiche Weg zum Ersetzen von zwei oder sogar drei aufeinanderfolgenden Lesefehlern mit dem oben beschriebenen Algorithmus gewählt werden kann. Um dies zu vermeiden, vergleicht der tatsächliche Algorithmus eine ausgewählte Ersatzzeile mit den drei vorherigen Ersatzzeilen. Wenn die ausgewählte Zeile mit einer der drei vorherigen übereinstimmt, wird automatisch ein Wert von eins, zwei oder drei zu dem Wert hinzugefügt, der den Weg für das Ersetzen auswählt.

Paul A. Clayton
quelle