Hallo, für LFSR gibt es diese Tabellen für die primitiven polynome. Die geben vor wie die LFSR verschaltet werden, damit man die maximale Periodenlänge eines LFSR erreicht. Wie wurden die primitiven Polynome gefunden? Ist es reines ausprobieren mit supercomputern, bis man ein primitives polynom gefunden hat? lg
Es geht um Maximallängen der rückgekoppelten Struktur. Du kannst dich in die Mathematik zu Maximum Length Linear Feedback Shift Registers einlesen .....
Ch. K. schrieb: > Wie wurden die primitiven Polynome gefunden? Ist es reines ausprobieren > mit supercomputern, bis man ein primitives polynom gefunden hat? "sowohl - als auch", wenn ich den Vorlesungsstoff noch in Erinnerung habe. Als man "damals" begonnen hatte, die Mächtigkeit der Mengen zu analysieren, gab es noch keine Super-Computer, daher war man auf die mathematische Analyse angewiesen, die beim LFSR recht einfach war. Soweit ich mich erinnere, ging das u.a. über die "vollständige Induktion" mit der bewiesen wird, dass der Nachfolger eines jeden Wertes wider bestimmte Eigenschaften hat, die implizieren, dass es zu einer Maximalfolge kommen muss. Ich kann dir das aber nicht mehr herbeten. In der Krypto gibt es mehrere Mechanismen, das zu untersuchen und seit es in den 1970ern auch Zugang zu schnellen Rechnern gab, die so etwas ausprobieren konnten, wurde das auch gemacht und gecheckt, insbesondere die Algos, die sich nicht analytisch beweisen liessen. Tatsache ist, dass damals eine Reihe von als "gut" bewerteten Folgen regelrecht "aufgeflogen" ist, weil diese so umfangreich und gutverteilt nicht waren, wie gedacht. Es gibt einige Folgen, die nach einer Anlaufphase in einen Zyklus münden können, je nachdem wie sie fomruliert sind und wie z.B. gerundet wird. Ob das bei reinen XOR-Shift-Systemen der Fall ist, weiß ich nicht auswendig. Ich habe nur in meiner Anfangszeit solche Folgen untersucht und auch eigene Strukturen ausprobiert, wie hier schon angeführt: Beitrag "Re: "analoge" FIR Filterung" ... von denen ich dann auch einige über board geworfen habe (unter anderem meinen ersten Super-Duper-Rauschgenerator im PYRA-Synth, der Häufungen im Spekrum hatte, die aber im groben Audio-Analyzer nicht aufgefallen waren). Der Punkt bei der High-End-Computer-Technik ist natürlich der, dass man für sehr lange Register einfach nicht mehr in sinnvollen Zeiten zum Ziel kommt, daher bleiben für die die richtig guten Polynome und Algorithmen nur analytische Methoden. Für die "kurzen" Generatoren um die 20 Bit abwärts, kann man die Zahlen sehr leicht in Excel berechnen, sortieren und schauen, ob sie die Maximalfolge erreichen und wie deren Spektrum aussieht. Für eine Reihen von LFSR wurde das bereits von anderen getan. Viele Dokumente (auch das oben gelinkte) verweisen direkt oder indirekt auf die einschlägige Xilinx APP 052, welche die Arbeiten von Wayne Stahnke aus dem Jahr 1970 zitiert.
Ch. K. schrieb: > für LFSR gibt es diese Tabellen für die primitiven > polynome. Die geben vor wie die LFSR verschaltet > werden, damit man die maximale Periodenlänge eines > LFSR erreicht. > > Wie wurden die primitiven Polynome gefunden? Ist es > reines ausprobieren Ja, mehr oder weniger. (Quelle: Erinnerung an Lüke, "Korrelationssignale") > mit supercomputern, bis man ein primitives polynom > gefunden hat? Nicht zwingend Supercomputer. Teilweise ist spezielle Hardware für die Suche gebaut worden, teilweise ist auch der Suchraum schon durch Vorüberlegungen eingeschränkt worden. Wenn man z.B. maximal 7 Ausgänge berücksichtigt, muss man für 100bit-Schieberegister "nur" etwas weniger als 100^7 =10^14 Varianten testen; wenn man Äquivalenzklassen bilden kann, muss man noch weniger testen. Schafft man 10^7 Varianten je Sekunde, ist man in einem knappen halben Jahr fertig.
Jürgen S. schrieb: > Es gibt einige Folgen, die nach einer Anlaufphase in einen Zyklus münden > können, je nachdem wie sie fomruliert sind und wie z.B. gerundet wird. > Ob das bei reinen XOR-Shift-Systemen der Fall ist, weiß ich nicht > auswendig. Durchaus. Bei schlecht gewählten Anzapfungen kann es passieren, dass wesentlich kürzere Zyklen entstehen. Stets aber ist die Periode 2^N -1. Und das ist auch der Punkt, der mich auch an der Diplomarbeit stört, die ich allerdings nur überflogen habe: Die Periode des gezeigten 9-Stufigen PRN-Generators beträgt nicht 512, sondern 511. Die Kombination "alle Stufen 0" tritt nicht auf und darf auch nicht auftreten, weil dann nie wieder eine 1 ins Schiebregister injiziert würde. Es kämen nur noch Nullen raus. Deshalb enthält die von dieser Schaltung erzeugte Sequenz 256 Einsen und 255 Nullen. Das wird auch der Grund sein, weshalb der Sender abwechselnd mit der normalen und der invertierten Sequenz moduliert wird, weil das Gleichgewicht zwischen Nullen und Einsen erst nach zwei Zyklen wieder hergestellt wird. Andernfalls würde der Sender nach jeder Sekunde um 13 Grad "vor" gehen, und nach 28 derartig phasenmodulierten Sekunden wäre er schon um eine volle Trägerschwingung = 13µs zu schnell. Dann doch lieber Opas alte Taschenuhr verwenden. ;-)
:
Bearbeitet durch User
Hp M. schrieb: > Und das ist auch der Punkt, der mich auch an der Diplomarbeit > stört, die ich allerdings nur überflogen habe: > Die Periode des gezeigten 9-Stufigen PRN-Generators beträgt > nicht 512, sondern 511. Das sehen die Herren von der PTB aber anders. Siehe in beigefügtem Dokument Seite 354 links oben. > Die Kombination "alle Stufen 0" tritt nicht auf und > darf auch nicht auftreten, weil dann nie wieder eine 1 > ins Schiebregister injiziert würde. Es kämen nur noch > Nullen raus. Um genau das zu verhindert ist eine Zusatzbeschaltung vorhanden; es handelt sich daher NICHT mehr um eine der üblichen Maximallängenfolgen.
Egon D. schrieb: > Schafft man 10^7 Varianten je Sekunde, ist man in einem > knappen halben Jahr fertig. Kommt auch auf die HW an. Bei ASIC-Prototyping mit FPGA-Farmen lässt sich das sehr weit herunterbrechen, zumindest dann, wenn es gelingt, die Aufgaben geschickt zu verteilen und die Ergebnisse einzusammeln.
Egon D. schrieb: > Um genau das zu verhindert ist eine Zusatzbeschaltung > vorhanden; es handelt sich daher NICHT mehr um eine der > üblichen Maximallängenfolgen. Dann ist der Wert der Sequenz aber noch noch geringer, als die mit (n-1)/n, wenn die 0 nicht auftritt.(?)
Egon D. schrieb: > Das sehen die Herren von der PTB aber anders. > Siehe in beigefügtem Dokument Seite 354 links oben. > >> Die Kombination "alle Stufen 0" tritt nicht auf und >> darf auch nicht auftreten, weil dann nie wieder eine 1 >> ins Schiebregister injiziert würde. Es kämen nur noch >> Nullen raus. > > Um genau das zu verhindert ist eine Zusatzbeschaltung > vorhanden; Ok. Egon D. schrieb: > es handelt sich daher NICHT mehr um eine der > üblichen Maximallängenfolgen Doch, die 000000000 gehört zur Folge, kann aber mit dem geXORten Schieberegister allein nicht hergestellt werden.
Beitrag "Re: Zufallsgenerator" eine LFSR-Tabelle von Motorola 1975, "Supercomputer" waren damals noch etwas kleiner
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.