mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik ATmega32: Gleichverteilung von Zufallszahlen verbessern


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

Bewertung
0 lesenswert
nicht lesenswert
Hi zusammen,

ich hab mal einen ATmega32 und einen offenen Single-Ended-AD-Eingang zum 
Generieren von Zufallszahlen benutzt und Matlab auswerten lassen.
Die Bilder zeigen für je >100.000 Zufallszahlen der Breite 8, 16 und 32 
die Wahrscheinlichkeit, dass die Zahl x zwischen 0 und y auftritt (z.B. 
bei 8 Bit liegt die Wahrscheinlichkeit für eine Zahl zwischen 0 und 128 
bei 50%) ... verständlich?
Die rote Strich-Punkt-Linie wäre übrigens die gewünschte ideale 
Gleichverteilung. Es ergibt sich also in einem weiten Bereich eine gute 
Gleichverteilung. Sehr große und sehr kleine Zahlen, also längere Reihen 
von 0en/1en sind leider wahrscheinlicher als der Rest.
Jetzt zu meinen Ideen, um diese Verteilung zu verbessern:
Macht es Sinn, statt dem Single-Ended-Eingang zwei Differential-Eingänge 
zu nutzen? Vergrößert sich dadurch das Rauschen?
Und:
Macht es Sinn, das Gain zu nutzen, um das Rauschen zu vergrößern?

Oder ändert sich nichts an den eingelesenen Werten?

Gruß,
Markus

Autor: Ulrich (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Übliche Weg eine gute Gleichverteilung zu bekommen, ist es die echte 
Zufallszahl mit einer Pseudo-zufallszahl zu verknüpfen, z.B. per XOR.

Ein offener AD Eingang ist übrigens auch keine gut Zufallszahl. Über 20 
ms bekommt man da oft recht viel Korrelation. Ein Schwierigkeit für 
wirklich gute Zufallszahlen ist die Abschirmung gegen Störungen von 
außen.

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So schlecht finde ich die Verteilung der Zahlen z.B. im Bereich 50 bis 
200 bei 8 Bit gar nicht. Ist doch annähernd gleichverteilt, oder?

Will man mehr Zahlen haben, kann man ja 16 Bit breite Zahlen nehmen 
(nutzbarer Bereich: 18.000 bis 52.000). Dann steigt allerdings die 
Verarbeitungsdauer. Deswegen wollte ich einfach schauen, ob sich jemand 
schon mal mit der Zufallszahlenerzeugung über einen offenen AD-Eingang 
beschäftigt hat und Optimierungen weiß.

Gruß,
Markus

Autor: holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Deswegen wollte ich einfach schauen, ob sich jemand
>schon mal mit der Zufallszahlenerzeugung über einen offenen AD-Eingang
>beschäftigt hat und Optimierungen weiß.

Ja, und das ist Bullshit. Der offene Eingang fängt alles ein
was da so rumsendet. Am häufigsten dürften 50Hz Einstreuungen sein.
Dann kommen wohl Handys und andere starke Sender.
In einem abgeschirmten Gehäuse kommt gar nix rein. Das wars
dann mit dem Zufall.

Es gibt da so viele schöne kleine Rauschschaltungen mit Zenerdioden oder 
Transistoren mit umgepolter Basis Emitterstrecke. Such einfach mal
nach Rauschgenerator.

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, werd ich mal schaun. Danke
Hab eben bemerkt, dass meine Graphen auch Bullshit sind. Die y-Achse ist 
blöderweise nichtlinear.

/offtopic
Weiß jemand spontan, wie ich in Matlab schnell und einfach eine 
Wahrscheinlichkeitsverteilung mit LINEARER y-Achse darstellen kann? :-)
/offtopic

Gruß,
Markus

Autor: Joachim B. (jojo84)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
holger schrieb:
> Ja, und das ist Bullshit. Der offene Eingang fängt alles ein
> was da so rumsendet. Am häufigsten dürften 50Hz Einstreuungen sein.
> Dann kommen wohl Handys und andere starke Sender.
> In einem abgeschirmten Gehäuse kommt gar nix rein. Das wars
> dann mit dem Zufall.

