mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik CRC16-CCITT Polynom Verständnisproblem


Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

Ich habe ein kleines Verständnisproblem mit CRC16-CCITT. Das Polynom das 
benutzt werden soll ist
das wäre ja im grunde
0b1001000000100001 = 0x9021
Es soll aber sein
0b1000000100001 = 0x1021
was wiederum ein polynom von
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/koopma...
und dort ist das Polynom
0x8810 = 0b1000100000010000

Da fehlt mir nun die 1 ...

Autor: Anja (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Jürgen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Ano Nym (oorim)
Datum:

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

Autor: Jürgen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Huch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jürgen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Für Testvektoren siehe auf

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

das englische PDF Appendix I Seite 153

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 :)

Autor: eProfi (Gast)
Datum:

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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.