Welche Bits müssen bei einem LFSR rückgekoppelt werden?

[Ohm-Mega]

hallo,
ich war mir nicht ganz sicher ob meine frage in dieses forum gehört oder in das über elektronik.
hat denk ich mit beidem bisschen was zu tun ;)

also:
man kann, in dem man einzelne bits eines schieberegisters rückkoppelt ja einen einfachen zufallsgenerator erzeugen.

je nachdem wie geschickt man die rückgekoppelten bits wählt können dann maximal 2 hoch die anzahl der bits - 1 zufallszahlen erzeugt werden.

für ein schieberegister mit 3-bit wären das das 2te und das 3te bit.
bei einem 5bit schieberegister das 5te und das 3te.

allerdings werden derartige zufallsgeneratoren ja hauptsächlich mit einer sehr großen anzahl an bits verwendet, da eben nur (2^n)-1 zufallszahlen erzeugt werden können.

für diese sehr langen schieberegister wäre es aber zu aufwändig die bits die man rückkoppel muss experimentell herauszufinden.

deswegen meine frage:
kann man irgendwie berechnen welche bits rückgekoppelt werden müssen?

mfg

[mare_crisium]

Ohm-Mega,

in dem Beitrag von Christoph Kessler vom 22.01.2006 20:37, den Du unter diesem Link findest

http://www.mikrocontroller.net/topic/39989

ist die Tabelle der Sequenzlänge und der Rückkopplungsstufen angehängt. Zur Berechnung der Rückkopplungen findest Du jede Menge Literatur, wenn Du nach "Zufallsfolge" und "Schieberegister" googlest. Z.B. hier

http://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitstrom/3_Schieberegister/synlsr.pdf

Ist aber keine leicht verdauliche Kost ;-).

Ciao,

mare_crisium

[Ohm-Mega]

hi,
genau das mit dem "leicht verdaulich" war bei allem was ich bisher gefunden hab das problem ;)

mitlerweile glaube ich aber ein wenig schlauer zu sein.
das polynom mit dem man den zufallsgenerator beschreiben kann soll ein faktor von X^N+1 (wobei N = 2^n-1 ist) sein.

für 3bits würde das also folgendes bedeuten:
X^N+1 = X^7+1
X^7 +1 muss man nun in primfaktoren zerlegen.
X^7+1 = (X+1) (x^3 + x^1 + 1) (x^3 + x^2 + 1)

nun kann man die bits die rückgekoppelt werden müssen anhand der exponenten ablesen.
in diesem fall müssen also entweder 3 und 1, oder 3 und 2 rückgekoppelt werden.

genauso müsste das ja im prinzip auch mit jeder anderen Bit-Länge funktionieren.
aber wie muss man bei der zerlegung in einzelne faktoren vorgehen?

[mare_crisium]

Ohm-Mega,

leider kenne ich mich in diesem Gebiet nicht genügend gut aus, um Deine Frage kompetent beantworten zu können. Vllt. meldet sich noch jemand anderes, der Dir helfen kann.

Ciao,

mare_crisium