Hallo. In der als richtig bestätigten Implementierung des A5/1 Algorithmus, der aus der Mobilkommunikation bekannt ist, findet sich folgende Angabe (siehe http://www.scard.org/gsm/a51.html): /* Feedback taps, for clocking the shift registers. * These correspond to the primitive polynomials * x^19 + x^5 + x^2 + x + 1, x^22 + x + 1, * and x^23 + x^15 + x^2 + x + 1. */ #define R1TAPS 0x072000 /* bits 18,17,16,13 */ #define R2TAPS 0x300000 /* bits 21,20 */ #define R3TAPS 0x700080 /* bits 22,21,20,7 */ Wenn ich nun aber Wiki-Artikel zum Thema LSFR lese (https://en.wikipedia.org/wiki/Linear_feedback_shift_register), steht da Folgendes: feedback polynomial or reciprocal characteristic polynomial. For example, if the taps are at the 16th, 14th, 13th and 11th bits (as shown), the feedback polynomial is x^{16} + x^{14} + x^{13} + x^{11} + 1. Was ist denn nun der Zusammenhang zwischen den Generatorpolynomen (bzw im Idealfall primitiven Polynomen) und den Stellen, an denen die Rückkopplungsbits sein sollen?
Hallo, ohne mich auszukennen... VL schrieb: > #define R1TAPS 0x072000 /* bits 18,17,16,13 */ > #define R2TAPS 0x300000 /* bits 21,20 */ > #define R3TAPS 0x700080 /* bits 22,21,20,7 */ wandle die Zahlen in Binärzahlen um und beachten MSB-LSB, dann dürfte es Dir vermutlich klar sein. VL schrieb: > feedback polynomial or reciprocal characteristic polynomial. For > example, if the taps are at the 16th, 14th, 13th and 11th bits (as > shown), the feedback polynomial is x^{16} + x^{14} + x^{13} + x^{11} + > 1. Sagte eigentlich schon alles. Mit freundlichen Grüßen Guido
Mir ist klar, dass wenn ich eine Hexadezimal-Zahl ins Dualsystem umrechne, ich zB. aus 0x072000 die Zahl 01110010000000000000 bekomme, wo an 13, 16, 17, 18 Stelle, angefangen bei Index 0, das Bit gesetzt ist. Die Frage war, was das mit dem Polynom x^19 + x^5 + x^2 + x + 1 zu tun hat.
Es fehlt der Zusammenhang zwischen Generatorpolynom und Schieberegister : https://www.google.ch/search?q=Generatorpolynom+und+Schieberegister https://de.wikipedia.org/wiki/Linear_r%C3%BCckgekoppeltes_Schieberegister Beitrag "Linear Rückgekoppeltes schieberegister polynom" https://www.tu-chemnitz.de/informatik/ThIS/downloads/courses/ss03/kv/Schieberegister.pps https://www.secorvo.de/publikationen/linear-rueckgekoppelte-schieberegister-lfsr-fox-2008.pdf
Danke, aber ich habe mir auch schon die ersten vier Google-Ergebnisse dazu angeguckt. Auf http://www.iti.fh-flensburg.de/lang/algorithmen/code/crc/crc.htm steht zum Beispiel auch: Gegeben sei das Generatorpolynom g = x^5+x^2+x+1, entsprechend dem Wort 1 0 0 1 1 1. In dem von mir aufgeführten Beispiel enspricht das Polynom aber eben NICHT dem für die feedback taps verwendeten Wort.
Okay, Frage hat sich erledigt. Erste Antwort war doch hilfreich. 72000 und 80027 sind spiegelverkehrt in binary, wobei im mathematischen Tupel, also 80027, noch das MSB gesetzt wird. Ich hab mir das mit kurzen Tupeln angeguckt, da war das nicht ersichtlich.
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.