Zufallsgenerator ?

[PICture]

Hallo!

Ich brauche für mein Projekt einen Zufallgenerator. Im Projekt ist ein µC bereits vorhanden und hat noch Freizeit. Laut Wikipedia am besten wäre nicht-deterministischer Zufallsgenerator: http://de.wikipedia.org/wiki/Zufallszahlengenerator .

Mir ist eine "verrückte" Idee eingefallen, die sich ziemlich einfach hardwaremässig realisieren lässt:


.-----. .-----. .-----.
| | | | | | S = Sägezahngenerator
| S |--->| SGO |--->| F |
| | | | | | SGO = spannungsgesteuerter
'-----' '-----' '-----' Oszillator

F = Frequenzzähler (µC)


(created by AACircuit v1.28.6 beta 04/19/05 www.tech-chat.de)

Was hält Ihr davon bzw. geht es einfacher, weil hier zufällig: je ungenauer um so besser ? :)

[BMS]

Hallo,
an deinem Mikrocontroller gibt es bestimmt Taster. Du könntest den µC so programmieren, dass er z.B. bei Tastendruck ein Register sehr schnell hochzählt. Nach Tastendruck wird dann der letzte Zählerstand verwendet. Da der Benutzer nicht immer gleich lange drückt, könnte man so Pseudo-Zufallszahlen erzeugen.

Eine andere einfache Möglichkeit wäre z.B. den AD-Wert eines offenen analogen Eingangs zu verwenden.
Oder du könntest den genannten Sägezahngenerator an einen analogen Eingang hängen und dann den digitalisierten AD-Wert zu verwenden.
Vorraussetzung ist natürlich, dass dein Mikrocontroller analoge Eingänge besitzt.

Es gibt auch digitale Pseudo-Zufallsgeneratoren, die z.B. mit rückgekoppelten Schieberegistern realisiert werden.
Grüße,
Bernhard

[PICture]

Hallo BMS ! ;)

Du hast den Nagel am Kopf getroffen, weil ich früher unentprellte Tasten dafür oft verwendet habe bevor ich alt geworden bin. Übrigens, Tasten prellen nur beim Drücken und nicht loslassen. Deshalb ist dein Vorschlag mit Zeitmessung für mich optimal, weil am einfachsten. Eigentlich kann bisher unbenutzter Timer permanent schnell laufen (mit gesperrten Unterbrechungen damit er das Programm nicht unnötig stört) und beim Tastendruck abgelesen werden, was noch einfacher ist. Besten Dank dafür und L.G. ! :Strahl

[ichbinsisyphos]

Bibliotheken hast keine zur Verfügung?

Man nennt die Software-Zufallsgenerator immer Pseudozufallsgenerator, was einerseits wichtig ist um keine Missverständnisse aufkommen zu lassen, aber andererseits ist ihr Verhalten in den meisten Fällen ja genau gefragt: sie erzeugen gleichverteilte Zahlen (in einer nicht sofort durchschaubaren Reihenfolge). Bei "echten" Zufallszahlen ist halt auch keine Gleichverteilung garantiert.

Kommt drauf an was du machen willst.

[PICture]

Hallo ichbinsisyphos !

Danke für deine Hilfsbereitschaft, aber ich bisher keine Bibliotheken für PIC in ASM kenne. :confused:

Ich möchte möglichst einfachen (soft- und hardwaremässig) echten Zufallszahlengenerator in ASM mit PIC realisieren. Das mit zufälligen Ablesen des permanent laufenden Timers scheint mir richtig zu sein, oder ? ;)

[ichbinsisyphos]

Aso, ich kenn mich nicht recht aus was es für die diversen Controller an Software gibt, aber ich nehm an einen Algorithmus irgendwo abschreiben sollte schon möglich sein.

Das mit "echt" und "unecht" ist nicht so einfach zu sagen. Wirklich "echt" ist es nur, wenn es aus einem tatsächlich zufälligen physikalischen Prozess stammt, also irgendwas, das als Rauschen klassifiziert wird. Das ist aber wie gesagt gar nicht immer erwünscht, weil man die Verteilung im Vorhinein nicht kennt.

Aber was du da oben skizziert hast ist ein Zähler bei dem die Frequenz einem Sägezahnverlauf folgt? Das ist dann den normalen Pseudozufallszahlen sehr ähnlich. Du musst aber einen Überlauf vorsehen, sonst kommen die ganz kleinen Zahlen nie vor. Oder du kopierst dir gleich irgendwo einen Algorithmus - zumindest versteh ich im Moment noch nicht ganz, was dein Zahlengenerator mehr können muss als die die es eh schon zu Hauf in Software gibt.

- - - Aktualisiert - - -

