Forum: FPGA, VHDL & Co. Guter Rauschgenerator in VHDL


von Michael (Gast)


Lesenswert?

Hat einer sowas?

Ich habe mich mit Zufallszahlen probiert, finde aber immer wieder 
eindeutige Spektren. In Wiki habe ich auch gegraben, aber das 
durchblicke ich nicht 100%.

Wie baut man einen guten Rauschgenerator - brauche ihn als input für 
Tests.

In MATLAB habe ich einen, aber ich bekomme nur Daten raus, die ich 
abspielen könnte. Das reicht aber nicht.

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

Michael schrieb:
> Wie baut man einen guten Rauschgenerator
Hab ich auch schon mal ausprobiert,das geht mit FPGAs nicht 
zuverlässig...

von Georg A, (Gast)


Lesenswert?

Die XAPP780 hat u.a. einen Zufallszahlengenerator. Das sind zwei 
schnelle, (hoffentlich) freilaufende Ringoszillatoren, die ein FF 
asynchron mit Daten versorgen. Das sorgt für viel Metastabilität und ist 
dann die Basis für ein LSFR. Die Qualität des Zufalls müsstest du halt 
mal anschauen.

von Sigi (Gast)


Lesenswert?

Der Algorithmus Beitrag "Zufalls-Bits in VHDL"
verwendet ein LFSR mit nur einem Feedback (ein XOR),
in Wikipedia gibts aber Tabellen mit mehreren Feedbacks.
24+x reichen für einfaches Rauschen z.B. für VGA-Ausgabe aus.
In Wikipedia findet man Tabellen mit bis zu 512 Bits.

Sigi

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

Georg A, schrieb:
> Die XAPP780 hat u.a. einen Zufallszahlengenerator. Das sind zwei
> schnelle, (hoffentlich) freilaufende Ringoszillatoren
Genau diese Hoffnung trügt, denn von dieser Security-App habe ich meine 
Erkenntnisse, dass damit keine wirklich zufällig verteilten Werte zu 
erhalten sind. Letztendlich wurde dann eine Benutzereingabe zusammen mit 
einem Ringoszillator zur Erzeugung der Zufallszahl zur Abfrage des Keys 
verwendet...

von Simon D. (simon86)


Lesenswert?

Die Lösung heißt MLS Signal (Maximum Length Sequence) oder auch als 
pseudo zufällige Bitfolge bezeichnet... ideal für einen FPGA!

z.B. http://en.wikipedia.org/wiki/Maximum_length_sequence

von Nobbi (Gast)


Lesenswert?

Mit MLS bekommt man aber auch nur Pseudozufallsfolgen, die sich nach 
einer gewissen Zeit wiederholen. Ist einfach zu realisieren mit einem 
Schieberegister, dem richtigen Startwort und Abgriffen.
Wirkliche Zufallszahlen werden da eher schwer realisierbar sein. Ich 
kenne das meist so, dass man ein analoges Rauschsignal abtastet und 
daraus dann die Zufallszahl generiert. Wenn ich das aber richtig 
verstanden habe willst du aus deinen Zufallszahlen ein Rauschsignal 
bauen, also genau umgekehrt ;-).
Gruß Nobbi

von Michael (Gast)


Lesenswert?

Also ich  brauche einen guten Rauschgenerator - die Idee, Zufallszahlen 
zu nehmen, ist eben eine von mehreren Ansätzen.

Dieses "Maximum length sequence" klingt gut, wobei ich auch dort nicht 
direkt sehe, wie ich es bauen muss.

von Nobbi (Gast)


Angehängte Dateien:

Lesenswert?

Das ist wirklich nicht schwer, du musst ein Schieberegister realisieren 
und dann an bestimten Stellen Werte abgreifen, die du ver-exor-st und 
wieder am MSB einspeißt.
Zur Verdeutlichung mal noch ein Bild im Anhang.
Je nachdem wie groß dein Schieberegister ist und deine Abgriffe gewählt 
sind, desto größer werden deine Pseudozufallsfolgen.
Beispielsweise bei einem Register mit 16 Stufen bekommst du die maximale 
Länge der Bitfolge von 65535 Bit und 2048 Bitfolgen.
Solche Verfahren zur Pseudozufallsfolgenerstellung werden beispielsweise 
auch bei der GPS-Übertragung verwendet.
Gruß Nobbi
PS: In dem Bild der Baustein mit dem "e" drin ist ein EXOR Gatter.

von Nobbi (Gast)


Lesenswert?

Nachtrag:
Was ich noch vergessen habe, in der Darstellung kann man gut erkennen, 
dass die Länge der Zufallsfolge von deinem Startwert abhängt. Die 
maximale Länge für ein Schieberegister mit 4 Stufen entspricht 16. Wird 
das Startwort und die Abgriffe optimal gewählt (Wie in der Tabelle die 
erste Spalte) dann bekommt man die maximale Länge.

von matzunami (Gast)


Lesenswert?

und wie komm ich am besten auf das optimale Startwort und die optimalen 
Abriffe? Probieren? bei 128 Bit Schieberegistern kann man dann aber 
schon kanns schön probieren

Gruß
matzunami

von Nobbi (Gast)


Lesenswert?

Ja ich würde einfach probieren ;-). Also ich hatte das mal in einem 
Praktikum in meinem Studium gemacht und da kann man mit probieren schon 
ziemlich gute Erfolge erzielen, aber vielleicht hat hier jemand eine 
etwas professionellere vorgehensweise parat.
Gut vielleicht findest du ja im Netz jemand der schon was ähnliches 
gemacht hat. Vor allem 128 Schieberegisterstufen is schon wirklich ein 
bisschen viel, da brauchst du glaub ich nicht die maximale Länge der 
Pseudozufallsfolge finden.
Gruß Nobbi

von Simon D. (simon86)


Lesenswert?

Nobbi schrieb:
> und da kann man mit probieren schon
> ziemlich gute Erfolge erzielen

1. Mathematik des MLS Signals erarbeiten
2. Matlab Testprogramm schreiben -> verschiedene MLS Längen generieren 
lassen und die FFT berechnen lassen
3. Verilog / VHDL Programm schreiben und testen
4. Implementieren des Programms in den Ziel-FPGA und Testmessung 
durchführen -> Vergleich mit Matlab Simulation
5. Optimieren

das war meine Vorgehensweise gewesen...

von Georg A. (Gast)


Lesenswert?

@Lothar:

Hast du rausbekommen, woran das liegt? Ich könnte mir höchstens 
vorstellen, dass je nach Placement die beiden Ringoszillatoren zu nah 
beieinander liegen und sich synchronisieren.

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

Georg A. schrieb:
> Hast du rausbekommen, woran das liegt?
Nein, wir haben das dann nicht weiter untersucht (wir haben ja den 
Bediener als Zufallselement). Aber sicher wird sich jeder der 
Oszillatoren irgendwie von anderen Routig-Ressourcen und daraus 
eingekoppelten Siganlwechseln beeinflussen lassen....

von Lattice User (Gast)


Lesenswert?

Bei der Erzeugung und Anwendung von Zufallszahlen kann man 2 Fälle 
betrachten:

A. Zufallszahlen für Sicherheitsanwendungen.
B. Zufallszahlen für Simulation.

Zu A:
Da brauchts eine echte Rauschquelle, (Stichwort Vorhersagbarkeit) Das 
kann man im FPGA mit Ringoscillatoren bauen, aber es zu beachten dass 
das nur gut ist wenn die Rate mit der man die Zufallsbits abgreift viel 
viel kleiner als die Frequenz der Oscillatoren ist. Also langsam. Auch 
externe Rauschquellen (Rauschdiode) sind nicht sehr schnell auswertbar.

Zu B:
Dazu gehöhrt meiner Ansicht nach ein Rauschgenerator für Messzwecke. Das 
muss vor allem schnell sein, womit eigentlich nur noch 
Pseudozufallszahlen in Frage kommen.
Generatoren von Pseudozufallszahlen haben habe zwei Nachteile: 1. Hat 
eine Periode, 2. können keine beliebig lange Folge von Nullen oder 
Einsen ausgeben. Wegen 2. bekommt man auch nicht den gewünschten glatten 
Frequenzgang, sondern einen glockenförmigen Frequenzgang. Punkt ein 
führt ausserdem zu Peaks (Grundfrequenz bestimmt sich aus Periode plus 
Oberwellen).
Die Peaks wird man relativ leicht los, wähle eine lange Periode.
Punkt 2 kann man z.B. mit einem sehr lange LFSR bekämpfen, aber das ist 
unpraktikabel, ausserdem woher ein gutes Polynom dafür nehmen.
Einfache den Frequenzbereich den man braucht festlegen und mit einem 
Filter gerade biegen.

Übrigens einfach z.B. einen 8 bit Wert aus dem Zufallszahlengenerator 
auf einen DAC geben reicht nicht aus. Das gibt im Idealfall eine 
Gleichverteilung aller Spannungswerte, also unbrauchbar für Messzwecke.

Alles in allen ein Rauschgenerator in Software oder FPGA ist nicht so 
einfach wie es sich anhört.

