Zufalls-Bits in VHDL

[Jörg (Gast)]

Hallo zusammen,

in Programmiersprachen wie z.B. C/C++ werden Zufallsfunktionen idR.
per lineare Kongruenz erzeugt. Dies in VHDL zu implementieren ist
wegen der notwendigen Modulo-Operation iA. nicht ganz trivial.

Braucht man nur zufällige Bitfolgen, dann können wesentlich einfachere
Ansätze verwandt werden. Ein aus der Algebra bekannter Ansatz ist der
über Polynome über Z2 (oder auch Modulo 2), in der Signalverarbeitung
als "Linear Feedback Shift Register" (LFSR) implementiert.

Der im VHDL-Code verwendete Algorithmus benutzt nur eine XOR-Operation
und erzeugt je Takt maximal ein Bit. Durch Modifikation können aber
auch mehrere Bits je Takt erzeugt werden. Die generischen Werte der 
Komponente sind in der Tabelle im Code angegeben (es sind natürlich noch
viele andere Polynome möglich). Ein kleiner <width>-Wert hat dann eine
geringe, ein grosser eine sehr grosse Periodizität zur Folge (Laufzeit
bei 100MHz und <width>=32 etwa 100 Sekunden, <width>=64 praktisch
unendlich). Als Startwert (Seed) sind alle Werte ungleich Null erlaubt,
der Seed-Wert wird beim Reseten angenommen (siehe Code).

Ich habe den Zufallsgenerator für meine VGA-Ausgabe (640x480) verwendet,
indem ich jedes Pixel mit einem neuen Zufalls-Bit gefüllt habe. Schon
ab <width> = 20 ist kein Muster mehr zu erkennen.

Die Zufallsbits können auch zu Vektoren und diese dann als
Zufallszahlen interpretiert werden. Die Qualität dieser Zahlen ist
allerdings sehr schlecht!!


Viel Spass,

Jörg

[Peter D. (peda)]

Jörg wrote:
> in Programmiersprachen wie z.B. C/C++ werden Zufallsfunktionen idR.
> per lineare Kongruenz erzeugt.

Also der Keil C51 benutzt auch ein LFSR, weil sowas in Software am 
einfachsten und schnellsten ist (Schiebebefehl).

Allerdings schiebt er immer mehrmals (ich glaube 17*), damit 
aufeinanderfolgende Zufallszahlen auch unabhängig sind.

Wenn man nur einmal schiebt, kann ja z.B. nie 0xFFFF auf 0x0001 folgen.
Man muß also immer größer als die auszugebende Bitzahl schieben.


Peter

[Ralle (Gast)]

Ich habe den Generator realisiert und ein paar Fragen:

Jörg schrieb:
> in Programmiersprachen wie z.B. C/C++ werden Zufallsfunktionen idR.
> per lineare Kongruenz erzeugt. Dies in VHDL zu implementieren ist
> wegen der notwendigen Modulo-Operation iA. nicht ganz trivial.
Wieso ist Modulo nicht trivial?

> Ich habe den Zufallsgenerator für meine VGA-Ausgabe (640x480) verwendet,
> indem ich jedes Pixel mit einem neuen Zufalls-Bit gefüllt habe. Schon
> ab <width> = 20 ist kein Muster mehr zu erkennen.
Ich finde eindeutige Spektren in der Ausgabe (1280x1024). Gibt es dazu 
ein update?

[Sigi (Gast)]

Warum eine Modulo-Operation nicht trivial ist, muss der
Autor wohl selber schreiben. Ich nehme mal an, er meint
evtl. den wesentlich höheren Resourcenaufwand verglichen
mit der einfachen Shifter-Operation.

Wenn du Muster erkennst, dann kannst du einfach die Grösse
des LFSR ändern. Im INet findest du Tabellen, die bei zwei
Rückkopplungen bis WIDTH=1024 gehen (inkl. Beschreibung wie
man diese berechnet, beim Code oben gehts nur bis 64). Ab
ca 256 erkennst du wohl kaum noch Muster bei 1280x1024. Oder
du erweiterst den Code um weitere Rückkopplungen etc.

Obigen Code habe ich mal schnell durch einen Virtex4
gejagt, erzeugt bei mir 400MBits/Sec. Daraus aber Zahlen
in Form von Bitfolgen zu erzeugen halte ich für eine
schlechte Idee.