Forum: Digitale Signalverarbeitung / DSP / Machine Learning LFSR Tabelle woher kommen die Werte?


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Ch. K. (Gast)


Lesenswert?

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

von chris_ (Gast)


Lesenswert?

Es geht um Maximallängen der rückgekoppelten Struktur.

Du kannst dich in die Mathematik zu

Maximum Length Linear Feedback Shift Registers

einlesen .....

von chris_ (Gast)


Lesenswert?


von Jürgen S. (engineer) Benutzerseite


Lesenswert?

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.

von Egon D. (Gast)


Lesenswert?

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.

von Hp M. (nachtmix)


Lesenswert?

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
von Egon D. (Gast)


Angehängte Dateien:

Lesenswert?

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.

von Signal-Analysierer (Gast)


Lesenswert?

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.

von Signal-Analysierer (Gast)


Lesenswert?

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.(?)

von Hp M. (nachtmix)


Lesenswert?

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.

von Christoph db1uq K. (christoph_kessler)


Lesenswert?

Beitrag "Re: Zufallsgenerator"
eine LFSR-Tabelle von Motorola 1975, "Supercomputer" waren damals noch 
etwas kleiner

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.