von Simon D. (simon86)


Lesenswert?

Lattice User schrieb:
> Alles in allen ein Rauschgenerator in Software oder FPGA ist nicht so
> einfach wie es sich anhört.

das stimmt so weit alles... das MLS Signal muss schon zur Anwendung 
passen...

Lattice User schrieb:
> 1. Hat eine Periode

stimm und muss natürlich mit berücksichtigt werden!

Lattice User schrieb:
> 2. können keine beliebig lange Folge von Nullen oder
> Einsen ausgeben.

die Aussage verstehe ich nicht... Das MLS Signal wird durch ein 
primitives Polynom und einem rückgekoppelten Schieberegister gebildet 
und deshalb kommen die Einsen und Nullen so raus, dass es ein möglichst 
kontinuierliches, gleichmßiges Spektrum ergibt...

Lattice User schrieb:
> 2. bekommt man auch nicht den gewünschten glatten
> Frequenzgang, sondern einen glockenförmigen Frequenzgang. Punkt ein
> führt ausserdem zu Peaks (Grundfrequenz bestimmt sich aus Periode plus
> Oberwellen).

Der Frequenzgang ist bis zu einer bestimmten Frequenz sehr, sehr 
gleichmäßig - dann kommen Einbrüche und glockenartige Effekte zum 
Tragen...

Lattice User schrieb:
> Übrigens einfach z.B. einen 8 bit Wert aus dem Zufallszahlengenerator
> auf einen DAC geben reicht nicht aus. Das gibt im Idealfall eine
> Gleichverteilung aller Spannungswerte, also unbrauchbar für Messzwecke.

Das MLS Signal kann wohl wieder abgetastet werden und dann in den 
Frequenzbereich umgewandelt werden, Shannon Theorem muss natürlich 
beachtet werden... Die Anzahl an Einsen und Nullen ist "fast" identisch 
(Crest-Faktor ist gleich Eins)...

Lattice User schrieb:
> Alles in allen ein Rauschgenerator in Software oder FPGA ist nicht so
> einfach wie es sich anhört.

gebe ich recht... Man muss schon genau wissen was man machen möchte, 
welches Frequenzspektrum man in welcher "Reinheit" braucht und ob das 
Signal eine Periode haben darf...

von Michael (Gast)


Lesenswert?

>Alles in allen ein Rauschgenerator in Software oder FPGA ist nicht so
>einfach wie es sich anhört.
So sieht es aus, ja.

von MXM (Gast)


Lesenswert?


von Nobbi (Gast)


Lesenswert?

@MXM
Na das is ma n Ding. Vielen Dank für den Link.

von Lattice User (Gast)


Lesenswert?

Simon D. schrieb:
> Lattice User schrieb:
>> 2. können keine beliebig lange Folge von Nullen oder
>> Einsen ausgeben.
>
> die Aussage verstehe ich nicht... Das MLS Signal wird durch ein
> primitives Polynom und einem rückgekoppelten Schieberegister gebildet
> und deshalb kommen die Einsen und Nullen so raus, dass es ein möglichst
> kontinuierliches, gleichmßiges Spektrum ergibt...

Hab ich wohl etwas unglücklich ausgedrückt. Ich meinte dass die Länge 
einer aufeinanderfolgender gleicher Ausgabe begrenzt ist. Das folgt 
schon allein aus der Tatsache dass wir es mit endlichen Automaten zu tun 
haben.
Das heisst dass es eine untere Grenzfrequenz gibt, bei einem LFSR ist 
diese nicht allzu niedrig. Dein MLS ist vermutlich besser.

>
> Der Frequenzgang ist bis zu einer bestimmten Frequenz sehr, sehr
> gleichmäßig - dann kommen Einbrüche und glockenartige Effekte zum
> Tragen...

Nicht vergessen, auch nach unten.

> Die Anzahl an Einsen und Nullen ist "fast" identisch
> (Crest-Faktor ist gleich Eins)...

Und genau das hat mit weissem Rauschen und Zufall nichts mehr zu tun.,
aber zugegeben für die Mess- oder Simulationsanwendung ist mein Einwand 
irelevant.

von Sigurt (Gast)


Lesenswert?

Hätte jemand einen solchen Rauschgenerator fertig parat, daß man das mal 
vergleichen kann?

von Andre (Gast)


Lesenswert?

Alle fest definierten Algorithmen - seien sie auch noch so komplex - 
sind keine Zufallszahlen!

von H. G. (Gast)


Lesenswert?

>Alle fest definierten Algorithmen sind keine Zufallszahlen
Das kenne ich ebenfalls so!

>Pseudozufallsfolgen
Bei den Algorithmen, die von einem Startwert abhängen, muss man 
zumindest diesen zufällig erzeugen. Da ist ein Tastendruck eines 
Bedieners ganz gut.

>Na das is ma n Ding. Vielen Dank für den Link.
Die repetition rate von einigen "billion years" klingt ja sehr 
vielversprechend.

von Random (Gast)


Lesenswert?

Wie werden dann Zufallszahlen (ugs oder besser Zufallsvariablen)
eigentlich definiert? (eigentlich Überhaupt nicht, jedenfalls
nicht in der Mathematik!)
Noch nie wurde eine brauchbare Definition vom Zufall selbst
formuliert, aber jeder weiss, was Zufall ist?!

Das Problem ist oft, dass algo. Generatoren schlechter
Qualität sind (d.h. erkennbare Muster liefern) und damit nicht
als Zufallsquelle akzeptiert werden. Natürliche Generatoren
liefern aber oft auch schlechte Qualität (z.B. ungeeignete
Dichte..). Das eigentliche Problem ist, dass man am Besten
nicht wissen will, wie die Zahlen generiert sind, dann glauben
die meissten es handle sich um einen perfekte Zufalls-Generator.

Es gibt aber eine Reihe guter Generatoren, wie z.B.
MersenneTwister (leicht in VHDL implementierbar). Ein solcher
lässt sich bei geeigneter Initialisierung nicht als Künstlicher
erkennen.

von J. S. (engineer) Benutzerseite


Lesenswert?

> Die repetition rate von einigen "billion years" klingt ja sehr vielversprechend.
Ja, aber ein echtes Rauschen hat gar keine repetition rate und ist 
vollständig zufällig. Ausserdem sagt die Xilinx-APP nichts über die 
Verteilung der Werte und die generierten Spektren.

> ich brauche einen guten Rauschgenerator - die Idee, Zufallszahlen,
> zu nehmen, ist eben eine von mehreren Ansätzen
Rauschgenerator und Zufallszahlen sind aber mitunter 2 verschiedene 
Dinge wie es im Beitrag über mir schon anklang.

Beim Rauschgenerator für Messtechnik möchte ich je nach Anforderung 
ein bestimmtes Spektralverhalten, z.B. gleichverteiltes Rauschen haben, 
im Regelfall mit möglichst "allen" Frequenzen, die aber nicht 
identifizierbar sein - bzw hervortreten sollen.