bits herumschieben ist einfacher als hardware, oder: http://www.dontronics.com/psbpix/random.html
Das erzeugt "Pseudozufallsbits" die sich nach 65k wiederholen. Für Zufallszahlen müsste man wahrscheinlich 8/16mal shiften.

Der hats sich ein paar mehr Gedanken gemacht: http://www.electricdruid.net/index.php?page=techniques.practicalLFSRs

[ichbinsisyphos]

Ich versuch dich immer noch zu überreden ohne externe Hardware auszukommen, oder zu verstehen, was du dir von deiner Idee für Verbesserungen erhoffst, also nicht einfach abhauen! ;)

[redround]

wann immer ich eine Zufallszahl brauche, nehme ich eigentlich eine Variable, die ich bei jedem Durchlauf der Endlos-Schleife um 1 erhöhe. Wenn der Grenzwert erreicht wird, setze ich sie wieder auf den Startwert. Das klappt super wenn man nur einen kleinen Wertebereich hat oder eine unspezifische Zeitspanne vergeht, bis man die nächste Zufallszahl braucht. Brauchst Du jedoch innerhalb 1 Sekunde 10 Zufallszahlen zwischen 1 und 10 Mio, dann klappt das so nicht mehr so schön, da die Zeitspanne zwischen dem Auslesen der Variable nicht für einen Überlauf reicht und so eine aufsteigende Folge von Zahlen entsteht. Wertebereich und Auslesehäufigkeit müssen also in einem Verhältnis stehen, das mindestens einen Überlauf zwischen zwei Auslesevorgängen ermöglicht.

[PICture]

Hallo redround !

Vielen Dank für deinen Erfahrungsbericht. :)

Mir scheint dein Vorgehen änlich wie meine Idee mit dem Timer, der paralell zum Programm läuft, also sehe ich es als deren Bestätigung. Das hochzählen muss natürlich entsprechend schnell laufen um gewünschte Menge von Zufallszahlen in konkreten Zeitabständen zu haben.

[ichbinsisyphos]

Haha, ich geb aber noch nicht auf, hier nochmal die Polynommethode mit Schieberegister-Interpretation. Weil, nur weil man bei einem Zähler in unregelmässigen Zeitabständen abliest wirds ja nicht zufälliger ... und diese Algorithmen liefern eine Zahl bei Bedarf und ruhen sonst.

http://de.wikipedia.org/wiki/Primitives_Polynom



Erzeugung von Pseudo-Zufallszahlen

Primitive Polynome definieren eine wiederkehrende Relation, die verwendet werden kann um Bits von Pseudozufallszahlen zu erzeugen. Tatsächlich steht jedes linear rückgekoppelte Schieberegister mit maximalem Zyklus (dieser ist 2lrsr length - 1) mit primitiven Polynomen in Beziehung.
Sei z.B. ein primitives Polynom x10 + x3 + 1 gegeben. Man beginnt mit einer benutzerdefinierten Saatzahl (diese muss nicht unbedingt zufällig gewählt werden). Man nimmt dann das 10-te, 3-te und 0-te Bit, gezählt vom niederwertigsten Bit, verknüpft diese mit XOR und erhält ein neues Bit. Die Saatzahl wird dann nach links verschoben und das neue Bit wird zum niederwertigsten Bit der Saatzahl. Dies kann wiederholt werden um 210−1 = 1023 Pseudo-Zufalls-Bits zu erzeugen.
Allgemein gilt für ein primitives Polynom des Grades m, dass dieser Vorgang 2m−1 Pseudo-Zufallszahlen erzeugt, bevor die Sequenz sich wiederholt.

[redround]

@PICture: ja klar ... ob Timer oder Zähl-Variable macht keinen übermäßigen Unterschied. Meine Variante "verbrät" halt ggf. etwas Rechenzeit, das sollte aber in den allermeisten Fällen nicht ins Gewicht fallen.

@ichbinsisyphos: das mit den Polynomen ist auch ne tolle Methode. Das Problem dabei ist aber glaub ich, dass bei gleicher Saat und bei gleichem Polynom-Grad immer das gleiche Ergebnis raus kommt. Das ist auch der Grund, warum die meisten Zufallzahl-Generatoren (z. B. in VB) erst mit einem geeigneten Wert initialisiert werden müssen. Üblicherweise verwendet man dort die aktuelle Systemzeit als Saat. Gerade für komplexe Zufallszahlen ist die Methode sicher besser ... in meinen Fällen ging es aber meist z. B. darum, eine INT-Zufallszahl zwischen 1 und 10 zu bekommen ... da ist die Polynom-Methode in meinen Augen etwas "Oversized".

[ichbinsisyphos]

Ja sicher, das geht immer die selbe Abfolge durch, 65kbits lang und wiederholt sich dann. Und zwar von der Zahl weg, mit der geseedet wird.