Mit Verlaub, das ist auch Bullshit. Ich habe schon sehr gut verteilte 
Zufallszahlen mit einem offenen ADC-Pin bekommen. Denn gerade die 
Tatsache, die du beschreibst (nämlich, DASS er sich jeden Scheiß 
einfängt), ist für diese Anwendung sinnvoll.
Und selbst das Datenblatt der diversen Controller belegt, daß du dich 
auf die untersten Bits nicht verlassen kannst.
Und wenn du jetzt den Pin 8x abfragst, und immer nur das untere Bit 
verwendest und hochschiebst, dann will ich mal sehen, wie du die Zahlen 
vorhersagst! Und mit ein paar Zentimetern Leitung am Pin wirst du auch 
in einem geschirmten Gehäuse keine "Stille" messen...!

Also:
Markus schrieb:
> ob sich jemand
> schon mal mit der Zufallszahlenerzeugung über einen offenen AD-Eingang
> beschäftigt hat

ja, ich zum Beispiel. Ich hab 8x das unterste Bit genommen, und mit der 
Zahl dann wiederum die C-rand()-Funktion gefüttert. Hab leider keine so 
tollen Diagramme mehr, aber die Verteilung war recht gut.

Gruß

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sieht eigentlich besser aus, als man (nicht als
Mathematiker, sondern als Techniker) vermuten würde!!!

Von dieser Seite aus betrachtet, sieht man:

- dass der ADC-Eingang bei dem Testaufbau wunderbar (!)
  im mittleren Bereich liegt. Genausogut könnten geringe
  Leckströme im Chip (je nach Exemplar) eher die Richtung
  Vref oder GND bevorzugen. - Würde ich mich aber nicht
  bei jedem Chip, bei jeder Temperatur und Luftfeuchte
  drauf verlassen!

- Der Eingang ist sehr schön hochohmig! Sonst könnten
  sich dort nicht Spannungen von +/- Vref/3  bilden!
  Würde ich mich aber nicht bei jedem Chip, bei jeder
  Temperatur und Luftfeuchte drauf verlassen!

Daraus kann man schon ein paar Schlüsse für die
Optimierung ziehen!

Autor: holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Mit Verlaub, das ist auch Bullshit. Ich habe schon sehr gut verteilte
>Zufallszahlen mit einem offenen ADC-Pin bekommen. Denn gerade die
>Tatsache, die du beschreibst (nämlich, DASS er sich jeden Scheiß
>einfängt), ist für diese Anwendung sinnvoll.

Das hängt dann aber ganz gewaltig vom Standort ab.
In der Nähe von Umspannwerken, Hochspannungsleitungen
oder Eisenbahnen könnte es da Abweichungen vom Zufall geben.

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ralli schrieb:
> dass der ADC-Eingang bei dem Testaufbau wunderbar (!)
>   im mittleren Bereich liegt. Genausogut könnten geringe
>   Leckströme im Chip (je nach Exemplar) eher die Richtung
>   Vref oder GND bevorzugen. - Würde ich mich aber nicht
>   bei jedem Chip, bei jeder Temperatur und Luftfeuchte
>   drauf verlassen!

Hast Recht. Den Test hab ich letztes Jahr in November gemacht und das 
Projekt dann erstmal wieder beiseite gelegt. Jetzt hab ich das Ganze für 
8 Bit breite Zahlen wiederholt und es sieht bei weitem nicht mehr so 
schön aus. Die Zahlen ziehts mehr Richtung GND und es ist auch 
buckliger. Könnte am Staub auf meinem STK500 liegen ^^.

Ralli schrieb:
> Der Eingang ist sehr schön hochohmig! Sonst könnten
>   sich dort nicht Spannungen von +/- Vref/3  bilden!
>   Würde ich mich aber nicht bei jedem Chip, bei jeder
>   Temperatur und Luftfeuchte drauf verlassen!

Das hatte ich vergessen zu erwähnen: Ich mache es genauso wie Joachim. 
Also unterstes Bit so oft auslesen, wie breit meine Zahl werden soll und 
die Bits einfach aneinander hängen.