Bei Zufallszahlen sollen und dürfen durchaus Ketten von identischen 
Zahlen vorkommen (siehe Roulette-Effekt) bzw. sie müssen sich erst sehr 
langfristig ausgleichen. Überdies gibt es den Fall, dass Zahlen nicht 
unbedingt gleich häufig kommen müssen/sollen und es ist ein Unterschied, 
ob eine Zahl nach einem Erscheinen dieselbe oder eine reduzierte 
Wahrscheinlichkeit für ein Wiedererscheinen hat. (siehe "mit 
Zurücklegen" -> hypergeometrische Verteilung).

Für solche echten Zufallsfolgen, bei denen früher oder später jede Zahl 
genauso häufig drankommt, Reihenfolge und Startwerte aber nicht 
ermittelbar sein sollen, muss ein Zufallswertgenerator mit einer 
definierten Verteilung kombiniert werden. Ich habe dazu eine Art 
Scrambler gebaut, der eine definierte Folge von Zahlen beliebig 
durchmischen kann und danach zufällig ausgibt. Dieser ist an mehreren 
Stellen durch einen Zufallsgenerator gesteuert.

http://www.mikrocontroller.net/articles/Digitaler_Zufallszahlengenerator_in_VHDL

Das Beste, was ich an echt Zufälligem gefunden habe, sind mindestens 
zwei sich gegenseitig umschaltende Oszillatoren. Diese leiden nicht wie 
die Applikation von Xilinx daran, dass sie sich auf interne 
Schaltvorgänge synchronisieren können. Dies ist nämlich offenbar der 
Fall, wie Lothar bereits vermutete.

http://www.mikrocontroller.net/articles/Digitaler_Rauschgenerator_im_FPGA

von Schröckel (Gast)


Lesenswert?

Juergen Schuhmacher schrieb:
> Das Beste, was ich an echt Zufälligem gefunden habe, sind mindestens
> zwei sich gegenseitig umschaltende Oszillatoren.
> dass sie sich auf interne Schaltvorgänge synchronisieren

Wie wäre es mit einem eigenen PLD, das nur die Oszillatoren enthält?

Dann gäbe es nicht anderes, was beeinflussen könnte, oder doch?

von H. G. (Gast)


Lesenswert?

Random schrieb:
> Wie werden dann Zufallszahlen (ugs oder besser Zufallsvariablen)
> eigentlich definiert?

wichtig ist, dass sie nicht vorhersehbar / vorraussagbar sind. Bei den 
digitalen Systemen läuft immer wieder dieselbe Folge ab, auch wenn man 
sie selber nicht vorrausberechnen kann.

Bei so einem analogen Oszillator kann man davon ausgehen, dass er immer 
wieder anders läuft.

> MersenneTwister
Den Wikiartikel muss man mal lesen. Eine Art Wirbelsturm im Wasserglas. 
Sehr nett finde ich dies hier:
1
Mersenne-Twister braucht eine Aufwärmphase,
2
bis er gute Pseudozufallszahlen ausgibt.
3
Im Zweifelsfall sollte man also etwa
4
800.000 Zufallszahlen generieren lassen,
5
bevor man die Zahlen verwendet.

von Hagen R. (hagen)


Lesenswert?

mal das hier lesen http://de.wikibooks.org/wiki/Zufall:_Mathematik von 
wegen keine Definitionen zu Zufall und Konsorten.

>Bei so einem analogen Oszillator kann man davon ausgehen, dass er immer
>wieder anders läuft.

Und warum kann man davon ausgehen das dieser "zufällig" erscheinende 
Prozess auch wirlich zufällig wäre ? Wo ist der Beweis für diese 
Hypothese ?

Es gibt diesen nicht da er auf physikalischen Annahmen unserer Umwelt 
basiert. Dieser Oszillator läuft "zufällig" an weil er immer von der 
Umgebungstemperatur abhängig ist. Und damit von der Hintergrundstrahlung 
unseres Universums. Nur für diese Strahlung postuliert die Physik die 
Annahme das es keinen deterministisch rechenbaren Weg gibt, um die 
Heisenbergsche Unschärferelation und damit das Ausserkraftsetzen vom 
kausalen Zusammenhang der Ursdache zur Wirkung, für uns nicht mehr 
ersichtlich ist.

Dumm nur das der prozentuale Anteil an diesen Temperaturschwankungen die 
der Oszillator sieht in Bruchteilen durch diese Hintergrundstrahlung 
beeinflusst wird. Es ist also eher so das das Startverhalten dieses 
Oszillators sehr satrk mit den direkt messbaren Verhältnissen seiner 
nächsten Umgebnung korreliert. Und damit eben nicht mathematisch 
beweisbar sicher zufällig ist.

Es wurde die Anforderung der Krypotgraphie an Zufallszahlen angesprochen 
und behauptet das man nur mit echten Zufallsgeneratoren diese Systeme 
wirklich sicher bekommt. Das ist defakto eine vollkommene Umkehrung der 
tatsächlichen Designstrategieen in der Krypotgraphie. Zuallererst gilt 
in der Kryptographie: ALLES muß mathematisch beweisbar sein. Das 
schließt somit nicht deterministische und kausale 
Prozesse/Datenerzeugungen usw. defakto aus, da sie nicht mathm. 
kryptographisch beweisbar sind.

Das führt dann dazu das man mit einem math. bewiesenen Algorithmus wie 
dem YARROW Pseudozufallsgenerator diesen mit echten Zufallsdaten 
initialisiert, als nicht-vorhersagbares-Datenpaket, und dann mit YARROW 
die Unsicherheit in der math. Beweiskette wieder klattbügeln muß, die 
Entropie auf ein gefordertes Maß anhebt. Wenn es anders ginge würde man 
in der Kryptographie auf die Verwendung von echten Zufall liebend gerne 
verzichten. Statt mit echtem Zufall zu arbeiten reicht es nun auch aus 
einfach die Eingaben der Menschen dafür heranzuziehen. Denn jetzt gilt 
nur noch eine Regel an diese Initialisierung und dessen "Zufälligkeit": 
Unvorhersagbarkeit. Alle anderen Eigenschaften von Zufallsgeneratoren 
sind nun irrelevant.

Gruß Hagen

von extraAusgelogged ;) (Gast)


Lesenswert?

ein guter PRNG ist der AES! ;)

von Hans (Gast)


Lesenswert?

>Dieser Oszillator läuft "zufällig" an weil er immer von der
>Umgebungstemperatur abhängig ist. Und damit von der Hintergrundstrahlung
>unseres Universums. Nur für diese Strahlung postuliert die Physik die
>Annahme das es keinen deterministisch rechenbaren Weg gibt, um die
>Heisenbergsche Unschärferelation und damit das Ausserkraftsetzen vom
>kausalen Zusammenhang der Ursdache zur Wirkung, für uns nicht mehr
>ersichtlich ist.

Ich kotze gleich!

von H. G. (Gast)


Lesenswert?

Hans schrieb:
> Ich kotze gleich!

Wieso?

Das ist doch der Vorteil, dass so viele Einflüsse den Zufall 
bestimmen.Welche es sind, ist unwichtig. wichtig ist allein, dass es 
nicht vorhersehbar oder berechenbar ist.

von M.K. (Gast)


Lesenswert?

Gerald H. schrieb:
> Das ist doch der Vorteil, dass so viele Einflüsse den Zufall
>
> bestimmen.Welche es sind, ist unwichtig
Du kannst aber nicht garantieren, dass es gleichverteilt ist.
Wie will man das machen, ohne die Zahlen untersucht zu haben?

von Weltbester FPGA-Pongo (Gast)


Lesenswert?

M.K. schrieb:
> Du kannst aber nicht garantieren, dass es gleichverteilt ist.
> Wie will man das machen, ohne die Zahlen untersucht zu haben?

Wer behauptet, dass zufällige Zahlen gleich verteilt sein müssen? In der 
Natur ist es auch nicht unbedingt so. Im Gegenteil: Es gibt unerwartete 
Häufungen bei einzelnen Werten, die niemals weggehen. Du weist nur 
vorher nicht welche es sind und kannst sie nicht berechnen.

Das ist der wahre Zufall!

von J. S. (engineer) Benutzerseite


Lesenswert?

Hagen Re schrieb:
> Und warum kann man davon ausgehen das dieser "zufällig" erscheinende
> Prozess auch wirlich zufällig wäre ? Wo ist der Beweis für diese
> Hypothese ?

Das ist eine Frage der Definition des Zufalls. Für mich bedeutet das: 
"nicht vorhersehbar" und das ist bei einem von aussen beeinflussten 
System wie dem vorgeschlagenen der Fall. Niemand hat behauptet, dass das 
dann gleichverteilt ist und sich keine Folgen bilden.

Weltbester FPGA-Pongo schrieb im Beitrag #2341404:
> Wer behauptet, dass zufällige Zahlen gleich verteilt sein müssen?

Eben! Man muss das Wort "Zufall" von "Gleichverteilt" trennen.

Und genau deshalb ist es ein Unterschied, ob man auf Zufallsfolgen 
setzt, Rauschen generiert oder gleichverteilte Folgen haben möchte.

Gleichverteilung muss mehr oder weniger aufgezwungen werden, wenn man es 
sicherstellen will, wie ich das mit meinem dem Zufallsfolgengenerator 
nachgeschalteten Mischer tue. Der stellt sicher, dass es eine 
Gleichverteilung der Werte gibt. Die Zufallsfolgen generieren dagegen 
irgendwelche Werte, deren Häufung nicht abschätzbar ist. Immer wieder 
bilden sich andere Folgen, es gibt Häufungen aber auch keine 
Gleichverteilung.

Und genau das kann die Mathematik nicht! Das kann kein Mersenne-Twister 
und auch kein Marsaglia-Algorithmus. Alle sind von ihren Startwerten 
abhängig und die Folgen letztlich vorhersehbar. Sowohl Marsaglia als 
auch der Mersenne bilden zudem in FFTs sichtbare Spektren ab, die sich 
immer wieder widerholen und förmlich korriegiert werden müssen, wollte 
man sie als Rauschgenerator nutzen, der messtechnische Qualität besitzt. 
Es gibt einen Excel-plugin der mit dem Mersenne-Twister Zahlenfolgen 
generiert, anhand dessen man das leicht verifizieren kann.

Diese Erkenntnis hat mich genau dazu gebracht, mich mit äusseren 
Zufallseffekten zu befassen und diese auch zu implementieren, wo ich es 
benötige.

von Peter Eiching (Gast)


Lesenswert?

Na da hast du aber glück... Da hat jemand genau das schon mal gemacht...

Vielleicht ist das was für dich. Scheint mir noch nicht ganz ausgereift
zu sein, jedoch ist es auch nur ein Bericht zum Praxissemester oder so.
Hier wurden aber verschiedene Methoden zur Erzeugung von Zufallszahlen
in einem FPGA getestet. An der Uni Magdeburg haben wir das mal
nachvollzogen und es lief ganz vernünftig. Leider gibt es keine
Beschreibung zur periph. Beschaltung des FPGA und der Autor kann diese
nicht liefern, da es sich um ein Industrieprojekt handelt.

