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.
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.
Eine eigene Frage?
Dieser Thread ist über 10 Jahre alt.
Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.
