Forum: Mikrocontroller und Digitale Elektronik Pseudo-Zufallszahlengenerator


von Didlmaus (Gast)


Angehängte Dateien:

Lesenswert?

Hallo,
ich habe diesen Pseudo-Zufallszahlengenerator gefunden:
1
unsigned int my_rand()
2
{
3
        static unsigned int Z;
4
        if (Z == 0) Z = 0x47110815;
5
6
        if (Z & 0x80000000)
7
        {
8
                Z<<=1;
9
                Z^=0x04C11DB7;
10
        }
11
        else
12
        {
13
                Z<<=1;
14
        }
15
        return Z;
16
}
Das funktioniert ganz gut, aber nach 2^32 Wiederholungen (mit einem 
schnellen Microcontroller sind das nur ein paar Minuten) fängt die Folge 
wieder von vorne an.

Gibt es eventuel längere als 32-bit die sich nicht so schnell 
wiederholen.
Wie kann man die testen?
Ich habe nicht (2^64) / 10 MHz = 58494,24174 Jahre Zeit das zu testen! 
:-)

von Landre (Gast)


Angehängte Dateien:

Lesenswert?

Hier mal Pseudo-Zufallszahlengenerator in bunt!

von Gast (Gast)


Lesenswert?


von Arc N. (arc)


Lesenswert?

Didlmaus schrieb:
> Hallo,
> ich habe diesen Pseudo-Zufallszahlengenerator gefunden:
>
1
> unsigned int my_rand()
2
> {
3
>         static unsigned int Z;
4
>         if (Z == 0) Z = 0x47110815;
5
> 
6
>         if (Z & 0x80000000)
7
>         {
8
>                 Z<<=1;
9
>                 Z^=0x04C11DB7;
10
>         }
11
>         else
12
>         {
13
>                 Z<<=1;
14
>         }
15
>         return Z;
16
> }
17
>
> Das funktioniert ganz gut, aber nach 2^32 Wiederholungen (mit einem
> schnellen Microcontroller sind das nur ein paar Minuten) fängt die Folge
> wieder von vorne an.
>
> Gibt es eventuel längere als 32-bit die sich nicht so schnell
> wiederholen.
> Wie kann man die testen?
> Ich habe nicht (2^64) / 10 MHz = 58494,24174 Jahre Zeit das zu testen!
> :-)

Standard-PRNG (nicht für kryptographische Anwendungen), Periode 2^19937 
− 1
http://en.wikipedia.org/wiki/Mersenne_twister
Dieharder Testbatterie
http://www.phy.duke.edu/~rgb/General/rand_rate.php

von Winfried (Gast)


Lesenswert?


von Juergen (Gast)


Lesenswert?

> http://en.wikipedia.org/wiki/Mersenne_twister

2.5kB RAM fuer einen Zufallszahlengenerator sind wohl etwas viel in 
einem Mikrocontroller.

Vom Prinzip her ist er aber sehr gut geeignet, am Besten kleinere 
Varianten davon (ein paar zig Bytes) mit Diehard testen, bis man was 
brauchbares findet.

Nicht fuer Verschluesselung oder Gluecksspiel verwenden!

von Didlmaus (Gast)


Lesenswert?

1
 // Create a length 624 array to store the state of the generator
2
 int[0..623] MT
3
 int index = 0
4
 
5
 // Initialize the generator from a seed
6
 function initializeGenerator(int seed) {
7
     MT[0] := seed
8
     for i from 1 to 623 { // loop over each other element
9
         MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i) // 0x6c078965
10
     }
11
 }
12
 
13
 // Extract a tempered pseudorandom number based on the index-th value,
14
 // calling generateNumbers() every 624 numbers
15
 function extractNumber() {
16
     if index == 0 {
17
         generateNumbers()
18
     }
19
     
20
     int y := MT[index]
21
     y := y xor (right shift by 11 bits(y))
22
     y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680
23
     y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000
24
     y := y xor (right shift by 18 bits(y))
25
     
26
     index := (index + 1) mod 624
27
     return y
28
 }
