Announcement: there is an English version of this forum on N'Abend allerseits, ich muss Stoerungen auf einem Signal (Registerwert mit 16 und 15 Bit Breite) erzeugen. Das ganze natuerlich auch vorhersagbar, sprich reproduzierbar (Testautomatisierung). Jetzt faellt mir spontan ein LFSR ein (immer mal wieder resetted damit definierte Zustaende sind) sowie eine LUT (z.B. 1024x16bit) die ich mit einem Skript (PERL) befuellen koennte. Das Noise/Rauschen das ich dem eigentlichen Signal ueberlagere, soll auch noch in der Amplitude einstellbar sein (also Multiplier oder eben nur einen Subset des Ranges verwenden). Hat da jemand ne zuendende Idee? Also wenn LFSR wie kann ich sicher sein, dass das Ding nicht nach ein paar Zyklen eingeschwungen ist? Und wenn LUT, mit welchem Algorithmus befuelle ich die? Das Ding soll Mitte naechster Woche laufen, ich hab' mich noch nicht wirklich in die Materie vertieft... (da sind wie ueblich auch noch andere Baustellen...) Also, gibt's Ideen? Gruss, - berndl
Eine Suche auf der Internetsuchmaschine Google (die kennst du sicher nicht, weil sie erst letzte Woche aufgemacht hat) bringt folgenden Artikel in diesem Forum: http://www.mikrocontroller.net/articles/Digitaler_Rauschgenerator_im_FPGA
Google, watt datt denn? Danke fuer den Link, schau' ich mir mal an
Ein LFSR wird mit zunehmender Länge immer "besser", eine indizierte Tabelle wird mit interessanter Länge immer undurchführbarer. LFSRs liefern immer nur 1 "gutes" Bit, der ganze Registerinhalt ist aber von Schritt zu Schritt hochgradig korreliert. Um ein moduliertes Signal (war selber eine PN-Folge) in weißem Rauschen zu ersaufen, habe ich einmal ein halbes Dutzend LFSRs ziemlich unterschiedlicher Länge genommen und aus jedem ein paar Bits gekürt und daraus das Zufallswort ziemlich mutwillig zusammengestellt. Das hat ganz gut funktioniert. Kryptologisch stark geht anders, aber der Spektrumanalyzer nach dem DAC war hoch zufrieden. Spektrum glatt wie'n Baby-Po. Es gibt ein gutes Buch von einem Herrn Dixon, "Spread Spectrum Systems and Commercial Applications" oder so ähnlich; sehr empfehlenswert für Praktiker. (richtig mit Scope- und Spectrum-Analyzer-Photos und der ganzen Pathologie: Wenn's so aussieht, was hab' ich dann verbrochen???) Gruß, Gerhard
Man kann ein LFSR auch parallel auslesen. Zb die oberen 10Bit eines 20 Bit LFSR auf einen DAC
Ich meine, die Bits müssen immer aus unabhängigen Quellen stammen. Also mehrere Generatoren.
Kann der Gerhard(Gast) mal kurz ausfuehren weshlab paralleles Auslesen eines LFSR die schlechteste Loesung sein soll. Mir scheint, alle parallel Werte ausser Null werden mit der gleichen Haufigkeit erreicht. Ich lern aber immer gerne mal was dazu.
moin moin, selbstverständlich kann man ein LFSR auch parallel auslesen. Aber: Ein Schiebevorgang liefert immer nur 1 neues Bit. Bei parallelem Auslesen muß für eine Wortbreite von n Bit der Schiebetakt daher das n-fache des Worttaktes betragen. Wenn man also beispielsweise 8 Bit parallel ausliest, muß man bis zum nächsten Auslesen das LFSR auch um 8 Bit weiterschieben. Wer nach jedem Schiebetakt 8 Bit ausliest, hat natürlich erhebliche Redundanz und bekommt alles andere als gleichverteilte Werte. Gruß, Thorsten
Thorsten S. schrieb: > selbstverständlich kann man ein LFSR auch parallel auslesen. > Aber: Ein Schiebevorgang liefert immer nur 1 neues Bit. > > Bei parallelem Auslesen muß für eine Wortbreite von n Bit > der Schiebetakt daher das n-fache des Worttaktes betragen. Warum denn? Was spricht konkret dagegen, das komplette LFSR parallel auslesen und weiterverwenden. Warum funktioniert das in der Praxis? > Wer nach jedem Schiebetakt 8 Bit ausliest, hat natürlich erhebliche > Redundanz Warum? Woher kommt diese "Redundanz"? > und bekommt alles andere als gleichverteilte Werte. Und was sollte z.B. bei einem 16-Bit LFSR dann besser sein, wenn es für einen 8-Bit-Wert jedesmal um 8 Bits weitergeschoben wird? Mir reicht die Zufälligkeit eines LSFR auch, wenn ich es genügend breit mache und beliebige Teile davon parallel auslese: http://www.lothar-miller.de/s9y/categories/38-LFSR
Nein, ein LFSR liefert nicht nur ein Bit pro Shift. Wenn die hoeherwertigen Bit alle Null waeren, und man gegen hoeherwertig schiebt, dann verdoppelt sich das Resultat. Das hoeherwertigste Bit faellt aber raus. Ich hab gute Erfahrungen mit LFSR parallel Auslesen gemacht. Die Werte sind wieder gleichverteilt. Da ist nichts mit Redundanz.
Vielleicht ist das was für dich. Scheint mir noch nicht ganz ausgereift zu sein, jedoch ist es auch nur ein Bericht zum Praxissemester oder so. Hier wurden aber verschiedene Methoden zur Erzeugung von Zufallszahlen in einem FPGA getestet. An der Uni Magdeburg haben wir das mal nachvollzogen und es lief ganz vernünftig. Leider gibt es keine Beschreibung zur periph. Beschaltung des FPGA und der Autor kann diese nicht liefern, da es sich um ein Industrieprojekt handelt. http://www.hs-merseburg.de/~8ckaehle/dateien/ind_BA/Bericht_Ind.pdf
Lothar Miller schrieb: > Was spricht konkret dagegen, das komplette LFSR parallel auslesen und > weiterverwenden. > Warum funktioniert das in der Praxis? Es funktioniert "so halbwegs" aber nicht ganz richtig... Konkret dagegen spricht, daß wenn man zum höherwertigen Bit schiebt, mehrere aufeinanderfolgende Werte mit einem Schiebevorgang jeweils nahezu (bis auf die unten reingeschobenen "Nachkommastellen") dem verdoppelten Vorgängerwert entsprechen. Das ist keine zufällige Verteilung! Diese exponentiell ansteigenden Kurventeile sieht man auch in Deiner Simulation. Ich habe mir das kürzlich (hinter einem DAC) auf dem Oszilloskop angeschaut und zwar nicht als Kurve, sondern als Punktdarstellung (ohne Rekonstruktionsfilter hinter dem DAC). Man erkennt bei 1-bittigem Schieben und 8-bittigem Auslesen gut diese bogenförmigen Häufungen. Probier es aus! Schiebe jeweils um die ausgelesene Bitbreite weiter. Das Ergebnis ist sichtbar besser! In meinem Fall zeigt die Darstellung der ungefilterten DAC-Werte auf dem Oszilloskop dann eine gleichverteilte Punktewolke, wie man das von weißem Rauschen auch erwarten muß. Das Signal sieht dann auf der gesamten ausgeschriebenen Schirmfläche aus, wie völlig gleichförmig mit einem Punkte-Streuraster belegt. >> Wer nach jedem Schiebetakt 8 Bit ausliest, hat natürlich erhebliche >> Redundanz > Warum? Woher kommt diese "Redundanz"? Daraus daß stets sich verdoppelnde Wertereihen entstehen, wenn die höherwertigen Bits gerade Null sind und auf einen kleinen Wert nie plötzlich ein großer folgt, sondern sich das Ganze immer erst in Verdoppelungsschritten "hochschraubt". Das Phänomen ist in Deiner verlinkten Simulation gut zu erkennen. Wie gesagt, probier es aus, und laß Dich vom Ergebnis überzeugen. >> und bekommt alles andere als gleichverteilte Werte. > Und was sollte z.B. bei einem 16-Bit LFSR dann besser sein, wenn es für > einen 8-Bit-Wert jedesmal um 8 Bits weitergeschoben wird? Der Zufallsdatenstrom eines LFSR ist die Folge der am Ende herausgeschobenen Bits. Beim Empfang eines seriellen Datenstroms kämst Du ja auch nicht auf die Idee, nach dem Einlesen jeweils eines Bits einen neuen 8-Bit-Wert als empfangen zu melden, sondern Du wartest alle 8 Bits ab, bevor der Wert gespeichert wird. > Mir reicht die Zufälligkeit eines LSFR auch, wenn ich es genügend breit > mache und beliebige Teile davon parallel auslese: > http://www.lothar-miller.de/s9y/categories/38-LFSR Bitte probiere es aus und erweitere Deine Simulation mal um die für die jweilige Bitbreite nötigen Schiebevorgänge. Das Ergebnis ist ein Vielfaches besser, ich vermute, Du wirst überrascht sein, wieviel besser. Gruß, Thorsten
Thorsten S. schrieb: > Konkret dagegen spricht, daß wenn man zum höherwertigen Bit schiebt, > mehrere aufeinanderfolgende Werte mit einem Schiebevorgang jeweils > nahezu (bis auf die unten reingeschobenen "Nachkommastellen") dem > verdoppelten Vorgängerwert entsprechen. Das ist keine zufällige > Verteilung! > Diese exponentiell ansteigenden Kurventeile sieht man auch in Deiner > Simulation. Das Argument ueberzeugt mich! Da ich zwischen 2 Werten genuegend Zeit habe werde ich das mal probieren (16bit LFSR eben 16 mal takten). Danke fuer die Erklaerung.
Lange Rede kurzer Sinn... Der Thorsten hat Recht... Mach dir mal den Spaß und simuliere solch ein Schieberegister in Matlab... Dann nimmmst du dir deine ersten parallel ausgelesenen 8 Bit und die nächsten ausgelesenen 8 Bit (zwischendurch nur ein mal schieben). Davon einfach mal die AKF berechnen und erhebliche Ähnlichkeit (fast Gleichheit) feststellen...
Die Beobachtungen sind richtig. Dasselbe trifft natuerlich auch zu wenn man nach LSB schiebt. Oder die Bits permutiert. Wenn man nun pro Bit ein eigenes LFSR verwendet muesste man diese Autokorrelation auch pruefen und nicht einfach annehmen, es sei sicher ok.
Thorsten, danke dass Du mir die Arbeit abgenommen hast. Völlig richtig. Selbst wenn man das Zufallswort aus mehreren LFSRs zusammenkopiert, wie ich oben beschrieben habe, ist man vor Überraschungen nicht völlig sicher. Etwa in der Art: Man nimmt die Pseudonoise-Worte um ein BPSK-moduliertes Signal mit einer PN-Folge im Rauschen zu ertränken und kann plötzlich nicht mehr auf die PN-Folge locken, auch wenn C/N noch gut ist. Mit einem anderen Polynom ist aber alles ok. Selbst wenn man nur 1 Bit aus dem LFSR nimmt, fällt der eine fehlende Registerzustand schon mal auf. Angenommen, man moduliert damit einen Träger in BPSK; dann dürfte kein Restträger übrig bleiben wenn sonst alles stimmt. Bei einem 8-Bit LFSR hat man aber 128 Einsen und 127 Nullen, d.h. die Trägerunterdrückung wird nicht besser als 10log(256), oder 24 dB. Der Träger ist auf dem Spekrumanalyzer fett zu sehen, weil die Modulations- Seitenbänder sich ja auch noch über viele Frequenzen verteilen, der Träger aber nicht. Gruß, Gerhard
gerhard schrieb: > Selbst wenn man das Zufallswort aus mehreren LFSRs zusammenkopiert, wie > ich oben beschrieben habe, ist man vor Überraschungen nicht völlig > sicher. Jo, mit solchen Spezial-Konstrukten stellt man sich oft eher selbst ein Bein (wenn man nicht gerade Mathematiker ist, und die Theorie dahinter wirklich verstanden hat). Ähnlich wie mit Krypto-Algorithmen... Da halten die "besonders genialen" proprietären Algorithmen oft einer Kryptoanalyse nicht stand und entpuppen sich nur allzuoft als schwach. > Selbst wenn man nur 1 Bit aus dem LFSR nimmt, fällt der eine fehlende > Registerzustand schon mal auf. Angenommen, man moduliert damit einen > Träger in BPSK; dann dürfte kein Restträger übrig bleiben wenn sonst > alles stimmt. > > Bei einem 8-Bit LFSR hat man aber 128 Einsen und 127 Nullen, d.h. die > Trägerunterdrückung wird nicht besser als 10log(256), oder 24 dB. auch 'ne interessante Anwendung dafür... Also hier lieber ein schön langes LFSR nehmen, bei 80 Bit juckt die fehlende Null nicht mehr. ;-) Hab mal ein LFSR benutzt, um Veränderungen zwischen aufeinanderfolgenden Videobildern zu erkennen, ohne daß ein Bildspeicher existiert. Das LFSR wird am Bildanfang zurückgesetzt und die Pixelwerte dann mit der Pseudozufallsfolge XOR-verknüpft. Ausgewertet wird das Histogramm über die Daten; das ändert sich bei Änderungen im Bildinhalt dann ziemlich stark. Was auch den Threaderöffner interessieren könnte, ist die folgende Application-Note (XAPP210) von Xilinx: http://www.xilinx.com/support/documentation/application_notes/xapp210.pdf Darin ist eine effiziente Implementierung von LFSR in Xilinx-FPGAs beschrieben (mit SRL16). Ein 52-Bit LFSR braucht so z.B. nur 3 SRL16, 4 FD und ein XOR2. Das Dokument ist zwar für Virtex / Virtex-II geschrieben, aber direkt übertragbar auf z.B. Spartan-3A oder Spartan-6. Also nicht irritieren lassen von der "Product is Obsolete" Notice. ;-) Selbst wenn man gar kein FPGA verwenden möchte, ist das Dokument sehr nützlich, da es eine Tabelle mit den XOR-Taps für Maximum-Length-LFSR bis 168 Bit Länge enthält. Gruß, Thorsten
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.