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?
Hier ist noch so ein Beitrag, der ähnlichen Inhalt hat. Aber auch mit keinem nachhaltigen Ergebnis: Beitrag "4, bzw. 16 verschiedene Zufallszahlen"
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.
:
Bearbeitet durch User
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.
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.