29
 
30
 // Generate an array of 624 untempered numbers
31
 function generateNumbers() {
32
     for i from 0 to 623 {
33
         int y := 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])
34
         MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))
35
         if (y mod 2) == 1 { // y is odd
36
             MT[i] := MT[i] xor (2567483615) // 0x9908b0df
37
         }
38
     }
39
 }
Müsste ich mal von Pseudocode nach C umschreiben.
Ist für meine Fummellei ein bischen mit Kannonen auf Spatzen geschossen, 
aber trotzdem danke :-)

von Didlmaus (Gast)


Lesenswert?

>Nicht fuer Verschluesselung oder Gluecksspiel verwenden!

Warum?

von Juergen (Gast)


Lesenswert?

> >Nicht fuer Verschluesselung oder Gluecksspiel verwenden!

> Warum?

Allgemein ist dieser RNG nicht geeignet, wenn man es mit intelligenten 
Gegenspielern zu tun hat. Es ist relativ leicht moeglich, aus den 
Ausgabewerten den Zustand zu berechnen, und dann die weitere Folge 
vorherzusagen. Bei kryptographischen Schluesseln oder z.B. Pokerkarten 
ist das unguenstig.

Mathematisch liegt das daran, dass die Berechnung im 
Zufallszahlengenerator linear ist.

von Hagen R. (hagen)


Angehängte Dateien:

Lesenswert?

LFSR-SG -> Periode 2^63-1, nichts anderes als die Kaskadierung zweier 32 
Bit LFSRs. Nach diesem Beispiel kannst du belieb viele LFSRs 
kaskadieren.

von Didlmaus (Gast)


Lesenswert?

Erst mal danke für die vielen netten Antworten.
Aber alles ziemlich kompliziertes Zeug!

@ Hagen Re (hagen): Welcher µC?

@ alle: Gibt's nix einfaches? anstelle
1
Z^=0x04C11DB7;
eine 64-bit Konstante
1
static unsigned long long int my_rand_64_bit()
2
{
3
        static unsigned long long int Z;
4
        if (Z == 0) Z = 0x47110815;
5
6
        if (Z & 0x8000000000000000)
7
        {
8
                Z<<=1;
9
                Z^=0x0447C11110D8B175;
10
        }
11
        else
12
        {
13
                Z<<=1;
14
        }
15
        return Z;
16
}
Würde bloß etwas lange dauern das zu testen :-)

von Hagen R. (hagen)


Lesenswert?

@Didelmaus:

AVR

@Didelmaus: Welcher µC ?

von MeinerEiner (Gast)


Lesenswert?

Theorie: Könnte man - wenns ein AVR ist - nicht einfach noch nen offen 
hängenden ADC-Pin mit einbeziehen? Der schwebt in der Luft, fängt sich 
"irgendein" Potential ein => "zufälliger" Wert, den man da noch 
mitverwursten kann.

von Mark B. (markbrandis)


Lesenswert?

Man könnte das thermische Rauschen eines analogen Bauteils per 
A/D-Wandler auslesen. Ist bestimmt super um echte Zufallszahlen zu 
bekommen. Gemacht habe ich es freilich noch nie ;-)

von Ralli (Gast)


Lesenswert?

Kommt drauf an, was du willst:

ECHTEN Zufall bekommt man z.B. aus dem Rauschen von Z-Dioden.
Dabei muss die Schaltung aber sehr gut von allen äußeren Einflüssen
geschirmt werden! Also HF- und NF-dicht! Dazu gegehören Drossel-
Spulen, Durchführungskondensatoren, versilberte dicke Messinggehäuse
etc.

ZUFÄLLIG ERSCHEINENDE Signale kann man mit "Linear Feedback Shift
Registers" (LFSR) erzeugen. Die Fa. XILINX hat mal App-Notes
veröffentlicht, in denen LFSRs bis 168 Bit beschrieben werden.
(Dezimal 50-stellig: 10 hoch 33 Jahre bei 10 GHz...)

