Forum: Mikrocontroller und Digitale Elektronik zufallszahl (at90s2313)

Ein langes Schieberegister bauen (3 Bytes in Software), Bit 13 und Bit
17 EXOR verknüpfen und per AND die Zahlen von 2-6 filtern. Das
Schieberegister hoch genug takten (mindestens 8x schneller als
abzufragende Zufallszahl).

klingt gut.

haste da für ein c code da ?

jeroen

Nee, leider nicht, mach´ alles in ASM. Ist da kein Problem - 20 Zeilen
Code ;)

ist das bei dir ein funktion ?
wenn ja schick troßdem mal !

uint8_t r = rand();
r = (r & 0x03) + ((r >> 2) & 0x01) + 2;

[0..3] + [0..1] + 2 = [2..6]

so bleibt die zufällige aber gleichmäßige Verteilung der Zahlen
zwischen 2 bis 6 erhalten, und die doch recht langsamme Funktion rand()
wird nur so oft wie nötig aufgerufen.


>>verknüpfen und per AND die Zahlen von 2-6 filtern.
>>Das Schieberegister hoch genug takten
>> (mindestens 8x schneller als abzufragende Zufallszahl).

Das ist nämlich ein ziemlich schlechter Vorschlag. Denn obwohl
statistisch sehr unwahrscheinlich ist es denoch praktisch möglich das
zb. 1000 mal nacheinander eine 0 erzeugt wird. In diesem Moment würde
mit obigen Vorschlag der Zufallsgenerator unnötig lange den
Programmfluß blockieren. Ein "übertakten" des RNGs ist also garnicht
nötig wenn man wie mit meinem Vorschlag die Zahlen einfach
zusammenbaut. Zudem erzeugt man so KEINE statistische Gleichverteilung
der Menge der möglichen Zahlen. Dh. man würde zb. die Zahl 6 wesentlich
häufiger erzeugen als zb. Zahl 3.

Gruß Hagen

leider kennt CodeVisionAVR, uint8_t nicht.

braucht ich dafür ein bestimmt bibliothek ?

jeroen

Nimm unsigned char. Ist das selbe.

die funktion zieht jetzt so aus:

int zufall()
{
unsigned char r;
r = rand();
r = (r & 0x03) + ((r >> 2) & 0x01) + 2;
return r;
}


welche werte sind jetzt für den zahlenbereicht zuständig ?

jeroen

hab nun folgendes geflashed:

#include <90s2313.h>
#include <stdlib.h>

int zufall()
{
unsigned char r;
r = rand();
r = (r & 0x03) + ((r >> 2) & 0x01) + 2;
return r;
}

void main(void)
{
DDRB=0xFF;

PORTB = zufall();
while (1);
}

kommt leider nur immer 0x05 raus.

jeroen

du schreibts ja auch nur die 1. zufallszahl auf den port.
in ner endlosschleife passiert nicht so wirklich viel.

Der RNG der stdlib ist ein Pseudo-zufallsgenerator, eine berechenbare
mathematrische Funktion die logischerweise mit den gleichen Startwerten
IMMER die gleichen Resultate erzeugen muß. DAS ist ja gerade der Vorteil
eines Pseudo-Zufallsgenerators gegenüber echten Zufall.

Also RandSeed oder so musst du vorher immer mit einem anderen Wert
initialisieren. Zb. könntest du das mit einem im EEPROM gespeicherten
Wert machen. Den aktuellen RandSeed Wert beim Ausschalten der MCU
speicherst du dann in dieses EEPROM.

Gruß Hagen

Hallo,
um die Zufälligkeit ein wenig zu erhöhen könnte man als externen
einfluss auch die Temperatur nehmen. Über einen ntc oder ptc am portpin
einen kleinen kondensator laden. zwischen dem ntc und dem C dann das
Signal abgreifen und auf einen eingang zurückführen. Dann könntest du
den ausgang setzen und mit hoher geschwindigkeit so lange zählen bis
der eingangspin kommt. Den zähler einfach mit ner while schleife, und
bei ner 7 auf 1 zurücksetzen. Man könnte das ganze dann so auslegen das
es bei 20 grad ca 5ms dauert bis der eingang kommt. Wenn du in der
deiner while schleife dann ohne eingebauten pausen zählst und auf eine
zählgeschwindigkeit von sagen wir mal 10khz kommst hat die kleinste
temperaturschwankung großen einfluss auf den entstehenden wert.

