Hallo, welchen sind hat das Zusammenschalten mehrerer Linear Feed Back Shift Register. Ich habe hier ein Blockschaltbild vor mir wo drei LFSRs mit unterschiedlichen Polynomen parallel betrieben werden. Aus jedem werden willkürlich zwei Ausgangsbits genommen und zu einem 6 bit Ausgangswort zusammengefügt. Hat das einen besonderen Sinn. Erhöht sich somit die maximale Zykluslänge ? Leider lässt der Author (Semesterarbeit) den Sinn und Zweck dieses Vorgehens völlig unbeleuchtet. Gruss, Matze
Hallo, man nimmt in der Regel nur ein Bit eines LFSR um damit Pseudo-Zufallszahlen zu erzeugen, denn andernfalls wird - zusätzlich zu der eigentlichen Periodenlänge des LFSR - ein periodisches Signal kleinerer Länge generiert. Bin selbst kein Experte auf dem Gebiet, habe aber vor kurzem einen einfachen Rauschgenerator benötigt, mir hat die englische Wikipedia weitergeholfen: http://en.wikipedia.org/wiki/LFSR -> Xilinx-Link Vielleicht hatte der Schreiber der Semesterarbeit nur einen sehr kleinen CPLD und wollte Logik sparen, aber besser dürften 6 parallele LFSR sein. Bei allen kann das gleiche Polynom verwendet werden, allerdings mit unterschiedlichen preload-Werten. Falls Rauschen als Störquelle erzeugt wird, lohnt es sich ein Histogramm für die Verteilung und eine FFT (keine unerwünschten Perioden) aufzustellen.
> Hat das einen besonderen Sinn. Ich tippe auf Hokus-Pokus ;-) Mit einem z.B. 16 Bit breiten LFSR kann ich maximal 65535 verschiedene Zufallszahlen erzeugen. Ich kann mir keine Konstellation vorstellen, in der die Aufteilung der Zahlen auf z.B. 2x8 Bit eine bessere Zufallsreihenfolge bringen könnte. 16 Bit bleiben 16 Bit. > wo drei LFSRs mit unterschiedlichen Polynomen parallel betrieben werden. > Aus jedem werden willkürlich zwei Ausgangsbits genommen und zu > einem 6 bit Ausgangswort zusammengefügt. Wenn also jedes der drei LFSR 16 Bit breit wäre, würde ich von einem 48 Bit LFSR, aus dem willkürlich 6 Bit herausgeschnitten werden, gleich gute Ergebnisse erwarten.
Ich frage mal nach, auch wenn es ein altes Thema ist: Lothar M. schrieb: > Wenn also jedes der drei LFSR 16 Bit breit wäre, würde ich von einem 48 > Bit LFSR, aus dem willkürlich 6 Bit herausgeschnitten werden, gleich > gute Ergebnisse erwarten. Hätte das 48er LFSR nicht ein bessere Güte die mit der 2er-Potenz geht? Das müsste doch gleich erheblich besser sein, um mehrere Bits zu gewinnen. Wäre die Frage, wie man sie gewinnen könnte.
Dann versuche ich mich mal an einer plausiblen Erklärung. Solche Konstrukte findet man oft in der Kryptographie, https://de.wikipedia.org/wiki/Stromverschl%C3%BCsselung um eine ausreichend hohe Periodenlänge zu erzielen. Das geht mit einem einzelnen, sehr langen LFSR nicht so gut, weil es "gute" und "schlechte" Polynome (Rückführungskombinationen) gibt, die zu ermitteln, einen beträchtlichen Aufwand macht. Also nutzt man lieber mehrere, kürzere LFSR, mir erwiesen gutem Polynom.
ok, das ist nachvollziehbar. Habe ich auch schon mitbekommen, dass sie verschiedene Autoren schwer tun, für ihre Polynome statistisch bewiesene Angaben zur Qualität zu machen. Für mich wäre es entscheidend, dass ich mehrere Bits erhalte, die unabhängi von einander sind und deren Zusammenführung nicht die Qualität des Rauschens reduziert.
Es geht dabei vermutlich um kryptografische Sicherheit. Ein LFSR ist deterministisch. Kennt man das Polynom und den momentanen Zustand, kann man alle Folgezustände berechnen. Kombiniert man hingegen Teilergebnisse aus mehreren verschiedenen LFSR, dann geht das nicht mehr so einfach, weil man aus dem Gesamtergebnis nicht mehr auf den aktuellen Zustand jedes der LFSR zurückrechnen kann, jedenfalls nicht mit nur einem Sample. Ein Angreifer braucht dann schon genaue Kenntnis der Architektur, um den Folgezsutand zu berechnen. Besser wäre es, einen richtig guten PRNG zu verwenden (z.B. einen Mersenne-Twister) und eine sichere Hashfunktion nachzuschalten. Aber der Hardwareaufwand dafür ist natürlich massiv größer.
Vancouver schrieb: > Besser wäre es, einen richtig guten PRNG zu verwenden (z.B. einen > Mersenne-Twister) Ja, wobei ein solcher Twister geht im FPGA erstaunlich einfach - mit entsprechenden Frequenzen - (BTDT). Weitere "Rüttel-und Schüttelmethoden" wären Marsaglia etc. Man muss sich aber immer fragen, wie sicher die Methode jeweils ist, wenn jemand aus der Entwicklertruppe ausscheidet oder ein Angreifer sonst wie dazu kommt, zu wissen, wie ein Algo funktioniert. Es ist im Sinne der Sicherheit daher oft zweckmäßiger eine einfache Codierung mit Verfahren zu wählen, die man dem Prinzip nach erraten kann, die aber von einem oder mehreren Schlüsseln abhängig sind, die man regelmäßig wechselt. Damit sind Klassifizierungen und das Einrichten von Sicherheitshierarchien sehr einfach möglich. Es ist nur eben etwas mehr Rundherumaufwand nötig wie das geschützte Übertragen von Schlüsseln, deren Änderungen und deren Löschungen. Eine andere Frage ist, wie man ein Signal so aufbereitet, dass es sicher decodiert werden kann, als Rauschen aber im normalen Datenstrom gar nicht auftaucht, also gar nicht bekannt ist, dass ein System etwas von sich gibt. Auch da gibt es Methoden mit / ohne LSFR. Markus W. schrieb: > Für mich wäre es entscheidend, dass ich mehrere Bits erhalte Das Einfachste sind wohl mehrere unabhängige Generatoren, jedenfalls im FPGA. Das ist zumindest die kleinste Lösung. Da ein einzelner Generator ein (fast) gleichverteiltes Spektrum (weißes Rauschen) erzeugt, sind die Ergebnisse auch "weiss", wenn die Generatoren wirklich unabhängig sind. Das sind sie allerdings nicht perfekt, wenn derselbe FPGA Takt verwendet wird. Auch nicht, wenn man ihnen einen Teiltakt verpasst. Kommt eben darauf an, welche Qualität man möchte. Ich habe das damals einfach so gemacht, dass ich das Rauschen, das entstand, gemessen habe und einen Korrektur-EQ drübergestülpt habe.
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.