Zufallszahlen-Generator fährt sich fest oder oszilliert

[Timm T. (Gast)]

Ich habe in einem kleinen Lampenprojekt einen Zufallszahlen-Generator 
verwendet, der Farbwechsel erzeugt. Funktioniert ganz gut, aber nach 
längerer Laufzeit scheint er sich festzufahren, die Farbe ändert sich 
nicht mehr.

1. Wie kann ich prüfen, ob der Generator zuverlässig durchläuft und 
nicht irgendwann immer die gleichen Werte oder Wertefolgen bringt? Ich 
habe es für ein paar tausend Testläufe geprüft, aber anscheinend reicht 
das nicht.

2. Wie muss ich den Generator modifizieren, um einen zuverlässigen Lauf 
zu gewährleisten?

Hier der relevante Programmteil zum Erzeugen der Zufallszahl:

  ;**** Controller ATtiny2313 ****

  ;**** Startwerte und Init ****

.EQU  Crndmul    = 80    ;Mulwert für RND
.EQU  Crndseed  = 7954    ;Seedwert für RND, 16 bit

  ldi  TEMP1, high(Crndseed)
  sts  Arndval, TEMP1
  ldi  TEMP1, low(Crndseed)
  sts  Arndval + 1, TEMP1  ;Seedwert RND

  ;**** Zufallszahl holen, 1 Byte ****

  rcall  rnd_calc    ;Zufallszahl berechnen
  lds  TEMP1, Arndval + 1  ;Zufallszahl low-Byte holen

  ;**** Zufallszahl berechnen ****

rnd_calc:
          ;x = a * (x & $FF) + (x >> 8)
  ldi  TEMP1, Crndmul    ;Multiplikator
  lds  TEMP3, Arndval + 1  ;Wert x low holen
  rcall  mpy8u      ;xneu = a * (x & FF)
  lds  TEMP1, Arndval    ;Wert x high holen
  add  TEMP3, TEMP1
  clr  TEMP1
  adc  TEMP4, TEMP1    ;xneu = xneu + (x >> 8)

  sts  Arndval, TEMP4
  sts  Arndval + 1, TEMP3  ;Wert speichern

  ret

  ;**** Multiplikation 8 x 8 bit unsigned, TEMP4:TEMP3 = TEMP3 x TEMP1 ****

mpy8u:  clr     TEMP4    ;clear result High byte
        ldi     COUNT, 8  ;init loop counter
        lsr     TEMP3    ;rotate multiplier
        
m8u_1:  brcc    m8u_2    ;carry set 
        add     TEMP4, TEMP1  ;add multiplicand to result High byte
m8u_2:  ror     TEMP4    ;rotate right result High byte
        ror     TEMP3    ;rotate right result L byte and multiplier
        dec     COUNT    ;decrement loop counter
        brne    m8u_1    ;if not done, loop more

  ret        ;zurück mpy 8x8

[Sam P. (Gast)]

Ein Pseudozufallsgenerator oszilliert immer. Das liegt in der Natur der 
Sache. Du willst halt nur, dass die Periode lang genug ist, dass es wie 
echter Zufall wirkt. Dazu empfehle ich Wikipedia und andere einschlägige 
Seiten, die dir geeignete Formeln (inkl. der nötigen Konstanten) 
liefern.

[Timm T. (Gast)]

Nu, das hab ich getan, und mit den Konstanten

a = 80
x = 7954

und der Formel

x = a * (x & $FF) + (x >> 8)
erg = (x & $FF)

bekomme ich in einer Simulation auf den PC auch schöne 
8-bit-Zufallszahlen, die sich erst nach laaanger Zeit wiederholen.

Allerdings scheint die Umsetzung auf den AVR nur auf den ersten Blick zu 
funktionieren, zumindest scheint sich die Funktion festzufahren (also 
immer den gleichen Wert zu liefern) oder zu oszillieren (also zwischen 2 
Werten zu springen).

Da das erst nach ettlichen tausend Durchläufen passiert, bin ich mit der 
Simulation im AVR noch nicht weitergekommen.

[Bupf (Gast)]

Nu versteh doch - das wird dein abr immer tun. Woher sollen denn die 
Zufallszahlen kommen wenn  dein avr ständig das gleiche macht und damit 
ständig das gleiche in dem Refistern steht. Für einen echten 
Zufallsgenerator kann man z.b. Das Rauschen einer zdiode nutzen. 
http://www.jtxp.org/tech/xr232web.htm