http://www.hs-merseburg.de/~8ckaehle/dateien/ind_B...

von B. (Gast)


Lesenswert?

Hagen Re schrieb:
> Nur für diese Strahlung postuliert die Physik die
> Annahme das es keinen deterministisch rechenbaren Weg gibt, um die
> Heisenbergsche Unschärferelation und damit das Ausserkraftsetzen vom
> kausalen Zusammenhang der Ursdache zur Wirkung, für uns nicht mehr
> ersichtlich ist.

Das postuliert die Physik, genua. Postulieren = Behaupten.

Gut, man kann davon ausgehen, dass die Summer der Strahlungsqzuanten so 
gross ist, dass dort keine Zusammenhänge mehr sichtbar oder gar 
voraussagbar wären. Allerdings stelle ich das bereits für supernovae in 
Frage. Die kann man nämlich durchaus sehen und einen Anstieg annehmen, 
wenn man sowas  beobachtet.

Aber zurück zur Frage:

Hagen, du lässt dich sehr genau zur Kryptografie aus und ich kann auch 
nachvollziehen, was Du möchtest. Die Frage betraf aber einen 
Rauschgenerator und der muss zufällig sein, nicht deterministisch.

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

B. schrieb:
> genua
Auch schön, dort...  ;-)

von J. S. (engineer) Benutzerseite


Lesenswert?

B. schrieb:
> Rauschgenerator und der muss zufällig sein, nicht deterministisch.
Nun ja, er sollte, wenn es ums Messen geht, und dafür setzen wir ihn ja 
meist ein, schon berechenbare Ergebnisse liefern, nämlich gleichförmigen 
Frequenzgang, oder zumindest einen bekannten. Zufall wäre suboptimal.

von Thomas Kölln (Gast)


Lesenswert?

für Messzwecke sollte einer der hier behandelten reichen. Wurde schon 
öfter hier auf µC.net genannt. Einfach mal die Suche benutzen

http://www.hs-merseburg.de/~8ckaehle/dateien/ind_BA/Bericht_Ind.pdf

von Unbekannter (Gast)


Lesenswert?

Also diese Arbeit von der Uni Merseburg finde ich nicht gerade 
"berauschend"!

Einerseits ist die Darstellung des Bearbeiters ein wenig strange:

"clk symbolisiert den Takt" (der clk IST der Takt)
"Rückkopplungspunkte, welche komfortabel  unter [1] entnommen werden 
können." soso, man entnimmt also die Schaltungspunkt, ich dachte immer, 
man entnimmt Informationen und die Chirurgen gfs Organe? Wie soll denn 
die Schaltung funktionieren, wenn man ihr die Knoten klaut?

Zum anderen sind die Codeausschnitte unvollständig, unvollständig 
beschrieben und der Code der angeblich von der Firma Fibotec Fiberoptics 
stammt, ist schlecht und unübersichtlich programmiert:

1: if rising_edge(prbsclk) then
2: x_neu :=((a*x)+c) mod m;
3: prbsreg <= CONV_STD_LOGIC_VECTOR(x mod 2,32);
4: prbs_out <= prbsreg(0);
5: x <= x_neu;
6: end if;

Wofür braucht man hier die Variable x_neu, wenn es eh nur einmal 
benötigt wird und alles in einem getakteten Prozess läuft? Wenn, dann 
bitte Trenneung von getakten Prozessen und ungetakteten. Und was ist 
"M"? Lustig ist die Formulierung "Modulo 2"- Mann da hat die Synthes 
aber schwer zu arbeiten, um das lumpige LSB, auf das der Konstrukt 
hinaus läuft, einzubauen :-)   Ob der Student durchschaut, was er da 
beschrieben hat?


Und es geht munter weiter:

Hier z.B. wird ein LSFR definiert, dass offenbar vollkommen seriell 
läuft, weil es "busy" sein kann. (????)

1: if (rising_edge(clk))then
2: if (i /= (2**tap2)-1) then
3: reg(0) <= reg(tap2-1) XNOR reg(tap1-1);
4: reg(tap2-1 downto 1) <= reg(tap2-2 downto 0);
5: busy <= '1';
6: i:=i+1;
7: else
8: busy <= '0';
9: end

VHDL-Prozesse sind aber niemals wirklich "busy", sondern laufen bei 
korrekter Implementierung parallel ab und bitte schön, wer - ausser 
offenbar der Uni Merseburg - implementiert rückgekoppelte 
Schieberegister sequenziell in Software? Die sind doch winzig und voll 
parallel in den LUTs aufzubauen bei minimaler Fläche. Wahrscheinlich hat 
es der dortige Informatikprofessor höchstpersönlich getippt :-)

Das Ganze schaut mir eher aus, wie "Ich male mal mit MATLAB rum und 
übersetze es dann irgendwie".

----

Was ich total unverständlich finde, ist die Behauptung, dass der 
BBS-Generator angeblich nur auf 5MHz laufen kann, weil die Simulation 
das so sagt und daher wurde der gar nicht erst implementiert. 
******lol******

Wenn der Student das nicht besser durchschaut, ok, aber dann hätte da 
wenigstens der Betreuer von der Firma Fibotec einhaken müssen und es ihm 
erklären können, wie er das bauen muss. Möglichweise braucht die Uni 
Merseburg oder die Firma Fibotec Fiberoptics mal einen guten 
VHDL-Entwickler, der ihr was von Teilparallelisierung in Hardware mit 
look ahead erklärt.

Und selbst wenn man eine Schaltung hat, die auf so komplexem Wege 
arbeitet, dass sie nur mit 5MHz Daten produziert, dann könnte man

a) mehrere Schaltungen auf ein Fifo arbeiten lassen, um die Datenrate zu 
erhöhen und mit z.B. 8x5 = 40MHz Rauschdaten zu haben

oder

b) die Schlussfolgerung ziehen, dass man mit einer anderen Schaltung 
arbeitet, die halt nur 1 eniziges Zufallsbit erzeugt, um dann 16 davon 
parallel zu nehmen, was immer noch kleiner ist, als ein einziger 
Riesengenerator.

Die Arbeit ist wieder mal ein typisches Beispiel, was dabei rauskommt, 
wenn Softwerker an Hardware rumwerkeln und beim Werkeln das eigentliche 
Ziel aus den Augen verlieren.

von Peter Eiching (Gast)


Lesenswert?

Unbekannter schrieb:
> "Rückkopplungspunkte, welche komfortabel  unter [1] entnommen werden
> können." soso, man entnimmt also die Schaltungspunkt, ich dachte immer,
> man entnimmt Informationen und die Chirurgen gfs Organe? Wie

es geht wohl eher darum, an welchen Stellen sinnvollerweise 
(mathematisch berechnet) rückgekoppelt werden kann um eine MLS zu 
erhalten

Unbekannter schrieb:
> Hier z.B. wird ein LSFR definiert, dass offenbar vollkommen seriell
> läuft, weil es "busy" sein kann. (????)

ich hatte genau deswegen mal Kontakt aufgenommen. Der Autor sagte mir, 
dass der Fibolocator mit einer vollen Periode der MLS läuft und deswegen 
das Busy Signal zum Start weiterer Vorgänge im FPGA dient.

Unbekannter schrieb:
> Zum anderen sind die Codeausschnitte unvollständig,

ähm ja... Industrieprojekt. Informier dich mal über die Funktionsweise 
des Korrelations-OTDR. Du wirst nicht viel finden. Evtl. wurde hier 
gekürzt, damit das auch so bleibt.



Abschließend:

Wenn du Studenten, Ingenieure und sogar Professoren derart derb 
kritisierst, sollte wenigstens dein Name, am besten mit mail-Adresse, 
dabei stehen. Nur damit der Interessierte, der evtl. etwas lernen möchte 
sich bei dir melden kann. Man kann von einem Studenten (im Studium) 
keine Leistung erwarten, die ein Ing. mit Jahrelanger Erfahrung bringen 
würde. Nun gut, manche konnten seit der Geburt alles schon.

von Peter Eiching (Gast)


Lesenswert?

Unbekannter schrieb:
> Und selbst wenn man eine Schaltung hat, die auf so komplexem Wege
> arbeitet, dass sie nur mit 5MHz Daten produziert, dann könnte man
>
> a) mehrere Schaltungen auf ein Fifo arbeiten lassen, um die Datenrate zu
> erhöhen und mit z.B. 8x5 = 40MHz Rauschdaten zu haben
>
> oder
>
> b) die Schlussfolgerung ziehen, dass man mit einer anderen Schaltung
> arbeitet, die halt nur 1 eniziges Zufallsbit erzeugt, um dann 16 davon
> parallel zu nehmen, was immer noch kleiner ist, als ein einziger
> Riesengenerator.

schon mal drüber nachgedacht, dass es dann evtl. auch noch 
wirtschaftliche Gründe gibt gewisse Sachen nicht weiterzuverfolgen?!

von Axel (Gast)


Lesenswert?

