Hi, was beschreibt dieses Polynom überhaupt?? Finde im Internet nichts eindeutiges..
Hallo, dann schau doch mal http://de.wikipedia.org/wiki/Linear_r%C3%BCckgekoppeltes_Schieberegister und die Hauptanwendung http://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung an!!!
Habe ich mir schon angesehen... So wie ich verstanden habe setzt man nie werte für x ein sonder dass ist nur eine darstellung dafür wo XOR ve3rknüpfungen reimgeballert wurden... Dieses Polinom nennt man dann Generatorpolynom aber warum schreibt mann dass al Polynom???
Da scheint einiges an Theorie zu fehlen. Es beschreibt die Blidung der Zahl aus dem Bitstrom, resp hier fuer den Bitstrom.
florz schrieb: > Da scheint einiges an Theorie zu fehlen. Es beschreibt die Blidung der > Zahl aus dem Bitstrom, resp hier fuer den Bitstrom. Ja ich habe kein Plan. Welche Zahl ein Beispiel wäre nett.
Jan R. schrieb: > florz schrieb: >> Da scheint einiges an Theorie zu fehlen. Es beschreibt die Blidung der >> Zahl aus dem Bitstrom, resp hier fuer den Bitstrom. > > Ja ich habe kein Plan. > Welche Zahl ein Beispiel wäre nett. Edit: http://www.inf.fh-flensburg.de/lang/krypto/algo/lfsr-zufallsbits.htm für das Beispiel en Ist das Polynom doch x^4+x=c(x) oder was Meinst du mit Bitstrom? die Bitfolge am Ausgang? 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 das polinom hat an der stelle 2^n-1 den wert 50640. Die Binärbitfolge wäre dezimal die zahl 3929 Welchen sinn hat das Polynom???? Was du gesagt hast war ja offensichtlich auch nicht richtig
Habe gerade mal geguckt die Polynome sind ja mit Modulos verknüpft.. also 1100010111000001 = 15^4 15=1111 also ist das ganze modulo also XOr 1100010111001110 dann nochmal modulo mit 1 dann ist das ganze 1100010111001111 ok keine Übereinstimmung mit der Bitfloge am Ausgang... dann habe ich gelesen, dass man das generatorpolynom mit dem Initialisierungspolynom multiplizieren muss also wohl x also dann gesammt x^5+x^2+x 15^5 = 10111001011001001111 15^2 = 11100001 15 = 1111 Mod = 10111001011010100001 was mit der Ursprünglichen Zhlenfolge auch nichts zu tuen hat, also erklärt mir bitte was ich falsch mache, dass sind die Infos, die ich aus demNetz schlagen konnte...
Das ist der momentane stand.. Das Polygon beschreibt offensichtlich ja nicht die ausgangsbits einer Periode... Was machen sie dann?? Oben habe ich ja nochmals was von Notstrom gehört aber dass ist doch der Ausgang oder ??
Hallo, du solltest dir jemanden in deiner Nähe suchen der Dir das Rechnen im Polynom-Ring über dem Körper F2 erklärt. Insbesondere wie man dort Polynome addiert, subtrahiert, multipliziert und vor allem wie man dividiert. Denn das was in einem linear rückgekoppeltem Schieberegister bei jedem Takt passiert ist nichts anderes als ein Rechenschritt bei einer fortgesetzten Polynomdivision. Der Divisor ist hierbei das sogenannte Generatorpolynom. Das "Bitmuster" das du immer versuchst als Zahl darzustellen repräsentiert hierbei die Koeffizienten der beteiligten Polynome und hat nichts mit einer Binärzahl zu tun. Übrigens: die Addition zweier Koeffizienten aus F2 entspricht dabei genau der XOR Verknüpfung mit der Überraschung dass 1+1 gleich 0 ist. Also noch mal: such dir Jemanden der Dir das erklärt und sofort auf deine Fragen eingeht. Schriftlich hier im Forum wird das nichts.
> > Also noch mal: such dir Jemanden der Dir das erklärt und sofort auf > deine Fragen eingeht. Schriftlich hier im Forum wird das nichts. Was Ringe und Körper sind weiß ich, aber irgendwie ist mir nicht klar wie man das hier anwendet. Ich mache dass alles im Selbststudium weshalb ich nicht weiß, wo genau und wen ich da fragen soll. Da ich ja aber weis, was Ringe und Körper sind, würde mir es vielleicht helfen, wenn du oder auch jemand anderes mir dass mal mithilfe dieses Beispiels aus dem PDF vorrechnet...
Das einzige was ich nicht kapiere ist, wie die Koeffizienten (die meiner Meinung nach auch nur 1 und 0 annehmen können), dieses bitmuster am Ausgang beschreiben. Was ist eigentlich der Dividende, wenn das Generatorpolynom der Divisor ist. Wie gesagt ein Beispiel anhand eines rechenwegs sagt wohl mehr als noch tausende worte...
Hallo also mal kurz zu dem Beispiel aus http://www.inf.fh-flensburg.de/lang/krypto/algo/lfsr-zufallsbits.htm Das Beispiel ist kein besonders schönes da die Art der Rückkopplung einem Fibonacci-LFSR entspricht und damit keiner einfachen Grundrechnungsart im Polynomring. Hier ist die Erweiterung bei jedem Takt der maßgebliche Schritt. Der neue Wert für r1 errechnet sich immer mit r1*a1 + r2*a2 + r3*a3 + r4*a4 wobei die r1, r2, r3, r4 die Inhalte des Schieberegisters sind und a1, a2, a3, a4 die Koeffizienten des Generator-Polynoms. Beachte dass all diese Werte nur den Zustand 0 oder 1 annehmen können und * einer UND Verknüpfung und + einer XOR Verknüpfung entspricht. Wesentlich schöner sind die Galois-LFSR da hier jeder Schritt (Takt) dem einer Polynomdivision entspricht und die geht so: Betrachte das Generatorpolynom x4 + x3 + 1 (höchster Grad links, kleinster rechts) dann entspricht das dem Bitmuster 11001 des Weiteren nehmen wir das Polynom 1 (= Anfangszustand im Schieberegister 0001) und jetzt teilen wir 1 / (x4 + x3 + 1) Die Rechenschritte sind jetzt ähnlich denen einer Division im Dezimalsystem, immer wenn ... nicht subtrahierbar wird eine Stelle nach links geshiftet, d.h. erweitert (im Dezimalsystem wäre das die Erweiterung mit 10 ) 0001 : 11001 = 00011….. (alle 0,1 sind Koeffizienten eines Polynoms, keine Binärzahl) ------------------------------------------------------ 0001 start 0010 nur erweitert 0100 nur erweitert 1000 nur erweitert 10000 jetzt erweitern und wegen überlauf in die nächste Stelle -11001 den Divisor subtrahieren (geht Koeffizientenweise mit XOR) ------ 1001 10010 erweitern und wegen überlauf in die nächste Stelle -11001 wieder subtrahieren (Koeffizientenweise mit XOR) ------ 1011 . . . . und so weiter. Wenn du jetzt nur alle 4 stelligen Bitmuster betrachtest hast du eine Folge aller möglichen 4bit-Kombinationen und das Ergebnis selbst ist eine Folge von Pseudozufallbits (Anmerkung: die Subtraktion in F2 ist identisch zur Addition (XOR) da die 1 invers zu sich selbst ist und 0 das neutrale Element bezüglich der Addition ist)
Siehst du hat mir super geholfen. . Wie würde man dann mit dem Fibonacci-LFSR weiter rechnen
Michael schrieb: > Hallo > > also mal kurz zu dem Beispiel aus > > 0001 : 11001 = 00011….. (alle 0,1 sind Koeffizienten eines Polynoms, > keine Binärzahl) > ------------------------------------------------------ > 0001 start > 0010 nur erweitert > 0100 nur erweitert > 1000 nur erweitert > 10000 jetzt erweitern und wegen überlauf in die nächste Stelle > -11001 den Divisor subtrahieren (geht Koeffizientenweise mit XOR) > ------ > 1001 > 10010 erweitern und wegen überlauf in die nächste Stelle > -11001 wieder subtrahieren (Koeffizientenweise mit XOR) > ------ > 1011 > . > . > . > . > und so weiter. Dieses 00011 ist das die Ausgangsbitfolge. > Wenn du jetzt nur alle 4 stelligen Bitmuster betrachtest hast du eine > Folge aller möglichen 4bit-Kombinationen und das Ergebnis selbst ist > eine Folge von Pseudozufallbits Was meinst du mit nur alle 4Stelligen. > Warum nennt man das eigentlich alles Zufallsbit das ist doch berechenbar.
Das heißt zuerst hat man 0001dann 0010 , 0100 , 1000 Dann 1001 Dann 1011 usw. I'm register. Have ichmdas aus deiner rechnung richtig abgelesen?? Dann it's doc haberdashery nichts surf all sondern 100% ig berechenbar.
Ja nix Zufall, sondern 100% berechenbar und reproduzierbar. dafuer mit definierter periode. Ein 10 bit LFSR wiederholt sich nach 2^10 = 1024 bit. Wenn man nun Zufall spielen will, so nimmt man ein LFSR, das laenger ist, als das Zielsystem es merken wuerde. Und das ist schnell machbar. Bei Xilinx findet man Polynome mit sehr hoher Laenge,
Sind die werte, die ich aus dem Beitrag von Michael abgelesen habe denn richtig??
Jan R. schrieb: > Hi, > > was beschreibt dieses Polynom überhaupt?? Es beschreibt einen endlichen Restklassenkörper; in der Regel einen der Characteristik 2, weil darin so schön einfach zu rechnen ist. Sei
mit einem über F_2 irreduziblen Polynom vom Grad n erhält man dann den endlichen Körper mit n Elementen durch Restklassenbildung aus dem Polynomring in einer Variablen F_2[x]:
Diese Konstruktion ist ganz analog zur Konstruktion der Komplexen Zahlen aus den Reelen Zahlen: Man bildes den Polynomring R[X] und faktorisiert das irreduzible Polynom x²+1 heraus (dieses Polynom ist irreduzibel über R):
Die Rechenregeln für LFSRs, die man quer durchs Netz findet, stellen lediglich die für eine Implementierung mundgerecht hingeschriebene Arithmetik über solchen endlichen Körpern dar. Eine Multipliketion mit x enspricht zum Beispiel einem Shift um 1. Beispiel für n = 2: x²+x+1 ist irreduzibel über F_2, die Elemente von F_2^2 können geschrieben werden als 0, 1, x und x+1 wobei x eine formale Nullstelle des erzeugenden Polynoms ist (analog wie bei den Komplexen Zahlen, wo i eine formale Nullstelle von x²+1 ist). Geschrieben als Bitstring mit dem höchsten Koeffizienten links: 0, 1, 10 und 11 (0, 1, x und x+1). Multiplizieren wir 11 (also x+1) mit x, dann ist das 110 (x²+x). Wegen x²+x+1 = 0, was gleichbedeutend ist mit x²=x+1, kann x² durch x+1 ersetzt werden: 110 = 10 + 11 = 1. Hier sieht man nun die Einfahcheit der Arithmetik: Addition entspricht einem XOR, denn in Characteristic 2 ist 1+1=0. Multiplikation mit x entspricht einem Shift um 1 nach links, d.h. bei allen Monomen wird der Exponent um 1 erhöht. War der höchste Koeffizient (der bei n-1) gleich 0 passiert nix, man schiebt eine 0 raus. War der höchste Koeffizient 1, dann hat das neue Polynom die gestalt x^n+... (eine 1 rausgeschoben). Das x^n kann durch ein Polynom vom Grade höchstens n-1 ersetzt werden wegen p(x) = 0. Die Addition liefert das XOR bei der LFSR-Arithmetik. Diese Beschreibung als endliche Körper mag zunächst kompliziert klingen und voll unnötog sein, aber sie gibt einem das Rüstzeug in die Hand, LFSRs theoretisch zu analysieren oder Fehlerkorrekturcodes zu schaffen. Mit dem Bitgewusel würde man sehr schnell den Überblick verlieren, während man bei der mathematischen Beschreibung den kompletten Werkzeugkasten der Algebra drauf anwenden kann, und der ist nicht gerade klein :-)
:
Bearbeitet durch User
Johann, dein Wissen in allen Ehren, aber da raucht mir auch der Schädel ein wenig ;-) Wie auch immer, bei mir kam damals der "Klick" Moment, als ich Begriff, dass bei derartigen Geschichten die Bits nicht als irgendeine (Integer) Zahl interpretiert werden, sondern jedes Bit stellt einen Koeffizienten von einem Polynom dar. Und dazu kann man nun sagen, dass dies spezielle Polynome sind, weil ein Bit, also der Bereich jedes Koeffizientens nur 2 Werte umfasst. Wie auch immer, DAMIT kann man nun eine bestimmte Form von Rechnungen durchführen, die allerdings gar nichts mehr mit den für einen "Normalsterblichen" bekannten Addition, Multiplikation und Co zu tun haben. Man benutzt also die Darstellung eines Polynoms, wobei die Koeffizienten das sind, womit nachher im Endeffekt "gerechnet" wird.
Einfach mal nach Gold-Codes googeln, oder die Dateien des US-Verteidigungsministeriums ansehen, die das GPS-Signal und seine Generierung erklären. GPSSPSA1 und GPSSPSA2 jeweils als PDF
Die Koeffizienten, können ja aber nur 1 oder 0 sein.
Jan R. schrieb: > Die Koeffizienten, können ja aber nur 1 oder 0 sein. So ist es. Klingt erstmal "billig" und unsinnig. Aber das ist es nicht. Der "Baukasten" vom Georg lässt sich trotzdem sehr schön anwenden.
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.