Hallo zusammen, für mein aktuelles Projekt brauch ich relativ schnell ziemlich viele 8bit Zufallszahlen. Dabei ist die Qualität der Zahlen für mich eher zweitrangig, solange sie gleichverteilt sind. Deshalb hab ich mich hier im Forum etwas umgeschaut, aber so richtig fündig bin ich nicht geworden. Also hab ich allgemein gesucht, was es so an (Pseudo-)Zufallszahlengeneratoren gibt und hab mich da ein bisschen reingesteigert, ist wirklich ein hochinteressantes Thema! Entschieden habe ich mich für einen "additive lagged fibonacci generator" mit Abgriffen bei 16 und 3 (anpassbar). Ich habe nur ein paar sehr einfache Tests in Matlab gemacht (Autokorrelation, FFT, Gleichverteilung über 10^6 Werte). Mit dem Ergebnis bin ich aber ganz glücklich (31 Takte auf ATTiny/Mega), und da das Thema ja immer wieder auftaucht, hab ich das ganze etwas aufgehübscht und stells hier für euch ein. Etwas ausführlichere Infos zu den Eigenschaften und zur Verwendung stehen in rand.c . Insbesondere die Initialisierung ist etwas umständlich und hat momentan einen festen Seed. Es muss sich da also jeder selbst was überlegen. Irgendwann werd ich das noch universeller machen. Besonders zur Periode, bis sich die generierte Zahlenfolge wiederholt, bin ich mir bei meinen Standard-Parametern nicht sicher. Wenn man in rand.c die defines ( RANDSIZE / RANDTAP ) auf ( 17 / 5) stellt, sollte die Periode nach meinem Verständnis > 2^23 sein. Ein Durchlauf braucht dann 36/37 Takte, allerdings steigt auch der Speicherbedarf auf 18 Byte. Wer z.B. auch 34 Byte über hat, darf sich z.B. bei (33 / 13 ) schon auf 2^39 Werte freuen, bis die Zufallszahlen von Vorn anfangen (bei immer noch 36/37 Takten Durchlaufzeit). Wie ich beim Stöbern gesehn hab, gibts hier ja schon einige, die von der Theorie deutlich mehr Ahnung haben als ich nach ner knappen Woche wildes Rumprobiern und lesen. Über Feedback würd ich mich von der Seite und auch sonst sehr freuen! Gruß, Alex
Da gibt es aber doch einfachere Möglichkeiten. Ich glaube Hagen hat hier auch irgendwo einen LFSR PRNG reingestellt. Einen LCG PRNG habe ich mal selber realisiert. Beides sehr einfache Realisierung.
Ja, da hast du natürlich recht. Ich glaub den LCG von Hagen hab ich auch ausprobiert. Da war mein Generator schon fast fertig. Gottseidank war der LCG n gutes Stück langsamer :-P Den hab ich auch in Matlab ausprobiert und die Verteilung ist deutlich weniger zufällig. Die FFT hatte hier ne deutliche Kuhle. Das passt auch ganz gut zu dem, was ich so über LCG gelesen hab. Die Zufallszahlen tendieren dazu, bei niedrigeren Bits eine sehr schnelle Periode zu erzeugen. Ein LFSR erzeugt zwar deutlich bessere Zahlen, müsste aber auch relativ lang und damit langsam sein wenn man ähnlich große Gesamt-Perioden will. Im Prinzip ist der Generator hier auch aus Überlegungen zu nem LFSR entstanden. Mein erster Gedanke war, man müsste doch genausogut 8 LFSRs vertikal anordnen können, so dass das Byte 1 die ersten Bits von 8 LFSRs darstellt, das nächste Byte Bit2 dieser 8 LFSRs. Anstatt die Bits eines SR zu verschieben kann man dann genausogut mehrere Zeiger drüber wandern lassen und ein XOR zwischen zwei Byte kostet genauso viel wie eins zwischen zwei einzelnen Bits. Damit hätte man je nach SR-Länge evtl. sogar weniger Rechenaufwand um statt einem Bit gleich ein ganzes Byte zu erzeugen. Einziges Problem: nach dem die vollkommen synchron laufen, hatte ich Angst, dass die einzelnen Bits irgendwie korrelieren. Ab dem Zeitpunkt hab ich dann angefangen zu suchen und entdeckt, dass ich mal wieder bekanntes neu erfunden habe ^^ Der nächste Schritt ist dann ALFG, bei dem das Xor durch ein Add ersetzt wird. Der Code ist eigentlich nur wegen der Kommentare und der Parametrierbarkeit so groß geworden, die erste funktionierende Version hatte irgendwas um 20 Zeilen. Der Speicherverbrauch ist natürlich ein echtes Argument, spielt aber bei mir keine große Rolle (AtXMega). Ansonsten sollten die Zahlen aber eine wesentlich bessere Qualität haben als ein LCG bei weniger Rechenaufwand. Gruß, Alex
Alexander v. Grafenstein schrieb: > Mein erster Gedanke war, man müsste doch genausogut 8 LFSRs > vertikal anordnen können, so dass das Byte 1 die ersten Bits von 8 LFSRs > darstellt, das nächste Byte Bit2 dieser 8 LFSRs. Anstatt die Bits eines > SR zu verschieben kann man dann genausogut mehrere Zeiger drüber wandern > lassen und ein XOR zwischen zwei Byte kostet genauso viel wie eins > zwischen zwei einzelnen Bits. Aber diese Annahme ist in Assembler schlicht falsch. Ein LFSR das breiter als 1 Byte ist lässt sich sehr schnell in wenigsten Operationen schieben. Das geht weil die 1 Bytes Shift Operationen das Überlaufbit in das Carry Register laden und der nächste Schiebebefehl dieses Bit als Most/Lowest Significant Bit rein schiebt, je nach Schieberichtung. Desweiteren, die Mathematik deiner "kaskadierten" 8Bit-LFSR ist nicht identich zu deinem LFSR mit 64 Bit Breite. Deren maximale Periode sollte minimal nur 2^8-1 betragen entgegem einem echten 64 Bit LFSR mit maximal 2^64-1 Periode. Du kannst das sogennante SR-LFSR (Self Shrinking LFSR) benutzen bei dem man 2 LFSRs zusammenschaltet. Das geht dann so: das 1. LFSR erzeugt einen Bitstrom und das 2. LFSR auch. Das Ausgangsbit des 2. LFSR bestimmt ob das Ausgangsbit des 1. LFSR benutzt wird oder übersprungen wird. Ganz klar ersichtlich ist nun das nur ca. jedes 2. Bit des 1. LFSR rauskommt, ergo die Laufzeit sich verdoppelt, im Gegensatz zu einem LFSR mit doppelt so breitem Register. Anderseits ist dieses LFSR auch doppelt so langsam da doppelt so breit. Angenommen 32Bit LFSRs als SR-LFSR gekoppelt ergibt ^63-1 Periode. Ein 64 Bit LFSR ergibt dagegen 2^64-1 Periode. Man gewinnt also nichts mit einem SR-LFSR auf AVRs. Nun, die meisten LFSR Implementierungen auf AVRs erzeugen pro Durchlauf 1 Bit. Das liegt an ihrer sehr kompakten Implementierung. Würde man bei einem 8Bit LFSR aber mit einer Tabelle im FALSH aus 256 Bytes bestehend arbeiten (wie bei CRCs auch) dann erzeugt dieser Code pro Durchlauf 8 Bits und das mit ganz wenigen Befehlen (ca. 8 takte). Schneller gehts meistens nicht kostet aber FLASH Speicher. Gruß Hagen
Hallo Hagen, freut mich, dass du dich hier gemeldet hast :) Hagen Re schrieb: > Alexander v. Grafenstein schrieb: >> Mein erster Gedanke war, man müsste doch genausogut 8 LFSRs >> vertikal anordnen können, so dass das Byte 1 die ersten Bits von 8 LFSRs >> darstellt, das nächste Byte Bit2 dieser 8 LFSRs. Anstatt die Bits eines >> SR zu verschieben kann man dann genausogut mehrere Zeiger drüber wandern >> lassen und ein XOR zwischen zwei Byte kostet genauso viel wie eins >> zwischen zwei einzelnen Bits. > > Aber diese Annahme ist in Assembler schlicht falsch. Ein LFSR das > breiter als 1 Byte ist lässt sich sehr schnell in wenigsten Operationen > schieben. Das geht weil die 1 Bytes Shift Operationen das Überlaufbit in > das Carry Register laden und der nächste Schiebebefehl dieses Bit als > Most/Lowest Significant Bit rein schiebt, je nach Schieberichtung. Ich dachte, mir wär klar, wie das funktioniert. Ich beschreibs nochmal mit meinen Worten, evtl. kannst du mir dann sagen, ob ich da falsch liege, oder ob man den Ablauf auch geschickter implementieren kann. Nehmen wir ein 32bit SR an, dann mach ich erstmal 4 shifts mit carry. Danach hol ich mir an den gewünschten Tap-Positionen die Bits raus und verknüpfe sie untereinander mit XOR. Das Ergebnis schreibe ich an Bit-Position 0. Das ganze wiederhole ich 8mal. Bei jedem Durchlauf fällt ein Bit raus, so dass ich am Schluss 8bit beisammen habe. Passt das soweit? Hagen Re schrieb: > Desweiteren, die Mathematik deiner "kaskadierten" 8Bit-LFSR ist nicht > identich zu deinem LFSR mit 64 Bit Breite. Deren maximale Periode sollte > minimal nur 2^8-1 betragen entgegem einem echten 64 Bit LFSR mit maximal > 2^64-1 Periode. Da vermute ich, dass du mich missverstanden hast. 8bit-LFSR kommen bei mir nirgends vor. Das wäre auch bei der Autokorrelation und der FFT aufgefallen. Ich beschreibs nochmal anders: Bei z.B. 16 verwendeten Bytes habe ich 16bit-LFSR, davon aber gleich 8 parallel. Das Byte n entspricht dabei nicht dem n-ten 8bit-SR, sondern enthält die n-ten Bits aller 8 SR. Will ich z.B. bit16 und bit13 jedes SR XOR-verknüpfen und wieder rein schieben, kann ich Byte16 und Byte13 ver-XOR-en und habe damit das XOR gleich für alle 8 SR erledigt (Den Gedanken hab ich mir bei Peter Danneggers Entprellroutinen abgeschaut). Jedes 16bit-SR spuckt mir jetzt ein Bit aus und das direkt in einem gemeinsamen Byte. Ich habe also immer 8 LFSR mit identischem Polynom aber (hoffentlich) verschiedenem Seed. Erst mal noch nicht optimal, da sind Korrelationen der einzelnen Bits ja fast schon vorprogrammiert. Die nächste Idee ist also, die einzelnen LFSR zu verknüpfen. An dem Gedankengang, wie das sinnvoll zu machen ist, bin ich dann gescheitert. Jemand anderes (wer genau hab ich nicht rausgefunden) hat das anscheinend durchstiegen und ist zu dem Schluss gekommen, dass ein Ersetzen des XOR durch ein ADD (entspricht einem XOR mit Übertrag) gute Eigenschaften ergibt (Alternativ würden auch - und * funktionieren, mit anderen Eigenschaften). Die Periode ist zwar weit von dem entfernt, was ein langes (8*16)bit LFSR erzeugen würde, aber gegenüber den 2^16-1 der Einzel-LFSR verbessert sie sich anscheinend noch ein wenig. Zur Veranschaulichung finde ich die Seite http://www.phy.ornl.gov/csep/CSEP/RN/NODE20.html ganz hilfreich, auch wenn da die Herleitung sehr knapp und aus einer komplett anderen Richtung kommt. Hagen Re schrieb: > Nun, die meisten LFSR Implementierungen auf AVRs erzeugen pro Durchlauf > 1 Bit. Das liegt an ihrer sehr kompakten Implementierung. Würde man bei > einem 8Bit LFSR aber mit einer Tabelle im FALSH aus 256 Bytes bestehend > arbeiten (wie bei CRCs auch) dann erzeugt dieser Code pro Durchlauf 8 > Bits und das mit ganz wenigen Befehlen (ca. 8 takte). Schneller gehts > meistens nicht kostet aber FLASH Speicher. Für 8bit-SR ist das einleuchtend, dass sind ja einfach alle möglichen Zustände abgewickelt, die dann nur noch durchlaufen werden müssen. Aber ne Periode von 2^8-1 ist dann nicht so das ware. Oder lassen sich damit auch größere LFSR beschleunigen? Das fände ich dann wieder hochspannend. Kleine Anmerkung noch am Rand: die 31 Takte sind incl. Funktions-Overhead und Zuweisung, also der Code 'wert = rand();' wird in 31 Takten ausgeführt. Gruß, Alex
>Ich dachte, mir wär klar, wie das funktioniert. Ich beschreibs nochmal >mit meinen Worten, evtl. kannst du mir dann sagen, ob ich da falsch >liege, oder ob man den Ablauf auch geschickter implementieren kann. >Nehmen wir ein 32bit SR an, dann mach ich erstmal 4 shifts mit carry. >Danach hol ich mir an den gewünschten Tap-Positionen die Bits raus und >verknüpfe sie untereinander mit XOR. Das Ergebnis schreibe ich an >Bit-Position 0. Das ganze wiederhole ich 8mal. Bei jedem Durchlauf fällt >ein Bit raus, so dass ich am Schluss 8bit beisammen habe. >Passt das soweit? Nein ;) Du teilst die 32Bit des LFSR auf 4 Bytes auf. Dann schiebst du das 1. Byte, ein Bit wird rausgeschoben und landet im CARRY. Dann schiebst du das 2. Byte, das CARRY wird reingeschoben als neues Bit und im CARRY Register landet das rausgeschobene Bit. Das geht so weiter mit dem 3. und 4. Byte. Das CARRY entheält danach den alten Bitzustand des 32Bit Registers das raus geschoben wurde. Das schieben geht links wie auch rechts. Nun an Hand des CARRY Registers entscheidest du ob du danach die 4 Bytes = 32Bit mit dem Polynom des LFSRs ver'XOR'en mußt. Fertig ist die Erzeugung von 1 Bit. Kosten tut es, mal vom Overhead der Initialisierung der 4 Bytes in Register, 4x Shifts = 4 Takte, 1 Branch = 2 Takte, in 50% aller Fälle dann 4x XOR = 4 Takte mit dem Polynom das ebenfalls schon in Registern steht. Also ca. 8 Takte für 1 Bit und 8 Register. >Ich habe also immer 8 LFSR mit identischem Polynom aber (hoffentlich) >verschiedenem Seed. Und exakt das ist der mathematische Worstcase den man eben nicht benutzen sollte. Die Bitfolge deiner 8 LFSR mit gleichem Polynom aber unterschiedlichen Seed's ist immer gleich, egal mit welchem Seed. Betrachte es mal anders: du erzeugts deine 255 Bits aus dem 8Bit LFSR = 2^8-1 Periode wenn das Polynom ein nicht reduzierbares (irreducible) ist. Dein Seed ist dann quasi nur ein Offset in diesen Bitstrom. Nun machst du mit deiner XOR Operation nichts anders als eine Multiplikkation im GF(2) (Galois Field zur Basis 2, die math. Grundlange für LFSRs und CRCs). Nimm deine eine Bitfolge und multipliziere sie 8 mal mit einem beliebigen Offset in diese Bitfolge zueinander. Dann wirst du eben immer nur noch eine maximale Periode von 2^8-1 = 255 Bits haben. Denn alle deine 8 LFSRs wiederholen sich nach 255 Bits. Wenn du also deine 8 LFSR Bitfolgen mit gleichem Polynom und unterschiedlichen Seed als 255 Bitfolge ver'XOR'st dann hast du exakt die Bitfolge erzeugt (einmalig) die sich permanent wiederholen wird bei deinem Konzept. Würdest du dagegen 8 unterschiedliche Polynome benutzen dann bist du mit deiner Methode bei den Gold Codes -> http://de.wikipedia.org/wiki/Linear_r%C3%BCckgekoppeltes_Schieberegister#Gold-Folgen Schau dir mal an wie lang die Periode dieser Gold Codes ist -> 2^m-1. Egal wie ich es drehe und wende, dein Vorgehen ist wenig sinnvoll. Du solltest einfach ein größeres LFSR benutzen statt dessen Größe mit vielen kleinen LFSRs zu ereichen. Erstens ist das sowieso langsammer im fertigen Program (wenn man Assembler benutzen kann oder das CARRY zugreifen kann). Zweitens ist es mathematisch sinnvoller für dich da du nicht so einfach auf Grund fehlendem Wissens in die Irre läufst. Ich kenne nur eine Methode die mathm. bewiesen eine größere Periode im Gesamten erzeugen, die JPL Folgen die auch in den SR-LFSRs (Self Shrinking) benutzt werden. Bei Wikipedia gleich nach den Gold Codes. Du siehst aber auch die Rahmenbedingungen für JPL Folgen, aus gutem Grund wohlgemerkt, und das Resultat der sich maximal ergebenden Periode. Wie ich es im vorherigen Posting schon sagte, mit gleichem Aufwand für ein großes LFSR sind die JPL Folgen schlechter, sie haben nur eine kürzere Periode. Der einzige Vorteil und Grund warum JPL Folgen entwickelt wurden ist das die Periode nicht mehr 2^x-1 ist sondern kürzer mit( 2^n-1)*(2^m-1). Also angenommen ein 8 und 9 Bit LFSR haben 255 und 511 Bit Periode = 130305 Bits. Ein 17 Bit LFSR hat 131071 Bit Periode. Beide LFSR Typen benötigen 17 Bit an Speicher, da beide LFSR Typen Operationsgleich sind und gleiche Menge Speicher benötigen (sie basieren ja beide auf exakt gleichen Operationen) macht es überhaupt keinen Sinn, wenn es nicht um die max. Periode geht, nicht auf ein einziges großes LFSR zu setzen. Nun, egal ob du deine LFSRs mit XOR oder anderen Operationen verküpfst du musst dir sicher sein das es mathematisch auch einen Sinn macht und eine wirklich mathm. beweisbare längere Periode dadurch entsteht, von der Qualität des Pseudozufalls mal ganz abgesehen. > Oder lassen sich damit auch größere LFSR beschleunigen? Nein. Wie ich es eben gerade erläutere sind LFSR schon Algorithmen die normalerweise auf fast jeder Hardware enorm schnell ausgeführt werden. Die Zerlegung eines LFSR in kleinere LFSRs kann keinen Vorteil in der Performance bringen und wird mathm. schlechteren Zufall erzeugen. Es macht keinen Sinn. Gruß Hagen
>ist zu dem Schluss gekommen, dass ein Ersetzen des XOR durch ein ADD >(entspricht einem XOR mit Übertrag) gute Eigenschaften ergibt Hm, denke ich nicht. ADD ist in GF(2) die XOR Operation und damit quasi identisch. ADD in GF(2) angewendet ist undefiniert und math. falsch, gerade weil das CARRY (Überlauf) mit eingerechnet wird, aber eben falsch aus Sicht der Domain GF(2). Wenn dann würde ich MUL, Multiplikation, empfehlen, da weiß ich das einige Verschlüsslungsverfahren wie zB. IDEA diese Operation auch in GF(2) benutzen. MUL ist in GF(2) eine komplexe Operation die eine Asymmetrie in der Berechnung einführt. Dh. man kann von einem gegebenen Resultat nicht zurückrechnen auf den Input (wie eine Hash Funktion in der Kryptographie). Poblematisch ist aber der math. Beweis das eine Änderung deiner LFSRs auf diesem Wege auch wirklich was verbessert. Gruß Hagen
Wenn du deine LFSRs beschleunigen möchtest dann geht das bei großen LFSR mit sogennaten Sparse-Polynomen. Also angenommen wie bauen ein LFSR mit 128 Bit (2^128-1 Periode) aus 16 Bytes zusammen. Unser Polynom ist ebenfalls 16 Bytes groß. Nun benutzt man Sparse-Polynome (dünn besetze Polynome also wenige Taps) deren Taps (Bits im 16 Bytes POlynom-register) nur aus 2-3 Bits = Taps besteht. Diese Taps befinden sich zb. alle im untersten Byte unseres Polynomes. Nun kannst du die Operation in der das Polynom mit dem LFSR ver'XOR'ed wird beschleunigen. Denn du musst nu 1 Byte XOR'en statt 16 Bytes. Eine solches LFSR mit variabler programmierbarer Periode habe ich schon für kryptographische Zwecke programmiert. Wenn du PASCAL (Delphi) lesen kannst dann schau dir das Attachment an. Gleich zu Anfang im Source findest du eine Tabelle mit den Sparse-Polynome die benutzt werden. Übrigens, dieser LFSR benutzt die Lookup Tabellen Methode die ich oben schojn angesprochen habe, mit dieser Methode kannst du wirklich dein LFSR beschleunigen da man Byte-weise statt Bit-weise rechnen kannst, also gleich 8 Bits pro Durchlauf erzeugt. Diese Wordbreite kann größer sein zb. 2 Bytes oder 4 Bytes auf 16Bit oder 32Bit CPUs. Entscheidender Nachteil ist die Lookup Tabelle dabei. Bei 8 Bits sind es 256 Bytes, bei 16 Bits sind es schon 2^16 16Bit Wörter die diese Tabelle aufnehmen muß, also 128kByte. Gruß Hagen
Hmm ok, ich seh, wo mein Fehler ist. Hab grad nochmal den Wikipedia-Artikel aufgemacht und gleich als erstes sind mir die beiden Arten von LFSR ins Auge gesprungen (Fibonacci- vs. Galois-LFSR), die ja mathematisch gleichwertig sind. Ich hatte mich direkt auf ersteres gestürzt. Für die Implementierung ist das aber die denkbar ungünstigste Form eines einfachen LFSR. Wenn du dir die Grafik nochmal anschauen willst, dann verstehst du auch, warum ich darauf bestanden hab, dass ich z.B. für eine 8bit-Zahl 8mal das komplette SR schieben muss. Beim Fibonacci-LFSR sollte man das vermutlich tatsächlich machen, da sich ja ansonsten nur das MSB ändert, während der Rest einfach nur eine Stelle weitergerutscht ist. Ist es bei dem von dir beschriebenen LFSR dann so, dass ich - um bei deinem Bsp zu bleiben - nach einmal alle 32bit (also die 4 Byte) schieben, bereits eine neue 8bit-Zufallszahl aus einem der Register entnehmen kann? Ob die dann mit der letzten Zahl korelliert, müsste ja stark davon abhängen, wie viele Taps in diesem Register sitzen. Angenommen, mein Polynom wäre gerade so, dass ausgerechnet das Register, das ich entnehmen will, nur einen Tap hat, dann wäre ja in der neuen Zahl lediglich ein Bit tatsächlich verändert, alle anderen ergäben sich aus der letzten Zahl. Ich werd mir einfach anschauen, wie du das in deinem Firefly-Projekt implementiert hast. Trotzdem bestehe ich aber immer noch darauf, dass ich in meinem Code nicht mit mehreren 8bit- sondern mit 16bit-LFSRs(in meinem Bsp.) arbeite :) Wenn ich mehr Speicher opfere, dann habe ich z.B. bei 57 verwendeten Bytes auch 8 57bit-LFSRs. Ganz abgesehen davon bin ich heute über ein ganz anderes Problem gestolpert: Wenn ich Zahlen z.B. im Bereich 0..13 erzeugen will, bin ich mit meinen 8bit-Zufallszahlen ziemlich aufgeschmissen. Aus den 256 Werten lassen sich einfach keine halbwegs gleichverteilten 14 Werte erzeugen. Einzige Möglichkeit wären 16bit-Zufallszahlen, da ist der Fehler bei der Umrechnung halbwegs erträglich. Hast du vielleicht ein Kochrezept parat? Vielen Dank auf jeden Fall schon mal für die Aufklärungsarbeit! Gruß, Alex
Tja, ;) >(Fibonacci- vs. Galois-LFSR), die ja mathematisch >gleichwertig sind. Ich hatte mich direkt auf ersteres gestürzt. Für die >Implementierung ist das aber die denkbar ungünstigste Form eines >einfachen LFSR. Deine Ableitungen sind nicht ganz richtig ;) Ob Fibonacci oder Galois ist egal vom Aufand her, der Unterschied besteht hardwaremäßig nur in der Schieberichtung und der Frage wie die Taps verknüpft werden müssen. Aus jedem Fibonacci kannst du ein Galois Schiftregister machen und umgekehrt. Auf FPGAs benutze ich zB. viel öfters die Fibonacci Version da sie schneller ausgeführt werden kann. Was aber nur an der Konstruktion der verfügbaren LUTs liegt. >Ist es bei dem von dir beschriebenen LFSR dann so, dass ich - um bei >deinem Bsp zu bleiben - nach einmal alle 32bit (also die 4 Byte) >schieben, bereits eine neue 8bit-Zufallszahl aus einem der Register >entnehmen kann? Nein. Betrachten wir mal das 128 Bit LFSR bestehen aus 256*2Bytes Lookuptabelle, einem 16 Bytes Register für 16 Offsets in die Tabelle und einem Zeiger bestehend aus einem Byte in dieses 16 Bytes Register. Also: byte Register[16] = {0}; word Lookup[256]; byte Index = 0; byte LastIndex = 15; byte Result = Register[Index]; word Look = Lookup[Result]; Register[Index] = Look mod 256; Register[LastIndex] = Register[LastIndex] xor (Look div 256); LastIndex = Index; Index = (Index +1) mod 16; byte Result enthält danach 8 Zufallbits. Die Operation (Look mod 256) extrahiert das LSB aus dem Word, (Look div 256) das MSB. Das ist alles. Die Erzeugung der Lookuptabelle: for i = 0 to 255 do Lookup[i] = i; for J = 0 to 7 do if Lookup[i] and 0x80 <> 0 then Lookup[i] = (Lookup[I] * 2) xor byte Polynom else Lookup[i] = Lookup[i] * 2; Gruß Hagen
Hm Hagen. Weil es so gut paßt zu Zufallszahlen: Ich möchte mir einen BERT Tester bauen. Problem: Wenn Bitfehler auftreten, wird es für den Empfänger immer schwieriger auf die Sequenz zu synchronisieren. Gibts da irgendeinen Trick? Mir fällt nur eine Möglichkeit ein: Erst das S/N extrem hoch ansetzen, den Empfänger synchronisieren lassen und dann das S/N immer weiter abzusenken. Der Empfänger sollte noch eine ganze Weile synchronisiert bleiben auf den nun korrekten Bittakt. Irgendein besserer Ansatz?
Nun betrachten wir mal die allgmeine Version mit der du bis zu 2^2032-1
kommst.
const Polynom_Size = 128;
const Register_Size = (Polynom_size +7) div 8;
byte Register[256] = {0};
word Lookup[256];
byte Index = 0;
byte LastIndex = Register_Size -1;
byte Result = Register[Index];
word Look = Lookup[Result];
Register[Index] = Look mod 256;
Register[LastIndex] = Register[LastIndex] xor (Look div 256);
LastIndex = Index;
Index = Index +1;
if Index >= Register_Size then Index = 0;
Dieser Pseudocode arbeitet dann mit den in meinem Source gelisteten
Polynomen.
Gruß Hagen
Langsam langsam! Ich kau doch noch daran, wie du zu dem speziellen Code kommst :) Das will ich dann schon auch wirklich durchsteigen. Hast du zu dem Problem noch eine Idee? Alexander v. Grafenstein schrieb: > Ganz abgesehen davon bin ich heute über ein ganz anderes Problem > gestolpert: > Wenn ich Zahlen z.B. im Bereich 0..13 erzeugen will, bin ich mit meinen > 8bit-Zufallszahlen ziemlich aufgeschmissen. Aus den 256 Werten lassen > sich einfach keine halbwegs gleichverteilten 14 Werte erzeugen. Einzige > Möglichkeit wären 16bit-Zufallszahlen, da ist der Fehler bei der > Umrechnung halbwegs erträglich. Gruß, Alex
@Abdul: >Hm Hagen. Weil es so gut paßt zu Zufallszahlen: >Ich möchte mir einen BERT Tester bauen. Problem: Wenn Bitfehler >auftreten, wird es für den Empfänger immer schwieriger auf die Sequenz >zu synchronisieren. >Gibts da irgendeinen Trick? Jo, Empfänger wird über einen anderen "Referenzkanal" synchromisiert. Man hat also zwei Übertragunsstrecken, einmal die man BERT'en möchte und ein die absolut sauber ist, meist digital einfach den gleichen Testbitstrom drüber sendet. Ansonsten: Korrelation mit MLS, Maximum Length Sequencies, nichts anders als LFSRs mit maximaler Periode. Die Synchronisation erfolgt, wenn man wenigstens annährende Freqnzstabilität auf Sender/Empfängerseite garantieren kann (mit Quartzen durchaus leicht erzielbar, leichte Abweichungen machen sich nicht bemerkbar) über die Korrelation. Du sendest also über den BERT Kanal diese MLS mit ausreichender Länge. Beim Empfänger wird diese Sequenz empfangen und Kreuzkorreliert mit der selben Sequenz. Der Index des Peak's dieser Korrelation bestimmt den zeitlichen Versatz der empfangen MLS zur internen Korrelations-MLS, also quasi den Startzeitpunkt. Nun kannst du über mehrere solcher Perioden 1.) den Frequenzdrift über PLL regeln 2.) den Phasenversatz über PLL regeln 3.) erkennen, mit hohem SNR, ob überhaupt was empfangen wurde Deine Korrelation kann arbeiten mit: 1.) den per ADC gesampelten Werten 2.) oder die vom ADC erhaltenen Werte auf das Vorzeichen reduzieren und dan nur mit diesem Vorzeichen korrelieren Im Fall 1. ist der Peak der Korrelation dividiert durch die Varianz der ADC Werte identisch mit dem BERT. Im Fall 2. bestimmt der Peak der Korrelation die Anzahl der übereinstimmenden Bits der empfangenen MLS zur Referenz-MLS die sauber ist. Nun, wenn du überabtastest mit deinem ADC, zb. 4 fach, dann machst du diese Korrelation im Empfänger 4 mal mit Abstand +4 in den Samples. Danach kombinierst du alle 4 Ergebnisse dieser Kotrrelationen und hast einen Peak der auf 90 Grad Phasenexakt ist. Nach mehren solchen Durchläufen hats du eine Liste der errechneten Indizies der Peaks aller Korrelationen. Wenn du Frequenzsynchromn bist dann sind diese Indizes alle identisch. Wenn die Frequenz leicht abdriftet dann wandern auch diese Indizes. Du kannst also einfach den aktuellen Index des Peaks mit dem vorherigen subtrahieren und hast den gesuchten Fehlerwert zum Nachführen der PLL. Mit 4 fach Überabtastung kannst du so auch die Phasenlage exakt nachführen. Gruß hagen
> Wenn ich Zahlen z.B. im Bereich 0..13 erzeugen will, bin ich mit meinen > 8bit-Zufallszahlen ziemlich aufgeschmissen. Aus den 256 Werten lassen > sich einfach keine halbwegs gleichverteilten 14 Werte erzeugen. Einzige > Möglichkeit wären 16bit-Zufallszahlen, da ist der Fehler bei der > Umrechnung halbwegs erträglich. Das ist ein generelles Problem auf das viele Programmierer überhaupt nicht Rücksicht nehmen. Sie machen es sich einfach und rechnen Resultat = Zufallswert modulo 14. Und exakt das führt zu dem was du beschreibst. Du kannst das mit einer Resteberechnung aber erschlagen. Also global integer Rest = 0; Rest = Rest - 14; if Rest <= 0 then Rest = Rest + byte Random; byte Zufall = Rest mod 14; Diese Methode setzt voraus das unser Random eine unendlich lange Zufallsfolge erzeugt. Wenn dem so ist dann ist das Resultat Zufall egal mit welchem Modulus man rechnet immer gleichverteilt. Gruß Hagen
Hagen Re schrieb: > @Abdul: > ... > Die Vierfachüberabtastung ist doch das Gleiche wie ein I/Q-Empfänger, richtig? 0° 90° und davon noch beide Polaritäten. Den Rest muß ich wohl erstmal überschlafen. Ich möchte aber nur einen Übertragungskanal benutzen! Denk einfach an Funk mit Abstand Sender-Empfänger relativ unbekannt. Mein selbstgebackener Zitronenkuchen wartet schon sehnsüchtig... Gute Nacht!
Hmm, da fehlt aber nicht noch ein Rest = Rest div 14 am Ende? Sonst kommt ja bei jedem Aufruf das selbe raus, bis die <= Bedingung greift, dann gibts die nächsten selben Zahlen //edit: nein, div is Käse, aber so kanns noch nicht stimmen
@Abdul: das mit der MLS geht mit einem Kanal. Wichtig ist nur das Empfänger und Sender halbwegs Frequenzsynchron sind. >Die Vierfachüberabtastung ist doch das Gleiche wie ein I/Q-Empfänger, >richtig? 0° 90° und davon noch beide Polaritäten. Ja und Nein. Wenn du die MLS im Basisband überträgst dann ist diese Überabtastung keine I/Q Demodulation. Sie dient dann wirklich nur dazu erkennen zu können ob der Peak am größten bei 0,90,180,270 Grad Phasenlage ist. Damit inkrementierst du die Regelgeschwindigkeit und Genauigkeit einer nachfolgenden PLL. Kostet aber auch 4 fachen Rechenpower. Wenn du aber die MLS benutzt um zb. per BPSK eine Frequenz zu modulieren dann kannst du mit der 4 fach Übertastung eine I/Q Korrelation aufbauen. Dazu wird I[x] = Sample[4*x +0] - Sample[4x +2]; Q[x] = Sample[4*x +1] - Sample[4x +3]; gerechnet, also BPSK dekodiert. Über I[MLS Periode] und Q[MSL Periode] samples wird dann jeweils eine Korrelation gemacht. Gruß Hagen
>Hmm, da fehlt aber nicht noch ein > Rest = Rest div 14 >am Ende? >Sonst kommt ja bei jedem Aufruf das selbe raus, bis die <= Bedingung >greift, dann gibts die nächsten selben Zahlen Nöö da fehlt garnichts. Rest = Rest - 14; Entfernt jedesmal einen Zahlenbereich von 0 bis 13. Stelle dir Rest einfach mal so vor wie einen Eimer der maximal 256 Kugeln aufnehmen kann. 256 Kugeln weil unser Zufallsgenerator ein Byte Zufall erzeugt. Jedesmal entnimmst du 14 Kugeln und schmeist sie weg. Danach zählst du alle Kugeln im Eimer in 14'er Schritten bis nur noch < 14 Kugeln im Einer sind. Das ist dein gesuchter Wert. Gruß Hagen
Hagen Re schrieb: > Rest = Rest - 14; > > Entfernt jedesmal einen Zahlenbereich von 0 bis 13. Naja, es entfernt doch eigentlich jedes mal genau 14 :) Und hat damit keinen Einfluss auf das später folgende Modulo.
>Hmm, da fehlt aber nicht noch ein > Rest = Rest div 14 >am Ende? >Sonst kommt ja bei jedem Aufruf das selbe raus, bis die <= Bedingung >greift, dann gibts die nächsten selben Zahlen Nöö da fehlt garnichts es muß nur heisen while Rest < 0 do Rest = Rest + byte Random; Das Rest = Rest - 14; entfernt jedesmal einen Zahlenbereich von 0 bis 13. Stelle dir Rest einfach mal so vor wie einen Eimer der maximal 256 Kugeln aufnehmen kann. 256 Kugeln weil unser Zufallsgenerator ein Byte Zufall erzeugt. Jedesmal entnimmst du 14 Kugeln und schmeist sie weg. Wenn der Eimer leer ist odr sogar Kugeln fehlen werden zufällig aus einen Zufallsgenerator der bis zu 256 Kugeln erzeugen kann neue Kugeln hinzugefügt so lange bis >= 0 Kugeln drinnen sind. Danach zählst du alle Kugeln im Eimer in 14'er Schritten bis nur noch < 14 Kugeln im Einer sind. Das ist dein gesuchter Wert. Oder du gehst andersrum vor: Zähle alle Kugeln im Eimer in 14'er Schritten ab und der Rest ist der gesuchte Zufallswert. Danach entferne 14 Kugeln aus dem Eimer. Ist der Eimer leer fülle ihn solange mit neuen Zufallskugeln bis >= 0 Kugeln drinnen sind. Der Unterschied beider Verfahren liegt in der Frage owie man die globale Variable Rest initialisieren muß. Bei der ersten Methode wird Rest fest mit 0 initialisiert bei der zweiten Methode MUSS man einmalig Rest mit Random intialisiert haben. Gruß Hagen
Mann ich erzähle eine Scheiße Du hast natürlich Recht. Laß mich mal in meinen Sourcen schauen wie ich das damals gelösst habe, es geht über eine Resteberechnung da bin ich mir sicher. Ist nun auch >15 Jahre her, sorry. Gruß Hagen
Ok, ich seh schon, und ich glaub nochmal anders :) Hab mir auch grad gedacht, die Beschreibung klingt logisch, aber der Code passt nicht so ganz. Ich sehs zwar nicht direkt, aber ich stells mir so vor, dass damit die einzelnen generierten Zufallszahlen aneinandergehängt werden, so dass es egal ist, mit welchem Modulo sie erzeugt wurden. Aber ich glaub, das Denken verschieb ich jetzt erstmal auf morgen. Nochmal Danke und gute Nacht! Gruß, Alex
exakt, ich hatte damals ein PDF mit einer mathm. Abhandlung dazu inklusive Pseudocode. Wenn ich nur wüsste wie das F'ckding heist dann würde ich es in den tausenden PDFs hier auch wiederfinden. Man führt zu den Zufallszahlen und den Random Zahlen die eine teilerfremde Periode zueinander haben deren Reste mit und macht dann eine Ausgleichsberechnung. Gruß Hagen PS: kleiner Tipp, halte in deinen PDFs usw. Ordnung und schmeiß sie nicht wie ich alle in ein zwei Ordner.
So, doch nochmal kurz :) Also mit rest = e am schluss schauts eigentlich ganz gut aus. Einziges Problem ist dann natürlich wieder das teure Modulo :(
So, zum Thema eingeschränkter Wertebereich mit Resteverwertung hab ich in Google einen alten Beitrag von dir gefunden, wo du das schonmal erklärt hattest: Beitrag "Re: zufallszahl (at90s2313)" Das LFSR mit Lookup-Table hab ich mittlerweile auch durchstiegen und ausprobiert. Braucht ca. 20-25 Takte mehr als mein ALFG, also nicht besonders viel. Da mir die 512Byte Flash wurst sind, werd ich also das LFSR nehmen, is schon schicker :) Wer den Flash nicht opfern will und trotzdem schnelle Zufallszahlen braucht, ist aber m.M.n mit dem ALFG trotzdem noch deutlich besser bedient als z.B. mit einem LCG. Um das noch etwas zu untermauern: In G.Marsaglia "A Current View Of Random Number Generators", 16th Symposium on the Interface, Proceedings, Atlanta, 1984 hat er fast alle DieHard-Tests bestanden. Ich hab den DieHard auch mal mit von mir erzeugten Zahlen durchlaufen lassen: sowohl mit Taps 17/5 als auch 16/13 besteht er alle 15 Tests bis auf den OPSO. Ist doch gar nicht schlecht! Es ist eigentlich nur die Periode, die in keinster Weise mit einem LFSR mithalten kann. Aber ich denke, in den meisten Fällen ist sie ausreichend. Gruß, Alex
Hagen Re schrieb:
Klasse Hagen! Ich hebe dich mal in den virtuellen Olymp der besten
Postings.
Machen wir per PM weiter.
Gruß -
Abdul
Alexander v. Grafenstein schrieb: > So, > zum Thema eingeschränkter Wertebereich mit Resteverwertung hab ich in > Google einen alten Beitrag von dir gefunden, wo du das schonmal erklärt > hattest: > > Beitrag "Re: zufallszahl (at90s2313)" Tja wusste ich's doch ;) Gruß Hagen
Thread beobachten
Seitenaufteilung abschaltenBitte 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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.