CRC: Unterschiede in Artikel auf mikrocontroller.net & Wikipedia

[Ralf (Gast)]

Hallo,

ich möchte Daten mittels CRC absichern. Dazu hab ich mir den hiesigen 
sowie den Wikipedia-Artikel zu Gemüte geführt, aber nach meinem 
Verständnis widersprechen sich die Informationen.

1) http://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung
2) http://www.mikrocontroller.net/articles/CRC

Beispiel:
In 2) steht einmal "Zum Beispiel bedeutet CRC16, dass das 
Generator-Polynom vom Grad 16 ist, sprich es hat 17 Bit." und direkt im 
nächsten Abschnitt "...wobei N die Anzahl Bits des Generatorpolynoms 
ist. (CRC16 -> 16 Bits)", also erst 17 und dann 16 Bit.
In 2) steht beim Beispiel mit einem Polynom 5.Grades -> "Gerechnet wird 
aber immer nur mit den unteren 5 Bit, hier also 00110.", es wird also 
die führende Eins weggelassen - in 1) wird im Beispiel ebenfalls ein 
Polynom 5.Grades verwendet, dort wird die Eins aber nicht weggelassen... 
Interessanterweise wird wiederum im echten Rechenbeispiel in 2) die Eins 
verwendet...

Insgesamt also verwirrend. Welcher Artikel stimmt denn nun?

Ralf

[crc0 (Gast)]

Ralf schrieb:
> Beispiel:
> In 2) steht einmal "Zum Beispiel bedeutet CRC16, dass das
> Generator-Polynom vom Grad 16 ist, sprich es hat 17 Bit." und direkt im
> nächsten Abschnitt "...wobei N die Anzahl Bits des Generatorpolynoms
> ist. (CRC16 -> 16 Bits)", also erst 17 und dann 16 Bit.
Da ist in der Tat etwas verwirrend. Ich würde
"wobei N die Anzahl Bits des Generatorpolynoms ist" durch
"wobei N der Grad des Generatorpolynoms ist" ersetzen.

Also CRC N, Grad N, höchste Potenz N, Prüfbits N, Länge/Bits des 
Polynoms N+1.

> In 2) steht beim Beispiel mit einem Polynom 5.Grades -> "Gerechnet wird
> aber immer nur mit den unteren 5 Bit, hier also 00110.", es wird also
> die führende Eins weggelassen

Vielleicht ist das Beispiel in der englischen WP besser geeignet. Man 
sieht sofort, dass die erste Stelle nicht berechnet werden muß, da sich 
dort entweder automatisch eine "0" ergibt (Input="1") oder für die 
Berechnung nicht relevant ist (Input="0").
Du kannst die Einzelschritte auch explizit durchführen und prüfen, ob 
das Ergebnis gleichbleibt.

00010111101100 000
   1011
00000001101100 000 <--- note that the divisor moves over to align with the next 1 in the dividend (since quotient for that step was zero)
       1011             (in other words, it doesn't necessarily move one bit per iteration)
00000000110100 000

http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Computation