Hier wird diskutiert, wie man mehrere Bits aus verschalteten LFSRs
erhalten kann.
Beitrag "Re: Zusammenschalten verschiedener LFSRs"
Das scheint mir aber nicht die beste Methode. Auf der Seite von Lothar
gibt es dazu auch keinen Hinweis. Wie erhalte Ich mehrere Bits aus der
Schaltung?
Bits hintereinander zu nehmen, ist sicher keine Lösung, weil es immer
dieselben sein werden. Also Dezimieren?
Ein normales Dezimationsfilter hat sofort einen ungleich höheren Aufwand
und damit fällt der wunderschöne Vorteil der einfachen und
platzsparenden Syntese im FPGA weg. Einen FIR würde ich gar nicht in
Betracht ziehen wollen. Ein IIR wird Fehler in der Auflösung haben, wenn
man ihn zu schmal gestaltet, also auch einiges an Bits vebraten. Mehr
sicher, als der Generator.
Also einfach n Generatoren?
Macht es etwas, dass der MCB-Generator mehr Gewicht hat? AFAIR summieren
parallele Rauschquellen zu einem immer stärkeren Gauss-Profil und
liefern verstärkt Werte in der Mitte des Wertebereiches.
Ließe sich die sehr gute Qualtität des LFRS auch gleich mehrkanalig
realisieren indem z.B. ein EXOR über ein Wort gebildet wird? Macht das
einen Unterschied zu dem n-Generatorfall?
Markus W. schrieb:> Das scheint mir aber nicht die beste Methode. Auf der Seite von Lothar> gibt es dazu auch keinen Hinweis. Wie erhalte Ich mehrere Bits aus der> Schaltung?
Mehrere Schaltungen?
Für nur wenige Bits würde ich mehrere Instanzen nehmen, bei 16 Bits und
mehr einfach filtern. Die Daten aus den LFSR-Generatoren bringen bei
günstiger Wahl des Generatorpolynoms eine Art von weißem Rauschen. Das
ließe sich mit einem einfach CIC beliebig filtern, sofern
Frequenzreserve beseht. In der Regel hängt man eh immer einen TP
dahinter. Aus einem 200MHz Rauscher erhält man z.B. 32 Bit mit immer
noch gut 1MHz.
Mehrere verzögerte LFSRs zu nehmen ist eine einfache, aber ineffiziente
Art das Problem zu lösen. Bei xilinx gibt es eine xapp zu einem
parallelen prbs generator (auch ein lfsr) oder outputlogic.com nutzt
einen Algorithmus für die crc (ein anderes lfsr).
Auf Anhieb ist das gar nicht so trivial, aber mathematisch lösbar.
LFSRs liefern gute Zufallsbits. Sie liefern keine guten
Zufallsworte, weil die Werte von JETZT und von INEINPAARTAKTEN
stark miteinander korrelieren. Man kann sich schon ganz gut
darauf verlassen, dass der Wert von Bit N im nächsten Takt bei
n+1 und dann bei n+2 landet; das ist halt ein Schieberegister.
Die spärlichen XORs machen das Kraut nicht fett.
Ich hatte ganz gute Resultate, 5 verschiedene LFSRs oder so
parallel zu betreiben und das Zufallswort aus willkürlichen
Bits der Register zusammenzubauen. Die hochwertigen Bits
bevorzugt aus den langen LFSRs. Der Aufwand geht im FPGA unter.
Das war ganz gut geeignet, um das Signal eines ADCs in Rauschen
zu ersäufen und das gab auch keine unerwarteten Autokorrelationen.
Gruß, Gerhard
Gerhard H. schrieb:> Das war ganz gut geeignet, um das Signal eines ADCs in Rauschen> zu ersäufen und das gab auch keine unerwarteten Autokorrelationen.
Wenn die im selben FPGA laufen, sind die aber fest korrelliert. Also
auch nicht zufällig. Ich würde sagen, dass die Werte dann von der
Initialisierung abhängen, oder? Das müsste sich dann auch mit nur einer
Schaltung zu machen sein.
Ja. Das sind ganz klar Pseudo-Zufallszahlen. Wenn man den reset
loslässt, erhält man jedes Mal die gleichen Ergebnisse.
Wenn man 16-Bit-Pseudozufallswerte haben will und man nimmt nur ein
einziges 16-Bit-LFSR, meinetwegen mit XORs an Position 2, 12, 15 (keine
Ahnung, ob das jetzt ein sinnvolles LFSR ergibt) und die Shift-Richtung
ist aufwärts, dann taucht Bit 2 im nächsten Takt bei 3 auf, dann bei 4,
5, 6, 7, 8, 9, 10, 11 und erst bei Bit 12 wird die Systematik
unterbrochen.
Das bedeutet aber, dass die Bits 2..12 von Ausgangswert zu Ausgangswert
wie bei einer Rampe verkoppelt sind. Die Rampe wäre dann noch mit 2**n
zu wichten. Und die Rampe wiederholt sich andauernd mit Nullen oder
Einsen.
Wenn man die Ausgangswerte aus den Bits mehrerer LFSRs unterschiedlicher
Lauflänge zusammenglaubt, dann kann sich so ein lokaler Zyklus deutlich
schwerer entwickeln.
Gruß, Gerhard
Gerhard H. schrieb:> Ja. Das sind ganz klar Pseudo-Zufallszahlen. Wenn man den reset> loslässt, erhält man jedes Mal die gleichen Ergebnisse.
Was wäre, sie beim Start zufällig loslaufen zu lassen?
Die Frage ist, ob man das braucht oder auch nur will. Man würde einen
echten Zufallswert zum Initialisieren brauchen, etwa die Zeit zwischen 2
Tastenanschlägen modulo 1 ms, oder ein ADC, der thermisches Rauschen
misst.
Wenn man ein Signal im Rauschen ertränken will um zu sehen, wie gut man
den BPSK-Demodulator hinbekommen hat, dann schadet das "Pseudo" nicht,
das würde in der Simulation sogar Regress-Tests erleichtern weil ein
größerer Teil des Gesamtsystems bit-identisch bleibt.
GPS-artige Systeme brauchen das "Pseudo" grundsätzlich, weil man eine
lokale Version des Rauschens herstellen muss um sie zwecks Korrelation
langsam über das empfangene Pseudo-Noise zu schieben. Wenn die
Korrelation maximal wird, dann hat man die Verzögerung zwischen den
beiden Signalen gefunden.
Mir fällt jetzt auf Anhieb keine Anwendung ein, wo die
Reproduzierbarkeit schadet. Ja, ein Computer-Kartenspiel, das irgendwie
langweilig würde.
Gruß, Gerhard
Gerhard H. schrieb:> Ja, ein Computer-Kartenspiel, das irgendwie langweilig würde.
Also sowas wie FreeCell, wo der Seed des RNG einfach als "Spiel-Nummer"
deklariert wird? :-)
Mehrere LFSR parallel. Mach die Länge des LFSR so lang, das Du in der
Praxis nie eine Widerholung sehen wirst. Das kostet ja nicht viel.
Das Problem mit der Korrelation kannst du lösen, indem Du die LFSR
clever initialisierst.
Beispiel: Du willst Dein LFSR mit 200Mhz laufen lassen und willst keine
Korrelation innerhalb eines Jahres sehen. Pro Iteration willst Du 8 Bits
rausholen:
Für 200Mhz 1 Jahr 8 Bit kommst Du mit 8 Registern á 56 Bit Länge
aus.
> print lg2(200e6*60.0*60.0*24.0*356.0*8)
> 55.4499018820035
Jetzt berechnest Du dir den Initialisierungsvector für das erste LFSR.
Das zweite startest Du mit dem Zustand nach (1*periodendauer/8). das
dritte mit (2*periodendauer/8) usw.
(den n-ten Zustand eines LFSR kann man vorberechnen)
So stellst Du sicher, das die acht LFSR nie innerhalb eines Jahres die
gleiche Sequenz durchlaufen. Es gibt dann kein Bias zwischen den Bits
mehr.
Hallo Nils, sowas hatte ich auch überlegt.
Siehe auch hier:
Beitrag "Re: 4, bzw. 16 verschiedene Zufallszahlen"
Die Längen sind kein Problem, richtig. Aber:
Nils P. schrieb:> Jetzt berechnest Du dir den Initialisierungsvector für das erste LFSR.> Das zweite startest Du mit dem Zustand nach (1*periodendauer/8). das> dritte mit (2*periodendauer/8) usw.
Wie ermittle ich diese Positionen? Ich kann es ja weder durchprobieren,
noch warten, weil die Dauer ja 1/8 eines Jahres wäre.
Das ist doch völlig gleich wie die bereits vorgeschlagenen typ. 5 LFSRs.
Das einzige, das man vermeiden muss, ist das Ausgangswort aus einem
einzigen LFSR zu nehmen, weil dessen Bits untereinander eng verkoppelt
sind. Bei 5 verschieden_langen parallelen LFSRs kann man alle
gleichzeitig starten, wenn es sein muss auch alle mit 1111111 oder
000000.
Vermutlich tun es auch weniger als 5 LFSRs, aber die kosten ja nix.
Bei der Länge braucht man es nicht übertreiben, weil die Größe des
Zustandsraumes von allen LFSR-Bits gemeinsam bestimmt wird.
Das ist übrigens nicht der Fall bei 8 gleichen LFSRs, die nur an
unterschiedlichen Punkten gestartet werden. Ich habe auch den Verdacht,
dass bei 8 gleichen Registern die Verkopplung der Bitpositionen nicht
wirklich weggeht. Das ist eigentlich strukturell nur 1 LFSR und ein
riesiges FIFO mit 7 Taps, das letztes Jahr gestartet wurde damit das
FIFO voll wird.
Gerhard H. schrieb:> Wenn man die Ausgangswerte aus den Bits mehrerer LFSRs unterschiedlicher> Lauflänge zusammenglaubt, dann kann sich so ein lokaler Zyklus deutlich> schwerer entwickeln.
Das sehe ich aber anders. Das ist nach wie vor nicht wirklich anders und
damit genau so vorhersagbar wie das einzelne Schieberegister-System. Das
gilt selbst dann, wenn man die Startwerte der einzelnen LSFR zufällig
wählt oder jedesmal neu variiert.
Der Vorteil ist aber der, dass man die Daten mit voller Bandbreite
bekommt. Für Audio kann man mit einem 20MHz-FPGA einen sehr guten
Datenstrom bekommen und auf 1kHz runterfiltern. Dann sind das echte 24
Bit-Rauschdaten. Nicht zufällig, sondern vorhersehbar - aber sie hören
sich an wie zufälliges Rauschen und sind auch so nutzbar. Das schließt
die Themen Dithering und Noise Shaping mit ein.
Für Video geht das nicht. Ein Rauschgenerator für die unteren 8 von 12
Bit bei Kamera-Rohdaten braucht 8 unabhängige Generatoren für alle Bits,
die mit z.B. Primzahlen rotieren und wenigstens 3-4sec Abstand haben.
Das sind 24 LFSRs mit mindestens 32Bit für alle 3 Farben.
