Hallo zusammen,
ich verwende bei einem Programm von mir eine library zur Berechnung
einer CRC16 prüfsumme. Um genauer zu sein handelt es sich um die library
von folgender Seite:
https://github.com/jdn-aau/sketchbook/tree/master/sketchbook/libraries/crc16
ich habe mittlerweile herausgefunden, dass sie ziemlich identisch ist,
mit der librarz aur Application Note AVR067 von atmel.
(http://www.atmel.com/images/doc2587.pdf).
In letzter Zeit habe ich mich jetzt etwas mehr mit CRC-Berechnung
beschäftigt und es ist ja so, dass man softwaremäßig zwei möglichkeiten
hat, eine CRC summe zu berechnen. Die eine ist, direkt jedes mal den
bit-string durch ein das entsprechende crc polynom zu teilen und somit
die entsprechenden Werte jedes Mal neu zu berechnen und die andere ist,
dass man sich die Werte vorab berechnet und sie in einer lookup Tabelle
speichert und dann nur jedes mal quasi nachsieht, was für ein Wert jetzt
"drankommt".
Meine Frage jetzt: kann mir jemand sagen, auf welchem Polynom die lookup
tabelle in oben genannter library basiert?
Wie kann ich das rausfinden?
Wenn du das Polynom im Quellcode findest und mir sagen kannst, welches
es ist wäre ich dir sehr Dankbar, du würdest mich von einer wilden
Sucherei erlösen. Vielleicht bin ich ja echt einfach nur blind und
übersehe es die ganze Zeit. Aber ich kann im Quellcode keine Angabe zu
dem Polynom finden.
Power schrieb:> dass man sich die Werte vorab berechnet und sie in einer lookup Tabelle> speichert und dann nur jedes mal quasi nachsieht
Auf was mag wohl dieser Kommentar hindeuten?
Da guckst Du: Zeile 60: "/* 16 bit FCS lookup table per RFC1331 */
Dann tippst Du "RFC1331" in die Suchmaschine Deiner Wahl.
Findest z.B.: https://www.ietf.org/rfc/rfc1331.txt
Da guckst Du wieder:
"B. Fast Frame Check Sequence (FCS) Implementation
B.1. FCS Computation Method
The following code provides a table lookup computation for
calculating the Frame Check Sequence as data arrives at the
interface. This implementation is based on [7], [8], and [9]. The
table is created by the code in section B.2.
"
Guckst Du noch mal unter B.2
Liest Du: "
/*
* The HDLC polynomial: x**0 + x**5 + x**12 + x**16 (0x8408).
*/
"
Mark Brandis schrieb:> Power schrieb:>> dass man sich die Werte vorab berechnet und sie in einer lookup Tabelle>> speichert und dann nur jedes mal quasi nachsieht>> Auf was mag wohl dieser Kommentar hindeuten?>> /* 16 bit FCS lookup table per RFC1331 */
Ich weiss es nicht, sag dus mir? Für was steht FCS und für was steht
RFC1331? Ich kann darin kein Polynom erkennen?
x^8 + x^3 +x^1 oder sowas in der art ;)
Klaus schrieb:> * The HDLC polynomial: x**0 + x**5 + x**12 + x**16 (0x8408).
Danke Klaus, das war das was ich gesucht habe!
Ich bin da nicht drauf gekommen. Danke für deine Hilfe.
Holger: Kauf dir selber erst mal ne brille
Ah. Wenn Du die Frage jetzt stellen kannst, warum konntest Du sie
nicht gleich im Eröffnungspost stellen? :-) Aber abgesehen davon "RFC"
mal kurz in eine Suchmaschine eingetippt hilft auch hier weiter. Für's
nächste Mal. ;-)
Klaus schrieb:> Aber abgesehen davon "RFC"> mal kurz in eine Suchmaschine eingetippt hilft auch hier weiter.
Ja, mir war nur nicht bewusst, dass das RFC1331 für das polynom steht.
Hätte ich das gecheckt dann hätte ich das natürlich gegoogelt ;)
Und ich werde versuchen das nächste Mal meine Frage von anfang an
deutlicher zu formulieren ;)
Danke auf jeden Fall nochmal!
Power schrieb:> Ja, mir war nur nicht bewusst, dass das RFC1331 für das polynom steht.> Hätte ich das gecheckt dann hätte ich das natürlich gegoogelt ;)
Tut mir leid. Leider falsch. Nochmal googeln, bitte.
Power schrieb:> kann mir jemand sagen, auf welchem Polynom die lookup> tabelle in oben genannter library basiert?> Wie kann ich das rausfinden?
Das müsste der CCITT-CRC (oder auch HDLC-CRC) sein. Die interessante
Information ist der Startwert und der "Gutwert" in Zeile 55 und 56.
Stefan Wagner schrieb:> Die interessante> Information ist der Startwert und der "Gutwert" in Zeile 55 und 56.
Hey,
auch dir danke für deine Hilfe. Mich würde aber einmal interessieren,
wie man von den beiden Zahlen 0xFFFF und 0xF0B8 auf das Polynom kommt?
Und auch was die Zahl 0x8408 damit zu tun hat? ich dachte die Hex-Zahl
steht transferiert zu einer binären zahl dafür die 1er und 0er im
polynom mit dem die X°n multipliziert werden?
also wäre dann
1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 = 0x8821 das oben genannte polynom. Aber
das ist ja offensichtlich falsch?
Power schrieb:> Mich würde aber einmal interessieren,> wie man von den beiden Zahlen 0xFFFF und 0xF0B8 auf das Polynom kommt?
Das ist eine Besonderheit des für HDLC definierten CRC.
Der Startwert ist mit 0xFFFF vorgegeben (sonst oft 0) und der berechnete
CRC wird invertiert (Einerkomplement) übertragen. Ein über ein korrekt
übertragenes Frame berechneter CRC muss dann 0xF0B8 ergeben.
Hat man viel damit zu tun, bleiben die beiden Werte irgendwann im
Gedächtnis :-)
Grüße
Stefan
g ich hab leider bisher noch so gut wie garnichts damit zu tun gehabt.
Habe nur mittlerweile einige Sachen darüber gelesen. Und da habe ich
jetzt schon wieder das nächste Problem. So wie ich die CRC Prüfsumme
bisher verstanden hatte dachte ich, es würde immer ein anderer Wert,
abhängig von der bitfolge über die der CRC berechnet wird rauskommt,
dieser an die ursprüngliche bitfolge addiert wird und somit beim
empfänger nach dem CRC check 0 rauskommt (egal ob mit dem Startwert 0
oder 0XFFFF begonnen wird). Jetzt schreibst du aber:
Stefan Wagner schrieb:> Ein über ein korrekt> übertragenes Frame berechneter CRC muss dann 0xF0B8 ergeben.
Wie passt das zusammen? Heißt das einfach, dass hier anstelle von 0 beim
Empänger immer 0xF0B8 rauskommen muss? Was hat das für einen Vorteil?
Man bildet über seine Daten einen CRC-Wert.
Den CRC-Wert hängt man am Ende der Daten mit dran.
Will man checken ob die Daten korrekt übertragen worden sind, bildet man
nochmal den CRC-Wert über alle Daten einschließlich dem CRC-Wert der
übertragen worden ist. Dieses Ergebnis muss einen Bestimmten Wert haben,
ist das der Fall ist kein Fehler aufgetreten.
Bei den meisten CRC-Berechnungen ist der Startwert 0x0000 und am Ende
von der Überprüfung muss ebenfalls 0x0000 rauskommen.
Wie Stefan Wagner schon schrieb, ist es bei HDLC anders.
Der Startwert ist nicht 0x0000 sondern 0xFFFF
und am Ende der Überprüfung soll nicht 0x0000 rauskommen sondern 0xF0B8.
Christian K. schrieb:>> Bei den meisten CRC-Berechnungen ist der Startwert 0x0000 und am Ende> von der Überprüfung muss ebenfalls 0x0000 rauskommen.
Das hat den Nachteil, dass man Anfang und am Ende des Datenblocks Nullen
hinzufügen oder löschen kann ohne dass es zu einem CRC Fehler führt.
Mit 0xFFFF als Startwert und dem Residual != 0 werden auch solche Fehler
detektiert.
Christian K. schrieb:> Ja, aber nur wenn die Soll-Länge des Datenblocks nicht bekannt ist.
Was bei HDLC aufgrund des Konzepts der Frame-Begrenzung durch die
Flag-Oktette der Fall ist.
Grüße
Stefan