mein Gott... Jetzt ziehen sich wieder die Oberprofis über Anfängerfehler 
auf... Man kann es doch einfach als "kleines Studentenprojekt" mit 
minderem Erfolg verbuchen. Die Studenten, die ich in unserer Firma 
betreue bringen auch nichts weltbewegendes zu Stande. Mal davon 
abgesehen, dass für so eine Arbeit meist nur 6 bis 8 Wochen Zeit 
bleiben. Manch einer meiner Schützlinge in den letzten Jahren hätte 
solch eine Arbeit nicht hinbekommen.

von J. S. (engineer) Benutzerseite


Lesenswert?

>strange

Nun der Student der HS Merseburg hat eben eine blumige Sprache, man 
sollte da aber nicht alles auf die Goldwage legen, jeder war mal 
Anfänger :-)

Den BBS-Generator kann man in der Tat erheblich schneller 
implementieren, dazu muss man jedoch in erster Linie die "Modulo 
N"-Division geschickt lösen. Mit einem Flash-Divider geht das in einem 
mittelmäßigen FPGA in 4 Takten auf 50MHz, in einem Virtex 6 in einem 
Takt.

Wenn man es aber nicht variiert, sondern einmalig berechnet, kann man in 
der Schleife mit inverser Multiplikation arbeiten und bekommt das mit 
voller FPGA-Taktfrequenz, ganz ohne Verrenkungen. Kann das, dass der 
Student das eben nicht wusste. Die Generation des Datenwortes aus den 
Bits muss freilich parallel geschehen, ansonsten wären das bei 16 Bit 
eben 16 Multiplier und damit entsprechend lange Kombinatorik.

Der Trick ist, solche REchungen wie hier in der BBS paritiell zu 
skalieren, um von der Modulo N wegzukommen und diese auf ein Modulo X zu 
transformieren, das binär läuft. Die falsche Multiplikation, die dabei 
in der nächsten Rechenstufe entsteht, muss antizipiert und durch eine 
weitere Skalierung vorkompensiert werden und so fort. Damit entsteht in 
der Heuptschleife eine simple Rechenkette aus reinen CCMs, deren Werte 
zum Synthesezeitpunkt bekannt sind. Abgesehen von dem jeweiligen 
Rundungsproblem in der nächsten Stufe, hat man dann nur 15 falsche Werte 
für X(t+1) .. X(t+15), die parallel vorliegen und die man noch 
rückrechnen muss, bevor man sie in die Modulo 2 steckt. Dabei steckt fpr 
den zweiten Wert der Skalierungsfaktor einmal drin, für den letzten 15 
mal. Aber auch diese Werte sind zur Synthesezeit bekannt und können 
passend hingerechnet werden. Letzlich zerfällt das Problem in eine reine 
zweidimensionale Additionskette, (einmal in Richtung der 16 Bits, einmal 
in Richtung des Ausgangs), die auf sicher 3-4 Takte @ 70-80MHz gebracht 
werden kann.

Ok,ok, das ist sicher nichts mehr für einen Studenten, aber andererseits 
haben wir zu unserer Zeit an z.T. schwerwiegenderen Mathematischen 
Problemen getüftelt, um sie in SW oder HW umzusetzen.

Komisch finde ich bei der Beschreibung des BBS, dass man bei der 
Matlab-Beschreibung das Pferd von hinten aufzäumt und die N,Q festlegt, 
statt von den Q2 und P2 auszugehen, die die gewünschten Kriterieren 
erfüllen, um dann in die andere Richtung auszurechnen.

Diesen BBS finde ich aber ohnehin nicht so gigantisch, denn er liefert 
sehr simple wiederkehrende Folgen. DAS wäre der wesenstliche Grund, ihn 
für diese App nicht zu implementieren.

> b) die Schlussfolgerung ziehen, dass man mit einer anderen Schaltung
> arbeitet, die halt nur 1 eniziges Zufallsbit erzeugt, um dann 16 davon
> parallel zu nehmen, was immer noch kleiner ist, als ein einziger
> Riesengenerator.
Genau das wurde ja auch getan. Wobei ich vollkommen zustimme:

Die meisten der existenten Generatoren, sind von Softwareleuten gemacht 
und unterliegen den Einschränkungen. In HW lassen sich viele Dinge 
einfacher paralleler Lösen. Ich produziere mit meinem Rauschgenerator 
die Bits auch einzeln, um auf die Datenrate zu kommen.

von Axel (Gast)


Lesenswert?

@J.S.

du scheinst einer der wenigen richtigen Ings. in diesem Forum zu sein.

1. Kritik anbringen
2. Lösung vorschlagen
3. dabei freundlich aber bestimmt
4. dabei nicht (vollkommen) anonym vorgehen

sehr gut!

von Unbekannter (Gast)


Lesenswert?

@Peter Eiching et al.

Es ging mir nicht darum, jemanden runterzumachen, sondern zu 
hinterfragen, ob sich ausgerechnet diese Arbeit als Endlösung der 
Rauschgeneratorfrage eignet, was hier ja anklingt:

Thomas Kölln schrieb:
> Wurde schon öfter hier auf µC.net genannt.
> Einfach mal die Suche benutzen
> http://www.hs-merseburg.de/~8ckaehle/dateien/ind_B...

Gerade weil der "schön öfter genannt wurde" bin ich da etwas kritisch. 
Ich habe auch nicht davon gesprochen, dass die Arbeit schlecht ist, 
sondern nur, dass es "nicht berauschend" sei - es ist eben 
Standardgebätschel auf durchschnittlichem Niveau. Und etwas Kritik 
müssen die Herren schon abkönnen, wenn sie sowas "Publizieren". Konkret 
zu diesem Beitrag oben:

Beitrag "Re: Guter Rauschgenerator in VHDL"

Wenn Dinge nicht veröffentlicht werden sollen, lässt man sie weg und 
zwar so, dass das Dagebliebene verständlich ist oder wird. Wenn das 
busy-Signal für was anderes gedacht ist und nicht zur Erklärung dieses 
Prozesses taugt, dann raus damit.

Ich denke, dass viele Studenten und auch Professoren noch nicht 
verstanden haben, wozu eigentlich solche Arbeiten da sind: Sie sollen 
nicht primär ein Ergebnis liefern, sondern Darstellung, Transparenz und 
Logik beim Studi trainieren und abprüfen und von der Seite ist das SEHR 
mittelmäßig.

Auch vom Ergebnis her ist es schlicht falsch, zu schlussfolgern, ein 
Generator sei nicht anwendbar, nur weil die SIM nicht das liefert, was 
man möchte. Mit genügender Parallelität erzeuge ich für Quellsignals wie 
Rauschen jede gewünschte Bandbreite. Das ist also ein grober Denkfehler. 
Aber auch, wenn etwas wegen wirtschaftlichen Gründen nicht verfolgt 
wird, dann muss das eben so dargestellt werden: Tenor: "Schaltung wäre 
machbar, aber zu gross, zu teuer, daher zur Seite gelegt worden". DAS 
wäre ein wertvolles Arbeitsergebnis. Dass aber aus einem falschen Grund 
heraus zufällig richtig entschieden wurde, ist sicher kein gutes 
Ergebnis.

Zurückkommend auf die Kernfrage würde ich mir wünschen, dass ordentliche 
papers gelinkt werden, wie z.B.:

http://hal-institut-telecom.archives-ouvertes.fr/docs/00/34/72/13/PDF/ICECS_00_Emul.pdf

http://mike-thomson.com/projects/pdf/Mike_Thomson--INDEPENDENT_STUDY_POSTER2.pdf

http://www.ee.ucla.edu/~dongu/pub/papers/tc05_dul98.pdf

von Robert K. (Firma: Medizintechnik) (robident)


Lesenswert?

Unbekannter schrieb:
> Endlösung der Rauschgeneratorfrage
Was wäre denn nun der ultimative Rauschgenerator nach eurer Sicht?

Ein Zufallsgenerator mit gesteuerten sortierten Folgen, wie es oben 
angedacht wurde oder doch einfach eine reproduzierbare Formel?

Ließen sich zwei oder mehr solcher Generatoren addieren, um mehr Zufall 
zu bekommen und die Formel zu verbergen?

von Uwe (Gast)


Lesenswert?

Aus ner Z-Diode und zwei Transistoren kann man schon echten Zufall 
generieren.
guck mal hier :
http://www.jtxp.org/tech/xr232web.htm#schaltung

von Uwe (Gast)


Lesenswert?

Ach ja der STM32F4 hat auch einen echten Zufallsgenerator eingebaut. 
TRNG

von J. S. (engineer) Benutzerseite


Lesenswert?

Da hast Du aber ein bissl zu tun, wenn Du den in VHDL modellieren willst 
;-)

von Christoph Z. (christophz)


Lesenswert?

Uwe schrieb:
> Ach ja der STM32F4 hat auch einen echten Zufallsgenerator eingebaut.

Haben moderne Intel Prozessoren z. B. auch. Dieser alleine Taugt aber 
nicht für Krypto, weil Intel nicht sagen will wie er funktioniert - also 
nicht überprüft werden kann. Was nicht überprüft ist, gilt als unsicher 
und vielleicht als manipuliert.