Der Vorteil ist, dass man selbst vorausberechnen kann, was an "Zufall"
herauskommt, - aber jeder, der es nachbaut, auch!

Verknüpft man mehrere LFSRs miteinander wird es für andere schon
deutlich schwieriger, dies nachzuvollziehen!

Also muss die Verknüpfung gut "abgeschirmt" werden...

Gruß Ralli

von Kai Klaas (Gast)


Angehängte Dateien:

Lesenswert?

Hallo Mark,

>Man könnte das thermische Rauschen eines analogen Bauteils per
>A/D-Wandler auslesen. Ist bestimmt super um echte Zufallszahlen zu
>bekommen.

Damit ist es leider nicht getan. Es geht ja nicht nur darum eine Zahl zu 
erzeugen, von der du vorher nicht weißt, wie sie aussieht, sondern auch 
darum, daß die Zufallszahlen in dem gewünschten Bereich gleichverteilt 
sind. Und das ist bei einer solchen Anordnung eher nicht der Fall, weil 
beispielsweise die Zufallszahl die dem Ruhepegel der Eingangsspannung 
entspricht, viel häufiger vorkommt, als die zu Rauschspitzen gehörenden 
Zufallszahlen.

Man könnte versuchen, daß Wandlungsergebnis so zu interpretieren, daß 
Rauschspitzen, die über dem Ruhepegel liegen eine logische "1" ergeben 
sollen, und Rauschspitzen unter dem Ruhepegel eine logisch "0". Man 
würde dann bei jedem Lesen des ADC ein Zufallsbit erzeugen.

Damit ist es aber leider auch noch nicht getan, da durch einen eventuell 
leichten Versatz des Ruhepegels gegenüber der exakten zugehörigen 
Schaltschwelle im ADC die Nullen und Einsen wieder nicht ganz 
gleichverteilt sind.

Vor einiger Zeit habe ich mal einen Zufallsgenerator wie im Anhang 
aufgebaut. Hier wird das thermische Widerstandsrauschen verstärkt, 
bandbreitenbegrenzt und dann auf einen Schmitt-Trigger gegeben. Die 
Bandbreitenbegrenzung ist sinnvoll, damit tieffrequentes Rauschen nicht 
dominiert und die Schaltung bei Übersteuerung nicht für längere Zeit 
lahmlegt. Mit den beiden Hochpässen erzwinge ich, daß der Komparator 
schnell genung hin- und herschaltet.

Ein nachfolgendes Flip-Flop sorgt für eine Vergleichmäßigung der 
0-1-Verteilung.

Die endliche Slew Rate am Ausgang des MCP601 verhindert, daß der 
Schmitt-Trigger zu schnell umschaltet und das erste Flipflop eventuell 
metastabil wird.

Natürlich ist der Aufbau der Schaltung einigermaßen kritisch. Die 
Signalmasse dieser Schaltung muß vollkommen isoliert sein und darf nur 
an den gezeichneten Anschlüssen mit dem Rest der Schaltung verbunden 
werden. Abschirmung der Schaltung ist ein Muß!

Zwischen dem Auslesen der Zufallsbits sollten übrigens möglichst lange 
Zeitspannen liegen, mindestens 10msec, besser daber deutlich mehr.

Kai Klaas

von Detlef _. (detlef_a)


Lesenswert?

Die schon erwähnte Xilinx Appnote mal anschauen:
http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

Für 63 Bit reicht es, das oberste und das zweitoberste Bit zu XNORen und 
unten wieder reinzuschieben:

uint64_t Z= (Z<<1)|( (~( ((Z<<1)XOR(Z))>>63) )&1);

Die Appnote nennt die 'Taps' bis n=168.

Cheers
Detlef

PS: ungetestet, hoffe ich habe mich bei der Formel nicht verhackt, aber 
die Appnote läßt ja keine Frage offen.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.