LFSR Tabelle woher kommen die Werte?

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.

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. ;-)

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