Einen RAM Tester oder irgendwas anderes zum Testen/Messen kann man damit 
gut bauen.

von Fpgakuechle K. (Gast)


Lesenswert?

R. K. schrieb:
> Unbekannter schrieb:
>> Endlösung der Rauschgeneratorfrage
> Was wäre denn nun der ultimative Rauschgenerator nach eurer Sicht?

IMHO ein analoger Rauschgenerator mit AD-Wandler zum FPGA und im FPGA 
ein Kontrollschaltung (Verteilung im Histogramm, spektrale 
Leistungsdichte) die Verfälschungen durch Parameterdrift im Analogteil 
(bspw. in Richtung Sättigung AD) erkennen und kompensieren.

MfG,

von Maxx (Gast)


Lesenswert?

Christoph Z. schrieb:
> Haben moderne Intel Prozessoren z. B. auch. Dieser alleine Taugt aber
> nicht für Krypto, weil Intel nicht sagen will wie er funktioniert - also

Und das ändert sich, wenn Intel sich dazu äussert? Muss ich der Aussage 
dann glauben oder gibt es dann eine deduktive Möglichkeit? Ich bezweifle 
letzteres zutiefst, denn es wird dir einfach ein nicht deterministisches 
System präsentiert, also Sytem mit nicht vorherbestimmtbaren 
Ergebnissen. Sprich nichts was du auf Richtigkeit/Erwartung prüfen 
kannst.

Dafür müssen immer statistische Methoden angewandt werden um die 
Eigenschaften bis zu einer sinnvollen Genauigkeit zu bestimmen. Dies 
kann ich allerdings auch ohne Angabe zum Verfahren von Intel.

> nicht überprüft werden kann. Was nicht überprüft ist, gilt als unsicher
> und vielleicht als manipuliert.

Und? Hindert es mich daran es als einen von mehreren Faktoren zu nutzen?
Zufall + NichtZufall ist immer noch Zufall.

von Fpgakuechle K. (Gast)


Lesenswert?

> Zufall + NichtZufall ist immer noch Zufall.

??
IMHO trägt Zufall keine Information, ein "modulliertes rauschen" dagegen 
schon, da der NichtZufall bspw durch Optimalfilter extrahierbar ist.

MfG,

von Maxx (Gast)


Lesenswert?

Fpga Kuechle schrieb:
> ??
> IMHO trägt Zufall keine Information, ein "modulliertes rauschen" dagegen
> schon, da der NichtZufall bspw durch Optimalfilter extrahierbar ist.

Es degradiert jedoch nicht die Entropie des Gesamtgebildes.

Auch wenn du die Struktur einer der Quellen kennst und vorausberechnen 
kannst kannst du es für das Ergebnis einer geeigneten Kombination durch 
die Entropie der anderen Quelle nicht.

Beispiel:

Produziere QuelleA eine Zufallszahl [QA(t) = rand] und Quelle B eine 
vorherberechenbare Zahlenfolge z.B. QB(t) = constB. Unter der XOR ist 
die Kombination QAB von QA und QB

QAB(t) = QA(t) XOR QB[t]

In der Entropiebetrachtung erhalten wir für ein XOR

E(FolgeA xor FolgeB) = Max(E(FolgeA), E(FolgeB))

also hier

E(QAB) = Max(E(QA),E(QB)). Da E(QB) in diesem Fall offensichtlich 
schlechter als E(QA) ist bishin zu E(QB):=0 für QB(t):=const gilt

E(QAB) = E(QA)

von Fpgakuechle K. (Gast)


Lesenswert?

Maxx schrieb:
>
> Unter der XOR ist
> die Kombination QAB von QA und QB
>
> QAB(t) = QA(t) XOR QB[t]
>
> In der Entropiebetrachtung erhalten wir für ein XOR
>
> E(FolgeA xor FolgeB) = Max(E(FolgeA), E(FolgeB))

?? Was für den Fall QA(t) = QB(t)

Da x XOR x = 0 ergibt sich für QAB(t) eine Folge von '0'. Die ist nun ja 
nun nicht gerade zufällig.

Damit kann ich
E(FolgeA xor FolgeB) = Max(E(FolgeA), E(FolgeB))
und somit "Zufall XOR irgendwas = Zufall" nicht uneingeschränkt folgen.

MfG

von Maxx (Gast)


Lesenswert?

Fpga Kuechle schrieb:
> ?? Was für den Fall QA(t) = QB(t)
>
> Da x XOR x = 0 ergibt sich für QAB(t) eine Folge von '0'. Die ist nun ja
> nun nicht gerade zufällig.
>
> Damit kann ich
> E(FolgeA xor FolgeB) = Max(E(FolgeA), E(FolgeB))
> und somit "Zufall XOR irgendwas = Zufall" nicht uneingeschränkt folgen.

Wenn QA(t) == QB(t) für alle t bei QA nicht phisikalisch identisch, dann 
ist QA nicht zufällig.

von Fpgakuechle K. (Gast)


Lesenswert?

Maxx schrieb:
> Fpga Kuechle schrieb:
>> ?? Was für den Fall QA(t) = QB(t)
>>
>> Da x XOR x = 0 ergibt sich für QAB(t) eine Folge von '0'. Die ist nun ja
>> nun nicht gerade zufällig.
>>
>> Damit kann ich
>> E(FolgeA xor FolgeB) = Max(E(FolgeA), E(FolgeB))
>> und somit "Zufall XOR irgendwas = Zufall" nicht uneingeschränkt folgen.
>
> Wenn QA(t) == QB(t) für alle t bei QA nicht phisikalisch identisch, dann
> ist QA nicht zufällig.

OK, welche Schlussfolgerungen kann man dann für das angefragte Szenario 
einer Kombination von Pseudozufallsgeneratoren ziehen?