mfg
Stefan

Sicher, perfekt ist mein Vorschlag nicht, es war nur ein Dekanstoß. Wenn
ich einst eine venünftige Routine gebastelt habe, poste ich sie mal in
der Codesammlung, dürfte dann allerdings etwas länger als 20 Zeilen
werden, dafür dann hübsch konfigurierbar ;). Einen einfachen
Zufallsgenerator hatte ich mal mit 2 unterschiedlich schnell laufenden
Timern gebaut, das lief recht schön und auch ziemlich "zufällig":
Timer 2 löste dann und wann einen Interrupt aus und sampelte dabei das
Timerregister vom weitaus schnelleren Timer 1. Noch etwas Bitschieberei
hintendran um den Zählbereich einzugrenzen und gut war´s.
Schönen Abend noch.

so was hatten ich mir irgendwie schon gedacht.

gut das die platine noch nicht geäzt ist.
ich glaub ich kopple den programm start des programm an einen
tastendruck.


jeroen

Dann ist das vollkommen in Software möglich.

nach einem Reset initialisierst du einen Timer der ja sowieso diese
Taste pollt und das Debouncing der Taste enthält. Zusätzlich zu diesem
eh notwendigen Code kannst du den RandSeed mit dem Timer initialisieren
und als zweiten Timerwert das Loslassen der Taste. Beides kann man als
nicht repdouzierbaren Pseudozufall, erzeugt durch einen Menschen,
ansehen. Das ist so gut wie echter Zufall.
Aber mache diese Initialisierung nur einmal pro RESET, nicht öfters.
Danach kannst du einfach mit Rand() weiterarbeiten bis zum nächsten
RESET.

Übrigens, falls dir die Funktion Rand() nicht gut genug ist oder zuviel
an FLASH verbraucht dann kannst du hier in der CodeLib meine GLCD
Library downloden. In dieser ist ein sogenannter LFSR-SG = Linear
Feedback Shift Register-Shrinking Generator enthalten der
1.) mit 2^63 Bit eine viel größere Periode hat
2.) weniger Code als Rand() benötigt
3.) meistens weit schneller als Rand() ist
4.) statistisch besseren Zufall erzeugt, es ist halt ein LFSR statt
einem LCG.
5.) auch für kryptographische Zwecke geeignet ist (BASICCards, das sind
SmartCards benutzen lange Zeit diesen RNG).

Gruß Hagen

hi,

gib es denn gar keine software lösung ?
das währe echt einfacher, dann müsste ich nix ändern.

jeroen

Häm ??

Doch ein Post vorher beschrieben, oder doch nicht ?

Nochmal zusammengefasst:

1.) benutze

int zufall()
{
unsigned char r;
r = rand();
r = (r & 0x03) + ((r >> 2) & 0x01) + 2;
return r;
}

um deine Zahlen zwischen 2 bis 6 zu erzeugen.

2.) beim der Initialisierung muß nun RandSeed initialisiert werden
damit nicht immer die gleiche Zahlenfolge durch Zufall() erzeugt wird.
Dazu nimmst du einfach den Zeitpunkt indem der Anwednder das Erste mal
den Taster drückst und die Dauer des Tastendruckes. Bei entsprechend
hoher Auflösung des Timers bewegen sich die Zeitunterschiede im
Nanosekunden-Bereich. Das schafft kein Mensch innerhalb von
Nanosekunden einen Taster exakt gleich und wiederholbar zu drücken.
Somit hast du zwar eine nicht ECHT zufälligen Startwert für RandSeed()
aber einen garantiert nicht exakt reproduzierbaren Startwert.

Oder einfacher ausgedrückt: es ist nur wichtig das bei jedem
Einschalten deines AVRs der Wert in RandSeed() immer unterschiedlich
ist. Ist dies der Fall so produziert die Funktion Zufall() auch immer
andere Zahlenfolgen.

Soooo. Einen Taster haste, eine MCU mit Timer haste, die Software für
Rand() haste, du hast also alles was du benötigst und brauchst KEINE
andere Hardware. Also heul :) nicht sonder fange an das umzusetzen ;)


Gruß Hagen

Hi Cheers Detlef,

wird deine zufall von äußern faktoren bestimmt ?
Wie tasten druck, oder so was ?

Haste du eine passende C funktion ?

jeroen

