MLS bei LFSR nachweisen

[Uwe_Beis]

Hallo zusammen,

ich hoffe, mit meiner Frage nicht ganz falsch hier zu sein.

Aus gegebenem Anlass beschäftige ich mich mit Linear Feedback Shift Registern, die die maximal mögliche Sequenzlänge von 2^N-1 haben sollen. Ich suche „ziemlich lange“ LFSR. Gefunden habe ich über Wikipedia als bisher interessantesten Beitrag http://www.xilinx.com/support/documentation/applicat…, wo LFSR mit bis zu 168 Bit Länge und angeblich maximaler Sequenzlänge aufgeführt sind.

Meine Frage ist, wie kann man nachweisen, das ein LFSR mit dem verwendeten Polynom die maximale Sequenzlänge hat? Das Ausprobieren nicht geht, dürfte jedem, der die Frage versteht, klar sein…

Grüße, Uwe

[Gezeiten]

Hallo Uwe,

ein LFSR hat die maximale mögliche Periodenlänge wenn das verwendete Generatorpolynom in GF(2) ein primitives Polynom ist:

Wikipedia: „Erzeugung von Pseudo-Zufallszahlen“
und
Wikipedia: "Funktion linear rückgekoppelter Schieber…

In der HW-Praxis werden gerne primitive Polynome mit nur drei Termen (Trinome) verwendet, weil sie die geringsten Anzahl Gatter benötigen. Ich vermute mal XILINX macht das auch, zumindest referenzieren sie, in dem von dir verlinkten Datenblatt, passende Literatur.

Primitive Trinome gibt es aber nicht für alle Werte von n. In diesen Fällen kann man auf Polynome mit 5 oder 7 Termen zurückgreifen. Da der Nachweis sehr aufwendig sein kann, greift man in der Praxis auf bekanntermaßen primitive Polynome zurück. Für diejenigen n