(Frage war: "Ein Zufallsgenerator mit gesteuerten sortierten Folgen, wie 
es oben
angedacht wurde oder doch einfach eine reproduzierbare Formel?

Ließen sich zwei oder mehr solcher Generatoren addieren, um mehr Zufall
zu bekommen und die Formel zu verbergen?")

Die Antwort wäre dann wohl eher Nein? Nicht "mehr Zufall"; sondern 
bestenfalls so gut wie die beste Quelle allein. Und falls es einer 
Quelle möglich wäre sich an die andere zu adaptieren (da bekannter 
Pseudorandomgenerator), ist sogar "weniger Zufall" möglich?!

Dann sollte IMHO nachgeschalter Entropieschätzer zur Überwachung auf dem 
Weg zum perfekten Zufallsgenerator nötig sein.

MfG,

von Maxx (Gast)


Lesenswert?

Fpga Kuechle schrieb:
> OK, welche Schlussfolgerungen kann man dann für das angefragte Szenario
> einer Kombination von Pseudozufallsgeneratoren ziehen?
>
> (Frage war: "Ein Zufallsgenerator mit gesteuerten sortierten Folgen, wie
> es oben
> angedacht wurde oder doch einfach eine reproduzierbare Formel?
>
> Ließen sich zwei oder mehr solcher Generatoren addieren, um mehr Zufall
> zu bekommen und die Formel zu verbergen?")

Das ist nicht Punkt der Betrachtung gewesen.
Diese bestand daraus dennoch den unbekannten vielleicht nicht 
Zufallsgenerator zu einer echten Entropie zu verwenden, denn es kann 
nicht zu einer Degeneration führen, wenn es keine Entropie enthällt, 
jedoch sichert "seinen" Entropieanteil, wenn es eine enthällt.

> Die Antwort wäre dann wohl eher Nein? Nicht "mehr Zufall"; sondern
> bestenfalls so gut wie die beste Quelle allein. Und falls es einer
> Quelle möglich wäre sich an die andere zu adaptieren (da bekannter
> Pseudorandomgenerator), ist sogar "weniger Zufall" möglich?!

Das wurde nicht behauptet.
Weniger ist aber auch nicht möglich, solange die Abbildung kein 
Aborbtionselement/Folge besitzt. Das ist für Folgen mit Entropie nicht 
der Fall.

PRNGs haben eine Entropie von 0. Sie erhalten Ihre "Zufälligkeit" 
alleine durch Ihren Seed und sind aus diesem streng vorhersagbar. Es 
darf hier nicht der Fehler gemacht werden, die Entropie mit der Anzahl 
durch einen Zufall veränderter Bits zu verwechseln.

Ich habe behauptet, dass die Entropie der Kombination einer echten 
Zufallsquelle und eines PRNG nicht geringer ist als die Entropie der 
Zufallsquelle.

> Dann sollte IMHO nachgeschalter Entropieschätzer zur Überwachung auf dem
> Weg zum perfekten Zufallsgenerator nötig sein.

Sowas gibt und kann es nicht geben.
Zu jedem Schätzer, der auf eine endliche Ausgabelänge n die Schätzung 
abgibt, definiere ich dir eine periodische Folge mit der Länge n+1 und 
der Entropie = 0, die dein Schätzer der gleichen Entropie zuordenen 
würde, die er einer reinen Zufallsfolge zuweisen würde.

von Robert K. (Firma: Medizintechnik) (robident)


Lesenswert?

Auch wenn das Thema schon älter ist, folgende Nachfrage:

Verwendet jemand einen solche RG in einem FPGA? Z.B. für die Erzeugung 
von Zufallsfolgen für die Codierung in Sicherheitsbereichen?

von bitwurschtler (Gast)


Lesenswert?

R. K. schrieb:
> Auch wenn das Thema schon älter ist, folgende Nachfrage:
>
> Verwendet jemand einen solche RG in einem FPGA?

Für BIST wird gern PN23 verwendet, bspw. 
https://www.doulos.com/knowhow/vhdl_designers_guide/models/bist_circuits/


> Z.B. für die Erzeugung
> von Zufallsfolgen für die Codierung in Sicherheitsbereichen?

Diese Info wirst du ohne Sicherheitsfreigabe nicht erhalten.

von Strubi (Gast)


Lesenswert?

Moin,

mit einem HW-basierenden Mersenne-Twister und zwei "gut" 
auseinanderlaufenden Oszillatoren kann man auf dem FPGA schon recht 
guten Zufall generieren. Die Frage ist, wie sicher dein System sein 
soll.
Leider spielt fast immer "Security by obscurity" mit, ist das System 
reverse-engineert, ist der Zufall zeitweise (während so einer gewissen 
mittleren "Kohärenzlänge") eben schlecht.

Gruss,

- Strubi

von Robert K. (Firma: Medizintechnik) (robident)


Lesenswert?

D.h. den völligen Zufall gibt es nicht?

von bitwurschtler (Gast)


Lesenswert?

Strubi schrieb:
> Leider spielt fast immer "Security by obscurity" mit,

Im Prinzip ja, allerdings würde ich hier nicht von (scheinbarer" 
Sicherheit durch Verschleierung reden, sondern vom Nicht-Offenlegen von 
Sichherheitsschwächen.


Robert Kuhn tipste:
> D.h. den völligen Zufall gibt es nicht?

Jaein. Es gibt (nahezu perfekten) richtigen Zufall, beispielweise indem 
man den User bittet wild mit der Mouse auf dem Desktop rumzufahren um 
Zufall zu erzeugen (gesehen bei einer älteren PGP Intsallation). Oder 
nicht vom Dritten einsehbare Zustandsvariablen (Beipielsweise 
(allerdings sichtbar) die PID , oder uptime) oder nichtinitialisierte 
RAM-Bereiche. Allerdings ist es bei FPGA-Implementierungen zuveilen 
schwierig den User um Zufalls-Input zu bitten oder variable Inputgrößen 
(bspw Rauschen auf Vcc) zu verwenden die nicht durch Dritte und Scope 
auslesbar sind. Und per se darf es keine nichtinitialisierten Zustande 
im FPGA geben, weil die Initialisierung die Grundvoraussetzung für ein 
deterministische System ist.

von Strubi (Gast)


Lesenswert?

bitwurschtler schrieb:
> Strubi schrieb:
>> Leider spielt fast immer "Security by obscurity" mit,
>
> Im Prinzip ja, allerdings würde ich hier nicht von (scheinbarer"
> Sicherheit durch Verschleierung reden, sondern vom Nicht-Offenlegen von
> Sichherheitsschwächen.
>

Naja, die Schwäche ist die: es kann halt mit einer gewissen 
Wahrscheinlichkeit im wahren Zufall an Stelle X n-mal ein '0'-Bit 
auftreten.

> Robert Kuhn tipste:
>> D.h. den völligen Zufall gibt es nicht?
>

Dazu hat Einstein ja auch mal was dazu gesagt :-)
Wenn Du halt Verfahren und Polynom/Seed kennst, ist der Zufall keiner 
mehr. Auch wenn ein User mit der Maus rumfährt, ist dabei der Zufall 
über ein gewisses Zeitintervall gesehen mies, denn du kannst eine 
ungefähre Vorhersage wie beim chaotischen System treffen, wo der Pfeil 
als nächstes hinspringt. Wenn du also beim FPGA "schnelle" 
Pseudozufallssequenzen mit "langsamem" echten Zufall kombinierst, hast 
du bessere Chance die Sequenz zu erraten, wenn für die nächsten 
zigtausend Werte der echte Zufall in der '0' hängenbleibt. Bei einem 
LFSR-Pseudozufall ist das simpel.
Egal wie gut das Verfahren ist, den perfekten Zufall gibt es spätestens 
dann nicht mehr, wenn jemand eine Methode findet, geeignete Wassermarken 
in deine Zufallskomponente zu injizieren. U.U. ist dann auch das 
Rauschen einer Diode korreliert...

von Robert K. (Firma: Medizintechnik) (robident)


Lesenswert?

bitwurschtler schrieb:
> Robert Kuhn tipste:
>> D.h. den völligen Zufall gibt es nicht?
>
> Jaein. Es gibt (nahezu perfekten) richtigen Zufall, beispielweise indem
> man den User bittet wild mit der Mouse auf dem Desktop rumzufahren

Das wäre aber doch schon ein guter Zufall, denn solche Handbewegungen 
sind im Detail nicht steuerbar und schon gar nicht zu reproduzieren. 
Deshalb kann man sie ja auch nicht fälschen.

Was ist mit der klassischen Variante, mit einem offen ADC einfach 
Laufrauschen zu sampeln und auszuwerten?

von S. R. (svenska)


Lesenswert?

Robert K. schrieb:
> Das wäre aber doch schon ein guter Zufall, denn solche Handbewegungen
> sind im Detail nicht steuerbar und schon gar nicht zu reproduzieren.

Sie sind aber (teilweise) vorhersagbar, denn du kannst nur begrenzt 
chaotische Handbewegungen durchführen: Muskelkraft und Massenträgheit 
sind da begrenzende Faktoren.

Robert K. schrieb:
> Was ist mit der klassischen Variante, mit einem offen ADC einfach
> Laufrauschen zu sampeln und auszuwerten?

Das dürfte mit der Netzfrequenz in der Umgebung korrelieren und ist 
damit auch nicht richtig zufällig.

von J. S. (engineer) Benutzerseite


Lesenswert?

Wenn man die unteren Bits nimmt, hat man schon ein sehr zufälliges 
Rauschen. Man kann auch einen DAC mit 1-Bit-PWM realisieren und mit 
einem Part-Pin über einen Komparator korrellieren, um ihn zu regeln. 
Durch die Regelung wird sichergestellt, dass der Komparator immer den 
richtigen BIAS hat um 50:50 zu modulieren. Statt einen analogen 
Eingangswert zu sampeln, nimmt man nun die Regelung als Wert. Die ist 
extrem empfindlich und zittert um den Mittelpunkt.

Bei allen Schaltungen im FPGA, die irgendeinen analogen Charakter haben, 
muss man aber immer im Auge haben, dass die Stromspitzen in diesen 
Bausteinen dazu führen, dass sich Schwingungen darauf synchen!

von Strubi (Gast)


Lesenswert?

Moin,

S. R. schrieb:
> Robert K. schrieb:
> ...
>
> Sie sind aber (teilweise) vorhersagbar, denn du kannst nur begrenzt
> chaotische Handbewegungen durchführen: Muskelkraft und Massenträgheit
> sind da begrenzende Faktoren.
>

Es gibt auch nette Attacken mit modifizierten HID-Devices ('trojanische 
Maus' mit 8051..). Die erzeugen unbemerkt sehr schlechten Zufall im 
/dev/random.

> Robert K. schrieb:
>> Was ist mit der klassischen Variante, mit einem offen ADC einfach
>> Laufrauschen zu sampeln und auszuwerten?
>
> Das dürfte mit der Netzfrequenz in der Umgebung korrelieren und ist
> damit auch nicht richtig zufällig.

Das ginge ja noch, ekliger ist schon korreliertes Artefaktrauschen vom 
SDRAM oder der CPU. Es soll auch hier Watermark-Attacken über injizierte 
Routinen geben, aber ob die im Wildpark auch so funktionieren wie im 
Labor, ist eher anzuzweifeln.

von Peter Schulz (Gast)


Lesenswert?

Ohne jetzt jeden Beitrag im Detail gelesen zu haben, hier nochmal ein 
paar theoretische Überlegungen mit praktischer Relevanz für 
FPGA-basierte Rauschquellen.

1. Ein rückgekoppeltes Schieberegister liefert eine Pseudozufallsfolge 
mit folgenden Eigenschaften:
1.a) Die Folge ist endlich und wiederholt sich periodisch.
Wenn die dieser Periode entsprechende Frequenz (Kehrwert der Periode) im 
Spektrum sichtbar ist, dann ist eine längere Periode zu wählen, entweder 
durch Herabsetzung der Abtastrate oder durch Verlängerung der 
Zufallsfolge, was mit der Verlängerung des Schieberegisters einhergeht.
1.b) Jeder in dieser Zufallsfolge enthaltene Zahlenwert kommt während 
einer Periode genau einmal vor. Somit sind die Werte gleichverteilt.

2. Die Fouriertransformierte einer Zufallsfolge im Zeitbereich ist eine 
Zufallsfolge im Frequenzbereich. Ein bestimmtes Spektrum kann man 
grundsätzlich also nicht erwarten.

2.b). Ist ein bestimmtes Rauschspektrum erwünscht, z.B. ein 
bandbegrenztes Rauschen, so muss man die Zufallsfolge durch ein 
entsprechendes digitales Filter geschickt werden.

3. Ist eine andere Verteilung  gewünscht, so könnte die Zufallsfolge 
nichtlinear verzerrt/komprimiert werden. Alternativ kann man zwei 
voneinander unabhängige Pseudozufallsfolgen miteinander addieren und die 
Ergebnisse duch 2 teilen (Normieren). Dann ergibt sich eine 
Dreiecksverteilung. Addiert man viele unabhängige Zufallsfolgen mit 
entsprechender Normierung, so nähert man sich einer Verteilung an, die 
der Normalverteilung ähnlich sieht.
3.b) Unabhängig sind die Zufallsfolgen dann, wenn Schieberegister mit 
unterschiedlichen Rückkopplungpunkten gewählt werden. Unterschiedliche 
Startwerte genügen nicht, da man dadurch nur unterschiedliche 
Phasenlagen derselben Zufallsfolgen erhält.

