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?
Nachschauen? Wenn Du im Quellcode nachschaust, was für Probleme treten auf? Sehunschärfe? Dunkelheit? Spielende Kinder? Wir helfen gerne.
Wenn du mir sagen kannst, wo im Quellcode das Polynom steht kauf ich dir eine Brille ab ;)
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?
1 | /* 16 bit FCS lookup table per RFC1331 */
|
holger schrieb: > 0x1189 das ist der zweite Wert der lookup tabelle. Wie kommst du darauf, dass das gleichzeitig das zu grunde liegende Polynom ist?
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.
1 | #define FCSINIT 0xFFFF
|
2 | #define FCSGOOD 0xF0B8
|
In diesem Fall wäre das Generatorpolynom
Grüße Stefan
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.
Ja, aber nur wenn die Soll-Länge des Datenblocks nicht bekannt ist.
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
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.