CRC16 per Hand berechnen - Fehler

[Sebastian H. (sebastian90)]

Hallo zusammen,
ich habe ein Problem mit meiner CRC-Berechnung von Hand.  Mit der 
Funktion _crc16_update(uint16_t crc, uint8_t data)der Bibliothek 
<util/crc16.h>, sowie mit dem Online Rechner von Lammertbies bekomme ich 
als berechneten CRC-Wert 0x40BF für eine Berechnung mit dem Polynom: 
0xA001 und dem Startwert 0xFFFF und einem Datenbyte 0x00.  Wenn ich es 
von Hand berechne komme ich absolut nicht auf diesen Wert.  Im Anhang 
ist meine Berechnung.  Kann mir vll jemand meinen Fehler sagen.  Ich 
habe auch schon versucht ohne die angehängten Nullen, oder mit dem 
Startwert angehängt ohne Nullen zu rechnen, aber in keinem Fall bin ich 
auf die Lösung des Online Rechners bzw. der Software gekommen.


Gruß

Sebastian

[Sebastian H. (sebastian90)]

Hat keiner eine Idee wo mein Fehler liegt?

[Jochen (Gast)]

Hallo,

vielleicht falsches Polynom?

Wenn ich hier auf dieser Seite:
http://www.zorc.breitbandkatze.de/crc.html

CRC order: 16
CRC polynom: 8005
Initial value: FFFF
Final XOR: 0000
Beide Häkchen an
Data Sequence: %00

einstelle bekomme ich als CRC: 0x40BF

Dein Polynom in der Excel Tabelle ist aber 0xA001 und NICHT 0x8005. 
(Kann aber auch Zufall sein)

Auch dann kommt nicht das richtige Ergebnis raus.

CU,
Jochen

[Sebastian H. (sebastian90)]

Hallo,
erstmal Danke für die Antwort.
Ich bin davon ausgegangen, dass meine Funktion _crc16_update() das 
Polynom 0xA001 verwendet, laut 
http://www.nongnu.org/avr-libc/user-manual/group__util__crc.html . Aber 
ich werde die Berechnung auch mal mit dem anderen Polynom versuchen.

Gruß
Sebastian

[Jochen (Gast)]

Hallo,

da bin ich wieder:

Mir ist aufgefallen, dass deine 'angehängten Nullen' nur 15 Byte lang 
sind. Das ist doch bestimmt ein Fehler oder?!

Aber das ist auch nicht die Lösung.

Wenn du auf der von mir verlinkten Seite nach unten scrollst wirst du 
einige Polynome finden wie z.B.:
CRC-16:     0x8005      =  x^16 + x^15 + x^2 + 1
Die 1 am Ende steht für x^0.
Dieses Polynom ist also eigentlich nicht wie man bei einem flüchtigen 
Blick annehmen möchte 16 sondern 17Bit lang. Das 17.Bit geht auch in der 
Berechnung einfach unter.

Um es auf deine Excel Tabelle zu übertragen bedeutet das, dass dein 
Polynom nicht bei C3 sondern erst bei C4 beginnt. Wenn du das konsequent 
befolgst sollte in Zeile 10  0x5FB1 stehen.

CU,
Jochen

[Sebastian H. (sebastian90)]

Hallo,
ich habe nicht ganz verstanden was du damit meinst erst bei C4 zu 
beginnen.  Was kommt dann in C3 ?  In meinem Bild hab ich mal das 
Polynom erst bei C4 angesetzt aber ich sehe da keinen Unterschied ausser 
das eine Zeile leer ist.  Welches Polynom muss ich überhaupt verwenden: 
1000000000000101 (x^15 - x^0) oder 11000000000000101 (x^16 - x^0) ?  Ich 
bin davon ausgegangen, das es eine CRC16 ist dass mein Polynom 16 Bits 
also von x^15 bis x^0 hat und ich 16 Nullen an meine Daten anhänge. 
Stimmt das so?

Gruß
Sebastian

[Jochen (Gast)]

Hallo,


ich hab mal wieder Zeile und Spalte vertauscht. Es soll natürlich D3 und 
nicht C4 heissen.

Zur Sicherheit hab ich es nun auch mal in Excel ausprobiert und das 
Ergebnis angehängt.

Wenn du die 16 roten Bits von rechts nach links interpretierst kommen 
auch die gewünschten 0x40BF heraus.

CU,
Jochen

[Tastkopf (Gast)]

Warum willst du das denn von hand rechnen? CRC16 ist nich gleich CRC16, 
neben den unterschiedlichen startwertmöglichkeiten, XOR am ende und den 
unterschiedlichen polynomen gibt es auchnoch Refin und Refout als 
Boolparameter. Üblicherweise rechnet man nur den klassischen crc16 von 
Hand, ohne die ganzen Erweiterungen, und für den praktischen Einsatz 
nimmt man die optimierten Funktionen die jemand mal entwickelt hat.
aber da du es ja von Hand rechnen möchtest:
für refin und refout = true nimmt man eine andere Formel wie für refin 
und refout = false. Wie sich das auf die Berechnung von Hand auswirkt 
weis ich leider nicht.

"There are really only two forms: normal and reflected. Normal
shifts to the left and covers the case of algorithms with Refin=FALSE
and Refot=FALSE. Reflected shifts to the right and covers algorithms
with both those parameters true."

http://www.ross.net/crc/download/crc_v3.txt
Kapitel 18.

SRP16 ist ein sehr nützliches Tool wenn man mit CRC arbeitet, dem prog 
gibst du deine Checksumme und die Daten und es liefert die die möglichen 
CRC verfahren zurück. da kannst du theoretisch auch mal reinstopfen was 
du von hand errechnet hast, vielleicht zeit es dir ja deinen Fehler.
FsumFrontEnd is auch recht nützlich.

[Sebastian H. (sebastian90)]

Hallo,
ich glaube jetzt hab ichs verstanden.  Also ich beginne sozusagen eine 
spalte später, weil mein Polynom normalerweise 11000000000000101 wäre 
aber die organgene 1 (x^16) exor 1 wird immer null also kann man sie 
weglassen.  Und die angehängten Nullen die ich vorher hatte fallen weg, 
da ich mit einem Startwert anfange und der vorne angestellt ist. Ist das 
so korrekt?

@ Tastkopf
Die Berechnung von Hand ist nur für meine Software-Dokumentation um 
nachzuvollziehen was genau die Funktion _crc16_update() der <util/crc16> 
macht.

Vielen Dank

Gruß
Sebastian