Gruss

Peter Schulz

von Mampf F. (mampf) Benutzerseite


Lesenswert?

Unbekannter schrieb:
> ist schlecht und unübersichtlich programmiert:
>
> 1: if rising_edge(prbsclk) then
> 2: x_neu :=((a*x)+c) mod m;
> 3: prbsreg <= CONV_STD_LOGIC_VECTOR(x mod 2,32);
> 4: prbs_out <= prbsreg(0);
> 5: x <= x_neu;
> 6: end if;
>
> Wofür braucht man hier die Variable x_neu, wenn es eh nur einmal
> benötigt wird und alles in einem getakteten Prozess läuft?

Wie kann jemand, der offensichtlich keine Ahnung hat von VHDL, 
behaupten, es wäre schlecht programmiert? Oo

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

Mampf F. schrieb:
> Wie kann jemand, der offensichtlich keine Ahnung hat von VHDL,
> behaupten, es wäre schlecht programmiert?
Naja, erstens hatte er jetzt über 4 Jahre Zeit, es zu lernen.

Aber tatsächlich ist in diesem Codeabschnitt die Variable komplett 
unnötig. Man muss nur das Verhalten von Signalen in Prozessen verstanden 
haben, dann sieht man, dass
1
if rising_edge(prbsclk) then
2
  x_neu :=((a*x)+c) mod m;
3
  prbsreg <= CONV_STD_LOGIC_VECTOR(x mod 2,32);
4
  prbs_out <= prbsreg(0);
5
  x <= x_neu;
6
end if;
genau das selbe ergibt wie
1
if rising_edge(prbsclk) then
2
  x <=((a*x)+c) mod m;
3
  prbsreg <= CONV_STD_LOGIC_VECTOR(x mod 2,32);
4
  prbs_out <= prbsreg(0);
5
end if;
oder auch exakt das selbe wie
1
if rising_edge(prbsclk) then
2
  prbs_out <= prbsreg(0);
3
  prbsreg <= CONV_STD_LOGIC_VECTOR(x mod 2,32);
4
  x <=((a*x)+c) mod m;
5
end if;

Nur: es haut an dieser Stelle spzielle "Softies" laufend aus der Kurve. 
Und deshalb nehmen sie gern Variablen, weil die so schön "sequentiell" 
reagieren...

Sie nehmen auch ganz gern Porzesse als "Funktionsaufruf-Ersatz" und 
haben so gleich mal 3 Takte Latency an der Backe (x --> pbsreg --> 
pbsreg(0))...

Ich würde das ganz ohne Prozess so schreiben:
1
  x <=((a*x)+c) mod m when rising_edge(prbsclk);
2
  prbs_out <= prbsreg(0);
3
  prbsreg <= CONV_STD_LOGIC_VECTOR(x mod 2,32);
Vermutlich ist der Umweg über das prbsreg sowieso unnötig, denn wenn x 
mod 2 gemacht wird, dann braucht man für so ein einzelnes Bit eigentlich 
keinen ganzen Integer. Und das prbsreg ist im Prinzip nichts anderes als 
das Signal x...
Fazit ist damit das hier:
1
  x <=((a*x)+c) mod m when rising_edge(prbsclk);
2
  prbs_out <= x(0);
Ich behaupte: das kann sogar jemand lesen und verstehen, der von VHDL 
nicht allzu viel Ahnung hat.

: Bearbeitet durch Moderator
von J. S. (engineer) Benutzerseite


Lesenswert?

Lothar M. schrieb:
> Ich würde das ganz ohne Prozess so schreiben:

Damit wird es aber wieder schwieriger, das Design auf Tempo zu bringen 
und es effektiv zu nutzen. Die MUL/ADD Funktion, zusammen mit einer 
unbekannten Modulo-Funktion erfordern ja etliche Takte, wenn man es mit 
speed laufen lassen möchte.
Ich plädiere daher lieber für eine Beschreibung step by step mit 
dedizierten Schritten, die als pipeline läuft. Die produziert dann 
mehrere BBS-Werte parallel, wenn man es im ersten loop richtig 
initialisiert.

Verfährt man nach der weiter oben vorgeschlagenen Methode der skalierten 
Berechnung, um Modulowerte allein durch MUL gfs auch als Primzahl 
ausführen zu können, läuft es auf zwei sequenzielle MULs und etwas 
Paralleles hinaus und man kommt auf eine Länge von z.B. 8 Takten. Dann 
hat man schon mal ein komplettes Byte zusammen. Man muss aber die Frage 
stellen, ob man wirklich nur 1 Bit auswerten will. Die erzeugten Werte 
kann man auch direkt verwerten, wie im Original. Man kann solche Werte 
auch falten.

Aber wie gesagt, BBS ist veraltet und in Digitaltechnik mit LFSR besser 
zu machen. Wen die festen Folgen stören, kann einen Zufallsgenerator 
nehmen, um mehrere Folgen unwillkürlich umzuschalten, wie in meinem 
Artikel hier im Wiki beschrieben.

von Audiomann (Gast)


Lesenswert?

Stefan Stenzel hat in der DSP-GRuppe einen neuen, audiotauglich RG 
vorgestellt. Der liesse sich gfs auch in VHDL machen:

http://stenzel.waldorfmusic.de/post/pink/

von J. S. (engineer) Benutzerseite


Lesenswert?

Ja kann man und gibt es auch :-)

Solche per FIR zurechtgetrimmten Rauscher werden u.a. im Bereich Radar 
und SDR, wo es darauf ankommt, ein "gutes" Rauschen zu erzeugen, das 
aber dennoch vorhersagbar ist, um es sauber wieder abziehen zu können, 
damit die darin versteckten Signale, die der Markierung und Ortung von 
Objekten dienen, erkennbar werden.

Dazu wurden früher auch genau solche LFSR-Rauschgeneratoren bemüht, als 
noch nicht soviel Rechenleistung zur Verfügung stand. Heute geht man 
aber eher den Weg und codiert mehrere skalierte AES-Folgen zusammen. Das 
ergibt auch noch ein gutes "Rauschen", hat aber eine viel höhere 
effektive Kanalbandbreite für die zu transportierenden Signale.

Die sind halt fürs Audio nicht so gut nutzbar und wie schon angedeutet, 
sehr rechenzeitaufwändig. Das Stenzelkonzept hat ja den großen Vorteil, 
sehr sparsam zu sein. Genau genommen besteht es überwiegend aus look up. 
Im FPGA hat man etwas mehr Möglichkeiten, insbesondere, weil man Tempo 
ohne Ende hat, aber gfs RAM sparen möchte. Die Filterung kann man 
trickreich aus anders machen, was in DSPs so nicht geht.

von J. S. (engineer) Benutzerseite


Angehängte Dateien:

Lesenswert?

Hier ist nochmal ein kleines Beispiel:

Ich verwende in meinem Synthesizer mehrere solcher LFSR-Generatoren, 
filtere im FPGA einfacher, aber aus mathematischer Sicht aufwändiger und 
gelange letztlich de facto zu einer Art musikalisch getrimmter "with 
noise". Man könnte es auch "coloured noise" bezeichnen, da es im 
doppelten Wortsinn "gefärbt" ist. Dadurch klingt es je nach Vorfilterung 
melodischer aber in den Obertönen zugleich aggressiver, als die Waldorf 
Synthies :-)

Angehängtes Beispiel: White Noise in A-Moll. Der Filter ist dreikanalig 
auf den Grundwellen. Man hört aber dennoch deutlich die sich periodisch 
durchsetzenden Oberwellen. Jetzt das Rauschen wieder abgezogen, noch 
Hall drauf und fertig ist der Kinderkirchenchor mit "A" und "O" als 
Begleitung :D

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.