ok ich habs eingesehen das ich miene schaltung um einen schalter
erweitern muss :-(

kann mir einer einen schalter sagen, am besten von reichelt.
bitte mit angabe von abständen zwischen den pin's.

@hagen:

> [0..3] + [0..1] + 2 = [2..6]
>
> so bleibt die zufällige aber gleichmäßige Verteilung der Zahlen
> zwischen 2 bis 6 erhalten, und die doch recht langsamme Funktion
> rand() wird nur so oft wie nötig aufgerufen.

Das ist leider falsch...

Durch das addieren von Zufallszahlen beliebiger Verteilung näherst Du
Dich immer der Gausschen Normalverteilung an.

Willkommen in der Wunderwelt der Statistik und der Zufallszahlen. ;-)

Aber zurück zum Problem:

Die erste Gegenfrage bei der Frage nach Zufallszahlenerzeugung ist:

  Für was werden die Zufallszahlen gebraucht?

Es macht einen riesen Unterschied, ob jemand echte Zufallszahlen
brauch, ob Pseudo-Zufallszahlen reichen, oder ob es auf den
menschlichen Betrachter wie Zufall aussehen soll.

ich bracuhe den zufall für ein rouletspiel.

hat hier jemand ein taster für mich ?


jeroen

@Detlef:

Ja dies stimmt ;)

Aber fragen wir uns mal wie man üblicherweise eine Zufallszahl zwischen
0 bis 4 == 2 bis 6 erzeugt.

Man rechnet Rand() modulo Anzahl. Gehen wir mal davon aus das Rand()
selber Zahlen zwischen 0 bis 7 erzeugen kann, also 0 bis 2^x -1 da wir
ja immer mit binären Datentypen arbeiten.

So bald die Anzahl <> 2^x ist muß es durch die modulo Operation zu
einer Ungleichverteilung kommen.

Das lässt sich aber lösen mit nachfolgender Methode, allerdings
erwähnte ich diese nicht da der Fragesteller offensichtlich ein
Anfänger ist.

unsigned char zufall2to6(void) {

  static unsigned char r = 0;

  r = r + (rand() % 8);
  while (r >= 5) r -= 5;
  return(r + 2);
}

Der modulare "Fehler" von [5..7] wird einfach bei den succesiven
Aufrufen von zufall() akkumuliert.

Nur wenn rand() eine Menge erzeugt deren Kardinalität = Anzahl Elemente
eine Primzahl darstellt kann man ohne Gefahr mit jedem Modul in mod
rechnen. Allerdings trifft dies nicht auf die meisten RNGs zu. Also
LSFRs, CRCs, Hashalgorithmen oder sogar echter Zufall bei dessen
Periode wir ja nicht wissen wie groß sie ist, bzw. ob die unendliche
Periode dieser echten RNGs nun eine gerade oder ungerade Zahl ist. Bzw.
genauer gesagt bei echten Zufallsgeneratoren wissen wir das deren
"Periode" unendlich groß sein sollte. Das Problem ist nun die Frage
"ist Unendlich relativ prime zu unserem Modulus ?". Falls ja können
wir gefahrlos mit unserem Modulus rand() % Modulus rechnen, falls nein
so würden wir eine Ungleichverteilung der Zahlen erreichen.
Das kannst du natürlich auch übertragen (downinterpolieren) auf jeden
beliebigen Zufallsgenerator bei dem wir eben nicht exakt wissen wie
groß deren reale Periode eigentlich ist. Besonders bei den meisten LCGs
= Linear Congruental Generators, wie dem in Rand() ist die reale Periode
abhängig vom Startwert = Seed des RNGs. Je nach Seed ändert sich also
die Periode.

Obige Funktion korregiert dies und arbeitet sozusagen unabhängig von
der Distributation des Zufallsalgortihmus in rand() oder jedes anderen
RNGs. Allerdings akkumiliert sie diesen Fehler nicht zu 100%
mathematisch exakt gleichverteilt sondern nur im Mittel statistisch
gleichverteilt. Das zu erklären würde aber hier in einer mathematischen
Abhandlung ausarten. Praktisch gesehen fällt das nicht ins Gewicht.

Sooo: erkläre dies mal einem Anfänger ;)

Gruß hagen

Um diese "statistische Ungfleichverteilung" auch noch wegzubekommen
nimmt man nachfolgende Funktion.

