mikrocontroller.net

Forum: Projekte & Code Zufalls-Bits in VHDL


Autor: Jörg (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Ralle (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Sigi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.