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
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
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
