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. !

[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.

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.p...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.