Schnelle (Pseudo-)Zufallszahlen

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

Der STM32F2xx hat ein "RNG - Random Number Genrator" im Chip.

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

nein, ein
Rest = Zufall
fehlt noch

Ich habs doch grad ausprobiert :)

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