suche Lookup Tabelle (asm) weises rauschen

Programmiere einen Pseudozufallsgenerator.

Travel Rec. wrote:
> Programmiere einen Pseudozufallsgenerator.
Geht ganz einfach und heißt LFSR (Linear-Feedback-Shift-Register)

Oder sowas:
http://en.wikipedia.org/wiki/Linear_congruential_generator

Im Attachment 2 LFSRs für WinAVG GCC. Der eine ist ein 32Bit LFSR mit 
einstellbarem Polynom. Der andere ist ein SG-LFSR mit einstellbaren 
Polynomen  und hat eine garantiert maximale Periode von 2^63-2 wenn man 
als Polynome diejenigen des Includes benutzt (Liste aus 1000 nicht 
reduzierbaren Polynomen). Mit 2^63-2 Bits Periode hast du dein 
technisches weißes Rauschen.

Im Grunde basieren beide Implementierungen auf einander. Zu Fuß könnte 
man den LSFR im Ordner SG-LFSR auch aus dem im Ordner LFSR bauen. Sie 
basieren beide auf 32Bit.

Lookup Tabelle ist also unnötig und sie wäre im Vergleich riesig.

Gruß hagen

oder man nimmt einfach die rand() aus der stdlib.h

http://www.nongnu.org/avr-libc/user-manual/group__avr__stdlib.html

Ist ein LCG und der hat wesentlich schlechtere statistische 
EIgenschaften, gerade wenn es um weißes Rauschen geht.

Wenn du einen LCG nimmst und dessen Bit Output in eine Monochrome Bitmap 
umwandelst und dann die Zeilen pixelweise zueinander verschiebst wirst 
du irgendwann ein schönes wiederkehrendes Muster erkennnen. Das wirst du 
mit LFSRs nicht finden.

Gruß Hagen

> Output in eine Monochrome Bitmap umwandelst und dann die Zeilen
> pixelweise zueinander verschiebst wirst du irgendwann ein schönes
> wiederkehrendes Muster erkennnen. Das wirst du mit LFSRs nicht finden.
Diese Behauptung finde ich gewagt.
Wenn du z.B. schlechte/ungeeignete Taps beim LFSR hast, nutzt du nur 
einen kleinen Teil der möglichen Kombinationen aus. Und ein zu kurzes 
LFSR wird dir genausolche Muster wie ein zu schmaler LCG bescheren.

Ich beziehe mich auf LCG nd LFSRs mit gleicher und maximaler Periode. 
Dh. bei den LFSRs sind es immer MLS = Maximum Length Sequence und somit 
math. schon korrekt gewählt. Das bei einem LCG und/oder LFSR mit sehr 
kurzer Periode dieses Verhalten bei beiden auftritt ist klar es tritt 
aber bei LCGs auch bei längen Perioden auf. Deshalb gelten ja LCGs als 
statistisch betrachtet nicht als die bessere Wahl.

Gruß hagen

>@Hagen was hast du mit LFSRs schon gemacht?

Einiges, sie laufen dir ja auch überall über den Weg. Im 
kryptographischen Sinne habe ich mit ihnen am meisten beschäftigt sowohl 
in der Theorie und Praxis. Zb. eben die BasicCards, programmierbare 
Chipkarten benutzten solche LFSRs. Damals ging es darum zu beweisen das 
deren Benutzung zum Schutz der BasicCard vor "illegaler" Benutzung nicht 
ausreichend ist. Kurz: ich habe den Updateschutz der BasicCards v3.x 
geknackt und konnte so die eingebauten Sperren gegen 
seblstmodifizierenden Code aushebeln, eg. jeden beliebigen Maschiencode 
über die BasicCard Software einspielen.
Parallel dazu habe ich das DEC = Delphi Encryption Compendium 
geschrieben, bei dem es auch in kleinen Teilen um LFSRs ging. 
Hauptsächlich "spare LFSRs" mit sehr großen Perioden von 2^128-1 bis 
2^2038-1 Bits.
Naja, und ansonsten trifft man ja auch in vielen anderen Breichen auf 
GF(x) Arithmetik zb. eben CRCs oder Elliptische Kurven Kryptographie in 
GF(m^n) auf MCUs. Ist letzendlich immer die gleiche Mathematik dahinter.
Im Hobby habe ich diese LFSRs auf allen AVR Projekten benutzt die einen 
RNG brauchten, siehe hier in der CodeLib meine Nokia6100 GCLD oder das 
Glühwürmchen Projekt.

Du wählst einfach eines der 32Bit Polynome aus LFSR.inc und schon ist 
die maximale Periode mathematisch garantiert. Falls du noch mehr solcher 
Polynome brauchst so könnte ich den Code auf meiner HD raussuchen und 
weitere berechnen. Ürbigens der Einwand von Lothar ist berechtigt unter 
der Annahme das man eben keine nicht reduzierbaren Polynome für LFSRs 
benutzt, aber das ist eben bei meinen Aussagen nicht der Fall. Alle 
Polynome in LFSR.inc sind nicht reduzierbare Polynome und erzeugen als 
LFSRs MLS. Die effiziente Berechnung solcher Polynome ist ja das worum 
es letzendlich ging bei meiner Arbeit. Und wenn ich LFSRs meine dann 
immer die mit maximaler Länge.

Gruß Hagen

@Lothar:

ürbigens diese Muster der LCGs sind nicht 1 zu 1 sich wiederholende 
Muster, logisch dann wäre es kein LCG mit maximaler Periode. Aber es 
sind definitiv leicht erkennbare und zyklische Muster die man so bei 
LFSRs mit maximaler Periode garantiert nicht finden wird. Konkret ging 
es um 32Bit LFSRs und LCGs bei meinen Untersuchungen. Die Bitmap größe 
schwankte von 512x512 bis 1024x1024 Pixel, also nur ein kleiner 
Ausschnitt des Bit Stromes dieser RNGs.

Gruß Hagen