unsigned char Zufall2to6(void) {

   static unsigned char k = 0;
   static unsigned char r = 0;

   if (k < 5) {
     r += rand() mod 8;
     k += 8;
   }
   k -= 5;
   if (r >= 5) r -= 5;

   unsigned char v = r;
   while (v >= 5) v -= 5;

   return(v + 2);
}


Die besagte im Mittel gleichverteilte Ungleichverteiltung (was fürn
Wortkonstrukt ;) entsteht mit der Funktion aus dem letzten Posting
dadurch das man quasi in "Sprüngen" von 5i aus der Menge von 8i
Elementen auswählt. Es können also 5i große Lücken bei der Auswahl der
Zahlen entstehen. Das kann mit obiger Funktion nun nicht mehr
passieren. Problematisch wird dies falls der benutzte RNG Periode 8 hat
aber zb. selber Ungleichverteilungen mit Periode 5i enthält. Dann taugt
aber der RNG nichts. Exakt dieses Problem tritt beim LCG wie dem in
rand() auf. Dieser LCG hat solche "Ungleichverteilungen" bzw. Muster
die abhängig vom gewählten Startwert sind.

Gruß Hagen

Zu den Algorithmen, wie man Zufallszahlen in C ermittelt ist ja schon
viel gesagt. Hauptproblem bleibt da wohl die Initialisierung. Ein Blick
nach
http://www.elektor.de/default.aspx?tabid=29&view=topic&forumid=23&postid=3789
zeigt die triviale Lösung.

@Florian:

das ist es was ich vermeiden würde. Denn wie immer, es fehlt der Beweis
das das immer korrekt funktioniert. Angenommen die Schaltung wird leucht
feucht und es kann ein Kriechstrom vom Pin nach Masse fleißen ? Dann ist
die Initialisierung des RNGs mit sich verändernden Werten nicht mehr
gesichert.

Wenn schon Taster vorhanden sind, und es für die Software eh notwendig
ist das der Taster gedrückt wird, dann sollte man diesen auch nutzen.

Besser wäre es dann schon eine Diode zu benutzen und deren Rauschen.
Das ist dann elektronisch auch garantiert.

Gruß Hagen

Wenn der Chip einen ADC hat: ADC-Takt sehr hoch (z.B. 1MHz) wählen und
nach jedem Sample eines auf Uref/2 gelegten Inputs das untere Bit in
eine Variable hineinschieben. Der ADC rauscht ja bekanntlich munter vor
sich hin. Da das LSB besonders bei "zu hohem" Takt doch recht wild
herumtoggled kann man den so erzeugten Wert z.B. zum Initialisieren von
rand() nehmen.

@Detlef:

>>Man kann den Fehler aber beliebig klein machen, wenn
>>man n groß macht. Der Rest Deiner Einlassung entzieht sich leider
>> meinem Verständnis. Könntest Du Dich genauer erklären?

Ganz einfach ;) Statt einen nicht gleichmäßigen Bereich ungleichmäßig
zu teilen, rechnen wir in Stücken diesen Bereich modulo in unseren
Zielbereich um.

Einfaches Beispiel:

Bereich bis 8, wir benötigen aber Bereich bis 3. Also 3+3+3+3+3+3 usw.
Bei 3+3+3 = 9 gibts einen Überlauf über Bereich 8. Wir rechnen ab da
die Zahlen mit einem "Offset" weiter. Also 9-8 = +1 versetzt.

Unser Rand() % 8 erzeugt ja Zahlen zwischen 0 bis 7. Stelle dir diese
Zahlen mal als Gerade vor die aus Stücken a 8 Elementen zusammengesetzt
ist. Also 0..7,0..7,0..7 usw. Das wäre das gleiche wie 0..23 immer
modulo 8 genommen. Wir möchten nun diese 0..23 bzw. eben 0..7,0..7,0..7
Gerade aber in 0..2,0..2,0..2 zerteilen. Nichts anderes macht mein
letzter Sourcecode.

Angenommen du hast einen echten Zufallsgenerator der logisch gesehen
eine unendlich große Periode besitzt, also eine Zahlengerade erzeugt
die von 0 bis unendlich geht. Wie willst du diese Periode in Stücken
von zb. 8 teilen ? Dein Vorschlag bezog sich ja darauf das man weis das
die Periode zb. 1000 ist und ich davon einen Bereich mit 5 Elementen
suche. Du wolltest jetzt eine Zahl zwischen 0 bis 999 erzeugen und dann
diese durch 1000/5 = 200 teilen, also auf 5 gleichgroße Zahlenbereich
umrechnen.
Nur, wenn die Periode nicht real bekannt ist, oder sie veränderlich ist
oder eben unendlich dann klappt das nicht mehr exakt.