Es ist die Frage, was man will.

"Echte" Zufallszahlen nur aus Rauschen, offener A/D-Wandlereingang oder so, die können aber auch einen bias haben, wenn man nicht genau drauf achtet.

Pseudozufallszahlen mit Gleichverteilung per Algorithmus.

Eure Zählermethode ist eher ein "Irgeneinzahlengenerator" ;), weil er erstens streng deterministisch ist, aber trotzdem keine bestimmte Verteilung garantiert. Wenn man zum Beispiel eine Zahl ausgeben will, sich aber nur nicht entscheiden kann welche, dann passt das sicher. Aber Monte-Carlo-Methode könnte man so nicht implementieren.

[Besserwessi]

Bei den "echten" Zufallszahlen so wie Rauschen per AD Wandler oder die Zeitmessung zu einem Tastendruck hat man ggf. keinen perfekten Zufall. Beim AD Wandler kriegt man z.B. einen kleinen Rest 50 Hz mit rein und man hat ggf. Probleme mit der Amplitude so dass die extremen Werte gar nicht oder zu oft kommen. Auch die Methode mit dem Timer / Hochzählen ist nicht ganz trivial wenn es exakt werden soll: so dauert z.B. ggf. der Schleifendruchlauf länger in dem der Zähler zurückgesetzt wird - das gibt dann eine etwas erhöhte Wahrscheinlichkeit für den einen Wert. Auch mit dem Timer hat man möglicherweise ein ähnliches Problem je nach Codelänge und Interrupt-reaktionszeit abhängig vom Code.

Ein gute Möglichkeit ist es da einen echten Zufall mit einer Softwaremäßigen Pseudozufallszahl (z.B. Schieberegister, Polyom,...) zu kombinieren. Etwa indem der echte Zufall genutzt wird unterschiedlich viele Schritte der Pseudozufallszahlenfolge zu überspringen. Die Pseudozufallszahlen sorgen dann für die berechenbare Verteilung und machen ggf. vorhanden Reste an Vorhersehbarkeit kaum noch erkennbar. Auch kann man so die ggf. begrenzte Datenrate (z.B. nur eine Zahl pro Tastendruck) der echten Zufallszahlen umgehen.

[PICture]

Hallo Besserwessi ! :)

Deine Überlegungen sind richtig, aber ich es nur für ein geplanntes Gedächtnis-Spiel (Übung von Kurzzeitgedächtnis) mit µC brauche. Das Ziel ist es, eine zufällige immer längere Tonreihenfolge, die ich mir nicht für lange Zeit merken kann, aber immer gleich danach richtig wiederholen könnte, simpel zu generieren, mehr nicht.

Es solte etwas änliches, wie "Simon says" bzw. "Senso" sein, bloss ohne Lichts, weil bei mir Hörgedächtnis dominierend ist. Es sollte auch nur mit gleichem eintellbaren Tempo laufen, weil es hier nicht um Schnelligkeit und Motorik geht (dafür habe ich ein E-Schlagzeug "sampled drums"). ;)

Danke sehr für deine Hinweise und L.G. ! :D

[Geistesblitz]

Im Zusammenhang mit Zufallsgeneratoren ahbe ich die logistische Gleichung (http://de.wikipedia.org/wiki/Logistische_Gleichung) kennengelernt. Im Prinzip ist es eine einfache Zahlenfolge, deren Ergebnis sich aus dem vorherigen Ergebnis berechnet. Wenn man den Parameter in einem bestimmten Bereich wählt, bekommt man ein künstliches Rauschen, was nur noch wirklich schwach deterministisch ist. Lässt sich jedenfalls super auf einem Controller implementieren, hab das auch schonmal in einen Timer geschrieben gehabt, r mit einem Poti einstellbar, und mir die Ergebnisse dann per PWM auf einen Lautsprecher ausgeben lassen. Da ließ sich das Rauchen sehr gut verdeutlichen.

Ein Professor unserer Uni hat sich auch schon eine Weile mit Chaos-Generatoren beschäftigt, hier kann man ein wenig dazu lesen: http://www.roebenack.de/content/experimente-mit-zeitdiskretem-chaos-generator

[021aet04]

@Geistesblitz
Das ist eine interresante Seite die du verlinkt hast (von deinem Professor).

Ich bin gerade dabei eine Chaosgenerator zu bauen (Platinen habe ich letzte Woche gefertigt, bin jetzt beim Löten). Ich habe es mit einem LM741 gelöst. Die Schaltung habe ich aus dem Internet.
Hier habe ich eine Post geschrieben https://www.roboternetz.de/community/threads/60727-Problem-mit-Zufalls-Tabelle-(Atmega32)#3

MfG Hannes