CRC16-CCITT Polynom Verständnisproblem

[Ano N. (oorim)]

Hi

Ich habe ein kleines Verständnisproblem mit CRC16-CCITT. Das Polynom das 
benutzt werden soll ist

$$x^{16}+x^{12}+x^5+1$$

das wäre ja im grunde
0b1001000000100001 = 0x9021
Es soll aber sein
0b1000000100001 = 0x1021
was wiederum ein polynom von

$$x^{12}+x^5+1$$

wäre. Ich vermisse also die letzte stelle. Wo ist sie hin?

Oder besser gesagt: Wo ist mein Denkfehler? Ein weiteres Problem das ich 
habe ist, wie kann ich das ganze testen? Das Datenblatt müsste mir 
aufschluss darüber geben, kostet aber solide 138chf und das ist mir für 
eine PDF doch etwas viel Geld ...


Grüße

ICh arbeite mich gerade hier durch
http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
und dort ist das Polynom
0x8810 = 0b1000100000010000

Da fehlt mir nun die 1 ...

[Anja (Gast)]

Ano Nym schrieb:
> Ich vermisse also die letzte stelle. Wo ist sie hin?

Die letzte Stelle (2^16 und nicht wie bei dir 2^15) wird ja wieder aus 
dem Schieberegister an die Stelle 2^0 geschoben.

Gruß Anja

[Ano N. (oorim)]

Blöd gefragt: Welches Schieberegister? Das ist doch nur eine Zahl die 
ich benutze um die Prüfsumme herzustellen. Wie ich sie herstelle, mit 
einer Tabelle, einer for-Schleifeo der einem hardware Schieberegister, 
ist dabei doch noch einerlei?

[Jürgen (Gast)]

Weil in dem Polynom für einen n-bit CRC immer x^n enthalten ist,
lässt man das im Hex-Code weg.

Sonst müsste es auch 0x11021 heißen, nicht 0x9021.

[Ano N. (oorim)]

Naja 16 bit wäre von 0 bis 15 und damit würde alles reinpassen oder steh 
ich grad komplett auf dem Schlauch?

[Jürgen (Gast)]

> Naja 16 bit wäre von 0 bis 15 und damit würde alles reinpassen

1 = x^0

x^0, ..., x^16 macht insgesamt 17.

[Ano N. (oorim)]

Ah ... ich hab falsch gezählt :D Dann find ich die "schreibweiße" 
dennoch etwas bescheuert ...

Aber was nehm ich nun - 0x1021 oder 0x8810?


PS: Ist nicht so das ich gar keine Ahnung habe auch wenn das hier so 
rüber kommt - ich steh irgendwie neben mir seit ein paar Wochen...

[Huch (Gast)]

Du musst Dich halt mal entscheiden ob Du die Bits ab 0 oder eins zählst. 
Sonst wird das niw was.

Bei den CRC Polynomen wird ab 0 gezählt.

0b1001.0000.0010.0001 = 0x9021

entspricht x^15+x^12+x^5+1 und nicht x^16+x^12+x^5+1

Was Du angegeben bekommst ist:

x^12+x^5+1

Dabei wird bei CRC16 immer implizit von x^16 ausgegangen,
also x^16+x^12+x^5+1 also 0b1.0001.0000.0010.0001 = 11021.

[Jürgen (Gast)]

Für Testvektoren siehe auf

http://www.itu.int/rec/T-REC-X.25-199610-I/en

das englische PDF Appendix I Seite 153

[Ano N. (oorim)]

Danke für die Testvektoren das ist awesome. Das schau ich mir später mal 
an

Ich zähl generell von 0 an ich hab aber mich selbst ein wenig mit dem 
Zählen verwirrt

Kurz geschaut und ich komm auf 1021 - dabei hab ich x^16 geflissentlich 
ignoriert da es ja nich reinpasst von 0 bis 15 ;)

Wenn ich jetzt x^16 rausschieb und wieder an die erste stelle setze 
müsste doch eigentlich was mit der ersten Stelle passieren oder? Also 
entweder addiert (dann wären die ersten beiden 10 und nicht 01) oder ein 
left shift (dann wären die ersten beiden stellen 11).

Man oh man sowas peinliches - ich steh sowas von neben mir das ist nicht 
mehr schön ....



Aaaaalso ich denke ich nehme dann 1021 und wenn der rest 0 ist freu ich 
mir einen Keks ^^ Wie ich das berechne muss ich mir noch anschauen, gibt 
ja mehrere Versionen. Aber ich denke ich nehme die Version mit der 
lookup table da die wohl die schnellste ist. Aber da muss ich noch ein 
wenig research betreiben.



PS: Tut mir leid wenn ich ab und an englische Wörter reinwerf - ich 
sprech den Alltag über Englisch und schreibe auf Deutsch - da werf ich 
oft mal was durcheinander.

[Ano N. (oorim)]

PPS: Ich habe nun das ISO file gefunden - durch Zufall im Netz - und das 
sagt mir folgendes:
The CRC polynomial (0x1021) is x16+x12+x1
The implemented version of the CRC check has the following 
characteristics
reverse CRC CCITT 0x8048
data stream has LSB first
the CRC shift register is initialied to all 16 bits equal to zero
the first data bit (LSB data) is XORed with the LSB of the register is 
shifted in to the registers MSB
after the 64 shifts (64 data bits are shifted) the register contains the 
BCC

damit lässt sichs ja arbeiten. Ich werde jetzt sehen das ich Algorithmen 
für normale berechnung in einer Schleife und mit Tabelle finde (+ den 
Algortihmus zum erstellen der Tabelle) und dann wede ich ein wenig 
Matlaben.

Ich weiß ja jetzt das ich 8048 nehmen muss als Polynom bzw Divisor :)

[eProfi (Gast)]

Es wäre schön, wenn Du einen Link angeben oder das File anhängen 
könntest.