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.
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?
digital-logic
Bruno Kim
quelle
quelle
Antworten:
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.
quelle
[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.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
N
undN+1
sehr 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.
quelle
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:
quelle