Gruß,
Markus

Autor: J.-u. G. (juwe)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus schrieb:
> Die rote Strich-Punkt-Linie wäre übrigens die gewünschte ideale
> Gleichverteilung.

Nein, roten Linien in Deinen Plots zeigen Normalverteilungen. Eine 
Normalverteilung ist etwas völlig anderes als eine Gleichverteilung.

Um die Qualität gleichverteilter Zufallszahlen zu beurteilen bietet sich 
ein beispielsweise ein Histogramm an.

Autor: J.-u. G. (juwe)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das mit Deinen Plots keine Gleichverteilung zeigen, kannst Du auch so 
erkennen:

Es kann doch nicht sein das bei gleichverteilten 32bit Zahlen, die 
Wahrscheinlichkeit für das Auftreten der 0 bei ca. 17% liegt.

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stimmt. Ist auch schon ne Weile her, als ich die gemacht hab und da war 
mir die nichtlineare y-Achse überhaupt nicht aufgefallen. Hatte mich so 
sehr über das Aussehen der Kurve gefreut, dass ich für das Wichtigste 
blind war :-).

Werd es mal mit Histogrammen wiederholen. Wenn es jemanden interessiert, 
kann ich das Ergebnis hier rein posten.

Gruß,
Markus

Autor: Cheeco (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Verteilungsfunktion, die du aufgezeichnet hast, ist in der Tat 
irreführend, weil die Skalierung logarithmisch ist. Wenn du einen Vektor 
mit y mit Zufallszahlen hast, dann kannst du über den "hist(y)"-Befehl 
dir die Verteilungsdichtefunktion (Histogramm) und damit die Güte der 
Gleichverteilung ausgeben lassen, die Balken müssten dann alle gleich 
hoch sein. Falls du die "Signal processing toolbox" besitzt, kannst du 
dir auch spaßeshalber mit "pwelch(y)" schauen ob das Rauschen auch 
wirklich weiß ist, also frei von Zeitabhängigkeiten. Zu beachten ist, 
dass man nur für wirklich große Vektoren zuverlässige Werte bekommt 
(>>10000). Also eigentlich ist die Antwort fast zu blöd, aber normale 
Graphen kann man mit dem "plot"-Befehl bilden?!

Viele Grüße,

Stefan

Autor: Cheeco (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nachtrag:

du hast bestimmt den "normplot"-Befehl benutzt. Probier mal den 
cdfplot(x)-Befehl aus. Dieser müsste in deinem Fall eine schöne linear 
ansteigende Gerade geben (wegen Gleichverteilung).

Stefan

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, sorry für die Verwirrung. Hab nie ein Matlab-Seminar/Kurs gemacht, 
mein Wissen beschränkt sich also auf Learning-by-doing :-)

Cheeco schrieb:
> weil die Skalierung logarithmisch ist

Da muss ich dir widersprechen. Logarithmisch sieht anders aus.

Danke für die plot-Tips (bis auf den "plot"-Befehl, der war mir schon 
bekannt ;-) ).

Schönen Tag,
Markus