[MN (Gast)]

lass dir doch die werte auf dem uart ausgeben

[Timm T. (Gast)]

Bupf schrieb:
> Woher sollen denn die
> Zufallszahlen kommen wenn  dein avr ständig das gleiche macht und damit
> ständig das gleiche in dem Refistern steht.

Das es Pseudozufallszahlen sind, und dass die Zahlenfolge sich 
irgendwann wiederholen wird, ist klar.

Ich brauch auch keine Kryptoqualität, ich brauch nur eine ausreichend 
lange Folge, dass sich das Gehirn nicht mehr an die Farbwechsel 
erinnert.

Der Generator erzeugt auch nicht alle möglichen Zahlenfolgen, z.B. kann 
0x0000 nicht vorkommen.

Die Formel x = a * (x & $FF) + (x >> 8) liefert im PC mit den 
angegebenen Startwerten aber zumindest immer wieder einen neuen Wert. 
Auf dem AVR scheint sie irgendwann auf einem Wert hängenzubleiben.

[Ja_Nee (Gast)]

moin

einfaches rückgekoppeltes 24 bit schieberegister

random:
rol RAND1 ;Shift the bits ->Carry
rol RAND2 ;RAND are register or Ram
rol RAND3
BRCC rr2
ldi TEMP,0x87
eor RAND1,TEMP
rr2:
ret

Rand 1- 3 im Ram oder Register - mit irgendwas initialisieren aber nicht 
"0"

mfg

[Timm T. (Gast)]

Achso, die Formel und die Startwerte basieren auf 
Beitrag "Re: Zufallszahlen mit Atmega8"

Ich hab den nur auf 8bit abgespeckt und verwende nur den X-Anteil.

[Yalu X. (yalu) (Moderator)]

Die Unterprogramme rdd_calc und mpy8u scheinen korrekt zu sein, auch
wenn der Zufallszahlengenerator eine Periode von nur 10239 hat.

Timm Thaler schrieb:
> zumindest scheint sich die Funktion festzufahren (also immer den gleichen
> Wert zu liefern) oder zu oszillieren (also zwischen 2 Werten zu springen).

Dann stimmt wahrscheinlich irgendwo anders im Programm etwas nicht.

[Timm T. (Gast)]

Yalu X. schrieb:
> eine Periode von nur 10239 hat

Reicht mir... ;-)

Ich hab jetzt eine Kurzversion mal einige tausend Runden laufen lassen, 
dabei jeweils 128 Zufallsbytes in den RAM geschrieben (siehe Programm im 
Anhang).

Da scheint sich nichts festzulaufen. Dann scheint der Generator erstmal 
in Ordnung zu sein.

Wenn ein Durchlauf der Periode keine Probleme macht, dann dürften die 
folgenden Durchläufe genauso sein, oder? Schließlich sind es ja jedesmal 
dieselben Zahlenfolgen.

[rr (Gast)]

Es gibt Pseudozufallsgeneratoren von nahezu beliebiger Laenge. Siehe 
auch
http://www.ibrtses.com/simulations/lfsr.html

die kann man auch auf einem PC oder AVR in code simulieren.

[Sascha W. (sascha-w)]

@Timm,

also wenn der Zufallsgenerator alleine läuft, dann gibts in dem "nicht 
relevanten Programmteil" folgende Fehlermöglichkeiten:
1) deine im RAM liegenen Werte werden durch eine andere Funktion 
verändert
1a) Speicherstelle wird gezielt überschrieben
1b) Stacküberlauf

2) im Hauptprogramm und in einer ISR wird ein Register verwendet welches 
in der ISR nicht gesichert wird

beides kann erst nach 'sehr' langer Zeit negativ auffallen, wenn der 
Fehler nur an einer kleinen Stelle die Auswirkung zeigt

Sascha

[J. T. (chaoskind)]

MoinMoin,
als kleiner Tip für den Zufall, zumindest hats bei mir mal so geklappt, 
setzt aber voraus einige freie Pins zu haben. Die habe ich als Eingang 
geschaltet, aber in der Luft hängen und einlesen lassen, und diese Werte 
habe ich dann mit denen eines Pseudozufallsgenerators verknüpft.

Das brachte zumindest für mich zufriedenstellende Ergebnisse.

restweihnachtliche Grüße

Chaos