Deshalb einfach sequientiell den Bereich in die Unterbereiche
aufteilen, so wie im letzten Source gezeigt.

Mathematisch gesehen ist das im Grunde nichts anderes als eine Modulo
Divison die per Additionen sequientiell berechnet wird.

Gruß Hagen

noch besser zufall bekommt mann wenn man ein OP ohne rückkopplung
arbeiten lässt.

                    _
                   | \
langer draht ------|- \
                   |   >----ADC
                  _|+ /
                  ||_/
                  |
                 ---
                  -

@Detlef:

Dein Problem im Verständniss liegt wohl daran das du die obigen
Berechnungen als Additionen von einzelnen Zahlen betrachtest.

Dies stimmt aber eigentlich garnicht. Erst beim return(v +2) geben wir
eine Zahl = Element aus einer Menge von 5 gleichwahrscheinlichen und
zufälligen Elementen zurück.

Die Berechnungen vorher sind eher im Kontext der Mengenlehre zu sehen.
Dh. dort rechnen wir mit der Elementeanzahl zwei verschiednener Mengen
-> Rand() & 8 = 8 Elemente von 0 bis 7 durchnummerriert und Menge K = 5
Elemente druchnummeriert von 0 bis 4.

Entscheidend ist dabei das bei einer Menge mit 8 Elementen die
Wahrscheinlichkeit für jedes Element das es "gezogen" wird exakt 1/8
= 12.5% beträgt. Wir suchen aber eine Menge mit 5 Elementen mit
Wahrscheinlichkeit 1/5 = 20%.

Was wäre wenn wir nun beide Mengen in eine dritte Menge C mit
Kardinalität 40 umwandeln ??

40 / 5 = 8 und
40 / 8 = 5.

Eine Menge C mit 40 Elementen wäre also ohne Rest teilbar durch beide
Mengen.

Also erzeugen wir einfach 5 mal mit Rand() % 8 eine Zahlenmenge a 40
Elemente und zerlegen diese Menge dann in 8 gleiche Teile a 5
Elemente.

Nichts anderes macht obiger Source, aber eben einfach mit
mathematischen Berechnungen und sequientiell Stück für Stück.

Wichtig ist nur eines zu sehen: man kann nicht nur mit Zahlen rechnen
sondern auch mit der Anzahl einer Menge von Zahlen und sogar mit deren
Zahlenmäßigen Wahscheinlichkeit ihres Auftretens innerhalb solcher
Mengen ;)

Die ersten Additionen in meinem Source beziehen sich also noch nicht
auf die eigentlich zu erzeugene Zufallszahl sondern nur auf deren
mengenmäßige Gleichverteilung.


Gruß Hagen

Achso:

>> Also erzeugen wir einfach 5 mal mit Rand() % 8 eine Zahlenmenge
>> a 40 Elemente und zerlegen diese Menge dann in 8 gleiche Teile a
>> 5 Elemente.

Wenn wir davon ausgehen das in der Menge mit 8 Elementen jedes der 8
Elemente eine Wahrscheinlichkeit von 12.5 % hat, also gleichverteilt
ist, dann können wir davon ausgehen das wenn wir 5 Haufen von solchen
8'ter Mengen in einen Topf werfen wiederum jedes der Elemente
gleichverteilt auftaucht, richtig ?

Nun nehmen wir diesen Haufen mit 40 Elementen nummerieren ihn einfach
von neuem durch, also 0 bis 39 und zerlegen diesen dann modulo 5 in 8
Haufen mit den Zahlen 0 bis 4 pro Haufen. Wieder haben wir eine
Gleichverteilung, sowohl in den Größen=Kardinalitäten der Mengen wie
auch in der Wahrscheinlichkeiten der einzelnen Zahlen.

Gruß Hagen

Betrachte mal das Resultat eines RNGs als einen Index in eine Menge,
vielleicht bringt das dich näher.

Statt also zu sagen Rand() % 8 erzeugt Zahlen im Bereich 0 bis 7, sagen
wir Rand() % 8 erzeugt einen zufälligen Elementeindex in eine Menge aus
8 Elementen von irgendwas. Zb. Obst, Mauersteinen oder sonstwas.

Gruß Hagen

abo