Digitaler Zufallszahlengenerator in VHDL
EIn digitaler Pseudozufallszahlengenerator in VHDL zur Realisation in FPGAs:
Intention
Oft werden in der technischen Simulation Zufallszahlen benötigt, die bestimmten Bedingungen folgen. So möchte man z.B. sicherstellen, dass im Laufe der Zeit alle Zahlen statistisch gleich häufig vorkommen. Das Abspielen von Wertesequenzen mit beliebigem Startpunkt, wie es oft verwendet wird, führt aber immer wieder zu ähnlichen Sequenzen und ist zudem in vielen Fällen vorhersagbar - d.h. bei jedem Start identisch. Ein klassischer Rauschgenerator hingegen kann nicht wirklich sicherstellen, dass jede Zahl in einem bestimmten Zeitraum mindestens einmal auftaucht und fabriziert ferner auch auf lange Sicht nicht unbedingt ein gleichverteiltes Spektrum.
Prinzip
Die gegebene Methode ist, die Werte deterministisch zu erzeugen, in einem RAM abzulegen und die Adressen, mit denen man auf das RAM zugreift, zufällig zu vertauschen, wobei ein Rauschgenerator verwendet wird, der echte und nicht vorhersagbare Zufallswerte liefert. Damit kann man festlegen, in welchen Zeitraumen ein Mindestwiderholrate gegeben sein soll, wie stark die Druchmischung ist und welche Zahlen im Detail erscheinen sollen. So lässt sich z.B. eine Normalverteilung in die Tabelle übertragen und diese dann zufällig abspielen. Auch Fehler in Datenfolgen, die in einem bestimmten Zeitraum erkannt werden sollen, können so künstlich erzeugt und abgespielt werden.
Funktion
Im Artikel Digitaler Rauschgenerator im FPGA wird beschrieben, wie man zu echten Zufallszahlen und -bits gelangt. Diese werden benutzt, um die folgende Architektur zu steuern:
Wertedefinition
Über den Wertegenerator, z.B. einen Zähler oder auch eine vorgegebene Tabelle, werden alle abzuspielenden Werte in einem RAM hinterlegt. Hierbei wird festgelegt, wie häufig ein Wert innerhalb eines Zyklus zu erscheinen hat. Sollen z.B. alle Zahlen von 0..1023 abgespielt werden, so wird nur ein einziges RAM dieser Größe verwendet, in dem jede Zahl genau einmal steht. Soll sich der Wiederholungsbereich über mehrere Zyklen erstrecken, so werden mehrere RAMs nacheinander beschrieben.
Datenvorsortierung
Bereits beim Einschreiben wird eine zufällige Sortierung vorgenommen: Ein Rauschgenerator bestimmt die Startadresse, ab der geschrieben wird und die Nummer eines Index, der einen Bitvertauscher steuert. Während des Einschreibeprozesses wird für eine festgelegte Anzahl von Schreibzyklen von z.B. 8 Werten ein bestimmtes Tauschmuster (3 bit) ausgewählt, das auf die unteren Adressbits wirkt und die ankommenden 8er-Gruppen in zufälliger Reihenfolge ablegt. Das selbe gilt für weitere Bittauscher, die in ähnlicher Weise die Datengruppen austauschen. Für ein zweistufiges System mit je 3 Bit = 64 Plätze erhält man für eine fortlaufende Zahl z.B. folgende Sortierung:
Adresssortierung
In ähnlicher Weise werden die Adressen für das spätere Auslesen generiert, wobei der gesamte RAM-Bereich von dem Bit-Vertauscher erfasst wird. Damit können Werte in einer hintere Gruppe gelangen und beim Auslesen der ersten Gruppe u.U. gar nicht auftauchen, um dann erst hinten häufiger zu erscheinen.
Verbesserungen
Eine weitere Verbesserung ist es, sowohl die Ausleseadressen, als auch Daten in kleinen Gruppen zusammenzufassen und nochmals kurz vor Anwendung zu tauschen. Z.B. kann man die beiden aktuellen Adressen an einen von einem Zufallsbit gesteuerten Austauscher anlegen, der wie im Fall des Größer-Kleiner-Sortieralgorithmus, in der Lage ist, einen Wert theoretisch bis zum Ende der Kette aufzuschieben. So werden die ursprünglichen Gruppen, die beim Einschreiben entstehen, verwischt. Auch das Einleiten in einen 1:n FIFO mit nachträglicher gruppenweisen Tauschung ist sehr effektiv.
Leistung
Durchmischung
Bei der Verwendung von 7 Einschreibepattern und 11 Auslesepattern ergeben sich bereits 77 verschiedene Datenmuster, die in beliebiger Weise zufallsgesteuert getauscht werden. Zusammen mit nur 2 Zufallstauschern für Daten und Adressen erhält man bereits nicht mehr vorausbestimmbare Anfangs und Folgewerte.
Datenrate
Das System kann (bei einiger Latenz) voll gepipelined aufgebaut werden und mit der vollen Systemtaktrate Daten liefern.