Hallo Leute,
ich versuche jetzt seit geraumer Zeit Zufallszahlen mit meinem Atmega8
zu generieren doch irgendwie funktioniert das nicht so richtig. Also
probieren wollte ich es mit einem linear rückgekoppelten
Schieberegister(http://de.wikipedia.org/wiki/Linear_r%C3%BCckgekoppeltes_Schieberegister)
um das umzusetzen nutze ich folgenden Code:
Bevor sich jemand beschwert: Ich weiß, dass die Verzögerung nicht
optimal gelöst ist und dass man das eigentlich mit einem Timer macht,
aber darum gings mir erstmal nicht.
Das Problem ist das er nach ein paar Schritten bei dem Wert 0b00111111
stehen bleibt und ich verstehe nicht warum, denn eigentlich müsste dass
quasi eine Endlosschleife sein bei der sich ständig die Werte ändern.
Könnte mir bitte jemand einen Tip geben? Danke schon mal vornweg.
David
Deinen Gedankengang mit der eor-Verknüpfung verstehe ich zwar nicht ganz
(bin schon müde), aber ich habe erst vor kurzem das selbe Programm auf
eine 8051 in asm und c geschrieben. Ich erkläre mal, wie ich es gelöst
habe (hat funktioniert):
Wenn man von einem 8-Bit Schieberegister ausgeht:
Du musst die Bits 0,4,5,6 eor-Verknüpfen und an den Eingang des
Schieberegisters legen. Meine Methode:
Du legts eine Kopie des Registers an. Danach schiebst du nach einander
jedes der 4 relevanten Bits in das Carry-Bit und summierst mit dem
Befehl ADC die einzelnen Bits auf. Am ende überprüfst du das LSB dieser
Zahl und wenn es gesetzt ist dann: Das Register mit der Zufallszahl
einmal nach rechts schieben und das MSB setzen. Sonst nur einmal
schieben und nichts setzen.
Ich hoffe ich konnte dir helfen. Vielleicht schreib ich das Beispiel
noch schnell. Wenn ja, poste ich es.
Danke erstmal für den Tip.
Naja wie der Alogithmus funktioniert steht ja in dem Link, da ist auch
das mit der EOR Verknüpfung erklärt. Ich mache das halt so dass ich eine
Kopie der Zahl anlege, dann die Kopie 3 mal nach rechts schiebe damit
quasi das Bit 0 mit Bit 3 EOR verküpft wird.
Ich benutze zwar (erstmal) nur 6 Bit, aber ich denke dass ich dein
Verfahren trotzdem anwenden kann. Schau'n mer ma'.
;generates 16 bit random value (16Bit SR with feedback on Bit 0, 2, 11, 15)
2
RANDOM:
3
mov Temp, RandomL ;exor feedback outputs for SR input
4
andi Temp, 0b00000001
5
lsl Temp
6
lsl Temp
7
eor Temp, RandomL
8
andi Temp, 0b00000100
9
swap Temp
10
lsl Temp
11
mov TempH, RandomH
12
andi TempH, 0b00001000
13
swap TempH
14
eor TempH, RandomH
15
andi TempH, 0b10000000
16
eor TempH, Temp
17
rol TempH
18
rol RandomL
19
rol RandomH
20
ret
RandomL und RandomH müssen zu Initialisierung mit einem Wert |= 0
geladen werden. Die Routine wird 1x pro Main-Durchlauf aufgerufen, wenn
Zufallszahlen gebraucht werden, liest man einfach RandomL und/oder
RandomH aus.
Mal so kleiner Tipp, was Dokumentation von Code angeht: Die Kommentare
sollen nicht beschreiben, was der Befehl macht, sondern Info darüber
geben, warum man etwas macht. Sonst hat man keinen Informationsgewinn.
Man schreibt z.B. nicht "Port B Pin 1 setzen" sondern "LED einschalten".
So danke an alle für die Tipps, hat super funktioniert. Nun muss ich nur
noch ein paar schlechte Angewohnheiten (Verzögerung) ausbessern und dann
gefällts mir richtig gut.
Ich habe seit geraumer Zeit den hier im Einsatz. Der Link ist allerdings
tot :-(
/* This code is listed in
* http://remus.rutgers.edu/~rhoads/Code/code.html
*
* in file
* http://remus.rutgers.edu/~rhoads/Code/random2.c
*
* with the following description:
*
* Concatenation of two 16-bit Multiply with carry generators.
* Has a list of recommended parameters. Good and even faster than the
above.
* Perhaps the fastest of any generator that passes the Diehard tests.
*/
/* concatenation of following two 16-bit multiply with carry generators
*/
/* x(n)=a*x(n-1)+carry mod 2^16 and y(n)=b*y(n-1)+carry mod 2^16, */
/* number and carry packed within the same 32 bit integer. */
/******************************************************************/
#ifndef _RRAND_H_
#define _RRAND_H_
/* return a random float >= 0 and < 1 */
#define rand_float ((double)rrand() / 4294967296.0)
static unsigned int SEED_X = 521288629;
static unsigned int SEED_Y = 362436069;
static inline unsigned int rrand ()
{
/* Use any pair of non-equal numbers from this list for "a" and "b"
18000 18030 18273 18513 18879 19074 19098 19164 19215 19584
19599 19950 20088 20508 20544 20664 20814 20970 21153 21243
21423 21723 21954 22125 22188 22293 22860 22938 22965 22974
23109 23124 23163 23208 23508 23520 23553 23658 23865 24114
24219 24660 24699 24864 24948 25023 25308 25443 26004 26088
26154 26550 26679 26838 27183 27258 27753 27795 27810 27834
27960 28320 28380 28689 28710 28794 28854 28959 28980 29013
29379 29889 30135 30345 30459 30714 30903 30963 31059 31083
*/
static unsigned int a = 18000, b = 30903;
SEED_X = a*(SEED_X&65535) + (SEED_X>>16);
SEED_Y = b*(SEED_Y&65535) + (SEED_Y>>16);
return ((SEED_X<<16) + (SEED_Y&65535));
}
static inline void rrand_seed( unsigned int seed1, unsigned int seed2 )
{
if (seed1) SEED_X = seed1; /* use default seeds if parameter is 0
*/
if (seed2) SEED_Y = seed2;
}
#endif /* _RRAND_H_ */
@Jan Zodiax (Firma ujbxp)
Gibt das wirklich 100% Random ?
Hat man bei so einer Hardwareloesung nicht immer die Gefahr, das
irgendwelche Dreckeffekte einem doch irgendwelche Periodizitaeten oder
anderes Einstrahlen?
Als Seed wuerde ich auch etwas "richtig" Zufaelliges waehlen, jedoch
ansonsten sind Pseudo Noise Folgen erste Wahl.
ArthurDent wrote:
> @Jan Zodiax (Firma ujbxp)>> Gibt das wirklich 100% Random ?>> Hat man bei so einer Hardwareloesung nicht immer die Gefahr, das> irgendwelche Dreckeffekte einem doch irgendwelche Periodizitaeten oder> anderes Einstrahlen?>> Als Seed wuerde ich auch etwas "richtig" Zufaelliges waehlen, jedoch> ansonsten sind Pseudo Noise Folgen erste Wahl.
Hallo ArthurDent,
Periodizitaet habe ich bisher nicht feststellen können; ich verwende
diesen Randomgenerator häufig in Spielen.
Für ein gutes Ergebnis brauchst Du nur ein Stück Draht vom ADC Messpin
(in diesem Fall Pin 40= A0)herauszuführen, 2-3 cm reichen vollkommen.
Der Controller empfängt dann soviel Rauschen und Datenmüll von Aussen
(Handy\TV\Radio-strahlen etc..). Kein Mensch dann kann vorhersagen
welche Zahl als nächstes kommt,und das ist meiner Meinung nach ein gutes
Zufallsergebnis.
Probiers einfach mal aus, schreib die Zufallsdaten zurück ins RAM
und sende sie per serieller Schnittstelle zurück zum PC.
Gruß
Zodiax
Ich denke, der offene ADC-Pin wird in der Hauptsache 50Hz der
allgegenwärtigen Netzleitung messen, was keinesfalls zufällig ist.
Versuche Deinen ADC-Zufallsgenerator mal in einem abgeschiedenen Gebiet
ohne Stromnetz zu betreiben, ich vermute mal, die Ergebnisse werden ganz
anders aussehen.
Wenn man beweisbar guten Zufall haben möchte dann sollte man einen
Pseudo Zufallsgenerator benutzen.
Ich mache es immer so:
- zwei LFSRs mit hinreichend großer Periode und unterschiedlichen
Polynomen
- ein Startwert=Seed steht im EEPROM
- beim RESET wird Startwert aus EEPROM geladen in beide PRNGs
- der eine PRNG wird nun dazu benutzt den nächsten Seed zu berechnen,
dieser Wert wird gespeichert im EEPROM
- der zweite PRNG dient dann in der Anwendung als Zufallsgenerator und
läuft mit dem so berechneten Seed
Somit erzeugt man nach jedem RESET einen anderen Seed. Diese Erzeugung
ist abhängig von dem einen PRNG. Nach dem ersten flashen der Anwendung
startet das System (jede AVR Kopie) mit exakt den gleichen Bedingungen.
Somit kann man auch eventuelle Fehler exakt reproduzieren und
simulieren, da man die Anfangsbedingungen der PRNGs eben reproduzieren
kann. Nichts ist schlimmer als eine Fehlersuche in einem Program das
echten Zufall in dessen Programablauf benutzt.
Der dazu nötige Code beträgt 31 Opcodes.
Der Code in Main() zur Berechnung der Seeds sieht dann so aus (aus
meinem Glühwürmchen Projekt in der Codelib)
1
// init PRNG, load last seed from EEPROM, calculate next seed and store back to EEPROM, use another polynom as in lfsr()
Er ist sicher und sparrt den enormen Aufwand wenn man versucht sein möge
den aktuellen Seed beim Wegfallen der Spannung speichern zu wollen ;)
Wichtig erachte ich aber den Fakt das man so wirklich eine
Reproduzierbarkeit der Ergebnisse des Programmes bekommt. Und
Programmieren bedeutet als Erstes für den Programmierer eine
Reproduzierbarkeit zu erreichen.
Für die spätere Serialization des Programmes, also so das jede AVR Kopie
einen anderen Zufall erzeugt, kann man ja die EEPROM Zellen für jede AVR
Kopie serialisieren = individuell initialisieren.
Allgemein halte ich nicht viel von den vorgeschlagenen HW-Lösungen. Der
so erzeugte "Zufall" ist in erster Linie mal nur abhängig von den
physikalischen Eigenschaften der Bauteile. Erst in vierter/fünfter Linie
ist er abhängig vom thermischen Zufalls-Rauschen auf Grund der
Hintergrundstrahlungen des Universums, und nur das wäre eine gute Quelle
für echten Zufall. Die Konstrukteure der Bauteile versuchen ja gerade
all diese unerwünschten Abhängigkeiten zu minimieren, sprich
Temperaturstabilitäten zu verbessern, Einflüsse durch EMV zu minimieren
usw. Das Rauschen des ADCs im AVR ist also erstmal systembedingt und
nicht so stark zufällig wie man annehmen würde.
Davon abgesehen entsteht für den Entwickler immer eine
Argumentations-Falle. Denn beweise mir das der so erzeugte Zufall auch
wirklich echt zufällig sein muß ! Das kann man aber nicht da man nicht
alle Parameter des Systemes kennen kann. Im Umkehrschluß kann ich also
mit Recht behaupten das das das System "ADC + Antenne" eben keinen
Zufall erzeugt, sondern nur hochkomplexe und von vielen Unbekannten
abhängige Bits sammelt.
Gruß Hagen
Genauso kann der ADC-Pin durch Spannungeeinstreuung hochlaufen und an
der Spannungsoberkante kleben bleiben und somit für einen längeren
Zeitraum sauber 0x3FF (1023) ausgeben. Nicht wirklich Zufall.
Es gibt also zwei Wege:
1.) man erzeugt "Zufall" mit mathematischen Verfahren. Die Komplexität
dieses Verfahrens und der verwendeten Zahlengrößen bestimmt die
Vorhersagbarkeit durch Dritte und die statistischen Eigenschaften des
Zufalls. Je nach Verfahren und Komplexität kann man diesen "Zufall" dann
nur reproduzieren wenn man die Anfangsbedignungen kennt, sprich das
Seed. Schützt man dieses so wird defakto für einen Dritten der erzeugte
Zufallsstrom wie echter icht vorhersagbarer Zufall erscheinen. Somit
kann man Beide Vorteile als Entwickler nutzniesen, die evtl. nötige
Reproduzierbarkeit der Ergebnisse in der Entwicklungsphase und die
beweisbare Nicht-Reproduzierbarkeit des Zufallsstromes für Dritte die
keinen Zugriff auf das Seed haben.
2.) man misst "Zufall". Dann benutzt man Hardware, mit ihr kann man
keinen Zufall erzeugen sondern nur Zufallseregnisse messen. Dabei ist es
aber dann auch wirklich wichtig das man sauber misst, also scharf
abgrenzen kann zwischen der zu messenden Zufallsquelle und den
physiaklsichen Störparametern der Bauteile und der Umwelt, und eben eine
gute Quelle der physikalischen Zufallsereignisse benutzt. In letzter
Konsequenz kann man eigentlich nur die Hintergrundstrahlung des
Universums als solch eine Quelle als gut bezeichnen. Oft benutzt man
radioaktive Zerfallsprozesse als Quelle. Auch diese sind als gut zu
bewerten da sie in letzter Konsequenz mit dem zeitlichen Verlauf des
Universums korrelieren, ergo Hintergrundstrahlung. Aber nur dann wenn
man sie von anderen absichtlichen radioaktiven Störquellen auch
messtechnisch unterscheiden kann.
Gruß Hagen
>Genauso kann der ADC-Pin durch Spannungeeinstreuung hochlaufen und an>der Spannungsoberkante kleben bleiben und somit für einen längeren>Zeitraum sauber 0x3FF (1023) ausgeben. Nicht wirklich Zufall.
Und viel schlimmer ist dabei der Fakt das man dieses Eregnis eben nicht
reproduzieren noch vorhersagen kann. Man wird dann als Entwickler
bestimmte mathematische Verfahren nachschalten müssen, also zb. die
Entropie verdichten zb. durch Hashalgorithmen, oder statistische
Verfahren um den so erzeugten "Zufall" zu bewerten. In letzter
Konsequenz hat man einen enormen zusätzlichen Aufwand betrieben der mehr
kostet als gleich einen guten beweisbaren PRNG zu benutzen.
Für den Entwickler bedeutet dies also:
Man verlässt sich in seiner Entwicklung, im Nachweis der
Funktionstüchtigkeit des eigenen Programmes auf Unvorhersagbarkeiten.
Das ist ein Widerspruch in der Arbeitsweise des Entwicklers.
Gruß Hagen
> Schützt man dieses so wird defakto für einen Dritten der erzeugte> Zufallsstrom wie echter icht vorhersagbarer Zufall erscheinen.
Das gilt nur bei kryptografisch sicheren Zufallszahlengeneratoren.
Deine LFSRs gehören nicht dazu.
Jürgen
Jo ich weiß habe auch nichts anderes behauptet ;) Es ging ja in dieser
Aussage im Allgemeinen um die machbaren Vorteile der PRNG im Vergleich
zu HW-RNGs.
Gruß Hagen
PS: übrigens sind es nicht meine LFSRs, ich habe sie nur in AVR Source
umgesetzt ;)
Thread beobachten
Seitenaufteilung abschalten