Autor: Vlad Tepesch (vlad_tepesch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
J.-u. G. schrieb:
> Um die Qualität gleichverteilter Zufallszahlen zu beurteilen bietet sich
> ein beispielsweise ein Histogramm an.

naja ein Histogram sagt nicht die ganze Wahrheit.
zum Testen von RNGs gibts zum Beispiel die diehard tests


Edit:
Beispiel:
8bit-Histogramm über 1000000 samples
wenn die Zahl immer nur hochgezählt wird, bekommst du ein wunderbar 
gleichverteiltes Histogramm, hast aber noch lange keinen 
Zufallsgenerator

Autor: J.-u. G. (juwe)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vlad Tepesch schrieb:
> J.-u. G. schrieb:
>> Um die Qualität gleichverteilter Zufallszahlen zu beurteilen bietet sich
>> ein beispielsweise ein Histogramm an.
>
> naja ein Histogram sagt nicht die ganze Wahrheit.
> zum Testen von RNGs gibts zum Beispiel die diehard tests
>
>
> Edit:
> Beispiel:
> 8bit-Histogramm über 1000000 samples
> wenn die Zahl immer nur hochgezählt wird, bekommst du ein wunderbar
> gleichverteiltes Histogramm, hast aber noch lange keinen
> Zufallsgenerator

Hast recht. Man kann mit dem Histogramm nur die Verteilung beurteilen, 
nicht die "Zufälligkeit".

Autor: (Gast) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du solltest mal die Autokorrelation prüfen, das scheint mir (zusammen 
mit der Gleichverteilung) der für Dich relevante Test zu sein.
Beides auf Bit-Ebene.

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

Bewertung
0 lesenswert
nicht lesenswert
Hab beides mal für eine reichlich halbe Mio. 8 Bit-Zahlen gemacht (siehe 
Bilder).

Ergebnis: offener AD-Pin ist für Zufallszahlen nur bedingt geeignet. 
Ziemlich schlechte Gleichverteilung (mal ganz davon abgesehen, dass bei 
mir die "0" viel viel zu oft vorkommt). Durch äußere (z.B. Luftfeuchte, 
Staub) und innere (Fertigungstoleranzen) Einflüsse wird sie sich im 
Laufe der Zeit wohl auch merklich nach Vcc oder GND verschieben.
Die Autokorrelation macht das Ganze auch nicht besser. Hat jemand Ahnung 
davon, so einen Graph auszuwerten? Hab Korrelation im Studium zwar mal 
gelehrt bekommen, aber dort nicht wirklich das Ergebnis auswerten müssen 
(war etwas theorielastig).

Werde es für 16-Bit Zahlen wiederholen, bin aber nicht sehr 
optimistisch, dass es da besser wird. Es wird wohl auf nen 
Rauschgenerator rauslaufen müssen 
(http://www.maxim-ic.com/app-notes/index.mvp/id/3469).

Vielen Dank für die konstruktive Diskussion.

Gruß,
Markus

Autor: (Gast) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Auf Bit-Ebene, nicht Bytes...
Und es interessieren nur die Werte um die Mitte rum (kleine 
Verschiebungen um +/- einige Bit), normiert scheint's ja schon zu sein.
Ebenso die Gleichverteilung: Ich meinte wirklich nur die relative 
Häufigkeit von Nullen und Einsen.

Autor: (Gast) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hm, wie passen diese neuen Daten denn mit Deinen alten zusammen (Deine 
ersten Plots), die sahen ja wesentlich gleichverteilter aus...

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mich interessierte aber mehr die Verteilung und Zufälligkeit auf 
Byte-Ebene. Aber weil du es bist ^^.

Markus schrieb:
> Hab eben bemerkt, dass meine Graphen auch Bullshit sind.

Die sollten nicht weiter beachtet werden.

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

Bewertung
0 lesenswert
nicht lesenswert
auf Bit-Ebene mit 500.000 Zufallsbits.

Gleichverteilung sieht sehr gut aus. Autokorrelation zeigt, dass es ein 
periodisches Signal geben muss.

Autor: (Gast) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da Du bitweise ausliest, macht es auch Sinn, die Daten erstmal bitweise 
zu analysieren, auch wenn Du später Bytes draus machen willst.

Interessant.
Wenn die Gleichverteilung so gut ist, frage ich mich, wieso die 
byteweise Gleichverteilung so schlecht ist und warum so viele Null-Bytes 
vorkommen. Seltsam. Sind das die gleichen Daten?

Die Autokorrelation weist auf eine Periodizität von ziemlich genau 40 
Bit Periodenlänge hin (wenn ich richtig abgelesen habe) - auch irgendwie 
seltsam. Möglicherweise fängst Du irgendeine Frequenz ein, die gerade 40 
Bit entspricht.

Hast Du dir mal ein paar hundert Bits einfach so anzeigen lassen? Könnte 
aufschlussreich sein.

Aber insgesamt geb ich Dir recht, scheint kein 'guter' Zufall zu sein.

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

Bewertung
0 lesenswert
nicht lesenswert
Das ist nicht der gleiche Datensatz, weil der alte ja die ganzen Zahlen 
und keine Bits beinhaltet. Hab also extra 500.000 Bits eingelesen.
Das eine Bild zeigt eine Bitfolge von 300 Bits an. Mit viel Phantasie 
könnte man aller 70 Bits eine größere Lücke erkennen.

Ich hab noch eine Messreihe mit Differentialeingang und Vcc als Referenz 
(dürfte beim STK500 nicht geblockt sein, oder?) gemacht. Sieht ein 
bisschen besser aus. Dazu sollte ich aber auch mal die 
Wiederholgenauigkeit testen. Das werd ich aber erst morgen machen.

Autor: (Gast) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sieht nach zu vielen, zu langen 0er- und 1er-Bursts aus, aber da kann 
man sich allzu leicht täuschen.
Irgendwie habe ich das Gefühl, dass Du mit jeder Messung irgendwelche 
anderen Störungen einfängst.
Kannst Du den Autokorrelationsplot noch mehr vergrößern und irgenwie 
anders mit Linien verbinden (stufig oder so, nicht schräg), so dass man 
die einzelnen Verschiebungen besser erkennen kann?

Hm, und mit der Differentialmessung liegt die Autokorrelation im Mittel 
unter 0.5, irgendwie klingt das komisch. Da muss ich noch ne Weile 
sinnieren was das bedeuten kann.

Autor: (Gast) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, habs raugefunden, kommt durch die Normierung auf's Maximum als "1" 
bei ungleich verteilten Bits.

Autor: Ralli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Soll es denn wirklich ECHTER Zufall sein?

Ein offener ADC-Eingang KANN doch nur eine Mischung aus echtem
Rauschen, sowie internen und externen (mehr oder weniger
periodischen, aber kaum ZUFÄLLIGEN) Störungen liefern.

Soll es weiterhin nicht zu aufwändig werden, dann ist doch
eher eine kleine gut geschirmte "Blechdose" mit einer niederohmig 
ausgekoppelten Z-Dioden-Rauschquelle angesagt.

Dafür gibts etliche Anleitungen im WWW.

Ansonsten will ich aber nicht beim Lernprozess "Korrelation"
stören...

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Für einen ordentlichen Zufall wird man um eine externe Beschaltung nicht 
drumherum kommen. Ich war einfach nur mal neugierig, welchen Zufall man 
aus einem AVR rausholen kann.

Die Vergrößerung von der Autokorrelation schick ich heut abend, muss 
dann erstmal auf Arbeit.

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So, hier der stark vergrößerte Ausschnitt der AK. Du hattest Recht mit 
der Periodizität von 40 Bits.

Hab zu verschiedenen Uhrzeiten die Messung wiederholt, um zu gucken, wie 
gut das Signal reproduzierbar ist. Es scheint doch ziemlich stabil zu 
sein.

Mein Programm erzeugt nun in 250 Sekunden 500.000 Bits, also 2000 Bits 
pro Sekunde. Durch 40 Bits geteilt ergibt das für das überlagerte Signal 
eine Frequenz von ... tataaa: 50 Hz. Ein herzliches Willkommen an unsere 
allseits beliebte Netzspannung ^^. War ja irgendwie zu erwarten ...

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mh ... irgendwie hat das Forum die .png-Endung meiner Bilder 
wegoptimiert.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:
Angehängte Dateien:
  • preview image for b1.png
    b1.png
    4,96 KB, 182 Downloads
  • preview image for b2.png
    b2.png
    5,04 KB, 192 Downloads

Bewertung
0 lesenswert
nicht lesenswert
Markus schrieb:
> Mh ... irgendwie hat das Forum die .png-Endung meiner Bilder
> wegoptimiert.

Vielleicht solltest du ja das nächste Mal nicht einen ganzen Roman
als Dateinamen schreiben. ;-)

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Damit wäre der 4. Post im Thread vom guten holger bestätigt und Joachims 
Post widerlegt.

Eignet sich also nur sehr bedingt für einen Zufallsgenerator.

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.