mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Pseudo-Zufallszahlengenerator


Autor: Didlmaus (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich habe diesen Pseudo-Zufallszahlengenerator gefunden:
unsigned int my_rand()
{
        static unsigned int Z;
        if (Z == 0) Z = 0x47110815;

        if (Z & 0x80000000)
        {
                Z<<=1;
                Z^=0x04C11DB7;
        }
        else
        {
                Z<<=1;
        }
        return Z;
}
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! 
:-)

Autor: Landre (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hier mal Pseudo-Zufallszahlengenerator in bunt!

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Didlmaus schrieb:
> Hallo,
> ich habe diesen Pseudo-Zufallszahlengenerator gefunden:
>
> unsigned int my_rand()
> {
>         static unsigned int Z;
>         if (Z == 0) Z = 0x47110815;
> 
>         if (Z & 0x80000000)
>         {
>                 Z<<=1;
>                 Z^=0x04C11DB7;
>         }
>         else
>         {
>                 Z<<=1;
>         }
>         return Z;
> }
> 
> 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

Autor: Winfried (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Juergen (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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!

Autor: Didlmaus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
 // Create a length 624 array to store the state of the generator
 int[0..623] MT
 int index = 0
 
 // Initialize the generator from a seed
 function initializeGenerator(int seed) {
     MT[0] := seed
     for i from 1 to 623 { // loop over each other element
         MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i) // 0x6c078965
     }
 }
 
 // Extract a tempered pseudorandom number based on the index-th value,
 // calling generateNumbers() every 624 numbers
 function extractNumber() {
     if index == 0 {
         generateNumbers()
     }
     
     int y := MT[index]
     y := y xor (right shift by 11 bits(y))
     y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680
     y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000
     y := y xor (right shift by 18 bits(y))
     
     index := (index + 1) mod 624
     return y
 }
 
 // Generate an array of 624 untempered numbers
 function generateNumbers() {
     for i from 0 to 623 {
         int y := 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])
         MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))
         if (y mod 2) == 1 { // y is odd
             MT[i] := MT[i] xor (2567483615) // 0x9908b0df
         }
     }
 }
Müsste ich mal von Pseudocode nach C umschreiben.
Ist für meine Fummellei ein bischen mit Kannonen auf Spatzen geschossen, 
aber trotzdem danke :-)

Autor: Didlmaus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Nicht fuer Verschluesselung oder Gluecksspiel verwenden!

Warum?

Autor: Juergen (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Hagen Re (hagen)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht 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.

Autor: Didlmaus (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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
Z^=0x04C11DB7;
eine 64-bit Konstante
static unsigned long long int my_rand_64_bit()
{
        static unsigned long long int Z;
        if (Z == 0) Z = 0x47110815;

        if (Z & 0x8000000000000000)
        {
                Z<<=1;
                Z^=0x0447C11110D8B175;
        }
        else
        {
                Z<<=1;
        }
        return Z;
}
Würde bloß etwas lange dauern das zu testen :-)

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Didelmaus:

AVR

@Didelmaus: Welcher µC ?

Autor: MeinerEiner (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht 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 ;-)

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Kai Klaas (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht 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

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die schon erwähnte Xilinx Appnote mal anschauen:
http://www.xilinx.com/support/documentation/applic...

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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.