Forum: Mikrocontroller und Digitale Elektronik CRC8 mit Tabelle


von Jens (Gast)


Lesenswert?

Hallo zusammen,

ich wollte gerne eine CRC8 Checksumme erstellen über 4-11 Datenbytes.

Da das ganze schnell sein soll wollte ich mit einer Tabelle arbeiten.

Leider verstehe ich noch nciht so ganz wie das mti der Tabelle 
Funktioniert :(

Wie das CRC Verfahren in der Theorie Funktioniert weis ich, nur leider 
weiß ich noch nciht wie ich das perfekt in C einbauen kann.
Da es schnell passieren soll wollte ich diese Methode mit einer Tabelle 
nutzen, nur leider find ich keine Doku oder am besten sogar Code wo 
sowas mal erklaert wird.

Ich hoffe ihr könnt mir ein bissel Code oder gute Links geben wo das 
Verfahren für ein 8 Bit CRC Verfahren gut erklärt wird.


Gruß
Jens

von Markus (Gast)


Lesenswert?


von Totti (Gast)


Lesenswert?

Hi,

hier ist die Berechnung der CRC basierend auf Tabellen beschrieben:

    http://www.efg2.com/Lab/Mathematics/CRC.htm

Ist zwar Pascal-Code aber recht einfach nach C zu übersetzen.



Gruß, Totti

von C. S. (cees)


Lesenswert?

Hier mal ein Link mit Tabellenbasierendem Code - und dem Hinweis auf den 
"Painless Guide"...

http://forums.freescale.com/freescale/board/message?board.id=8BITCOMM&message.id=1152

von Jens (Gast)


Lesenswert?

Danke für eure Antworten!

Kann mir aber auch noch einmal einer erklären wie das System 
funktioniert?

Ganz dumm gefragt "Wofür ist eigentlich die Tabelle da?" ???

Vielleicht muss mir doch noch einmal jemand das Konzept von dem CRC 
Handling erklären.

Also ich will 5-8 Bytes von einem Controller an den anderen Senden. Das 
9te Byte ist dann für das CRC Byte.


Beim sender ruf ich dann eine Funktion auf mit den Datenbytes und dem 
Polynom. Diese Funktion berechnet mir die Checksum und ich übertrage die 
Datenbytes mit der Checksum, oder?

Der Empfänger weiß ja welches Polynom benutzt wurde. Er empfängt die 
Daten, und berechnet auch die Checksum und vergleicht die Danach mit der 
übertragenen Checksumme oder?

Wobei mir gerade einfällt das die Datenbytes sich bei der CRC Berechnung 
auch ändern und nicht gleich bleiben oder?

Nun ist meine Frage einmal ob das so stimmt oder wie man es besser 
formulieren kann und die andere Frage, wie arbeitet nun die Tabelle 
dabei?
Da ich mit 8Bit nur 256 Zustände haben kann stehen dann in der Tabelle 
alle Werte von 0 bis 255 jeweils mit dem Polynom XOR't oder? Dann in 
meiner CRCBuild Funktion muss ich also gucken welchen Wert mein Byte 
hat, geh an die Stelle in der Tabelle und habe das Ergebnis von dem Byte 
? Aber wie mache ich das mit mehreren Bytes?

Ach irgendwie versteh ich das noch nciht so ganz wie ich da nun schnell 
und Sinnvoll mehrere Bytes bearbeite :/

Ich hoffe einer kann mir das mal für "dummys" erklären :(

von Thomas (Gast)


Lesenswert?

Hallo,

die CRC-Berechnung funktioniert ungefaehr so wie du schreibest. Ein 
C-Pseudo-code wuerde dann so aussehen:
1
int crc;
2
char buf[] = "123456789";
3
int buf_len = 9;
4
int i;
5
6
crc = crc_init();
7
for (i = 0; i < buf_len; i++) {
8
   crc = crc_update(crc, &buf[i], 1);
9
}
10
crc = crc_finalize(crc);
11
printf("0x%04x\n", crc);

Eine vereinfachte Form ist:
1
crc = crc_init();
2
crc = crc_update(crc, buf, buf_len);
3
crc = crc_finalize(crc);

Diese Pseudo-code verwendet die Funktionen von pycrc 
(http://www.tty1.net/pycrc/). Dieser Code-Generator enthaelt auch 
Beispiel-Code. Vielleicht hilft dir das weiter.

Thomas

von Falk B. (falk)


Lesenswert?

@ Jens (Gast)

>Ganz dumm gefragt "Wofür ist eigentlich die Tabelle da?" ???

Sie ersetzt 8 Schiebe- und XOR Operationen.

>Polynom. Diese Funktion berechnet mir die Checksum und ich übertrage die
>Datenbytes mit der Checksum, oder?

Ja.

>Der Empfänger weiß ja welches Polynom benutzt wurde. Er empfängt die
>Daten, und berechnet auch die Checksum und vergleicht die Danach mit der
>übertragenen Checksumme oder?

Ja.

>Wobei mir gerade einfällt das die Datenbytes sich bei der CRC Berechnung
>auch ändern und nicht gleich bleiben oder?

Die Datenbytes ändern sich logischerweise NICHT!

>formulieren kann und die andere Frage, wie arbeitet nun die Tabelle
>dabei?

CRC, der Link unten erklärt das recht gut, ist aber auf englisch.

>Da ich mit 8Bit nur 256 Zustände haben kann stehen dann in der Tabelle
>alle Werte von 0 bis 255 jeweils mit dem Polynom XOR't oder? Dann in

Reicht doch. Deine Datenbytes sind der Index, mit dem du auf die Tabelle 
zugreifst. Der Inhalt wird mit der CRC XORed. Dann kommt das nächste 
Datenbyte.

CRC initialisieren

Schleifenanfang
  CRC_xor= tabelle(Datenbyte(i))
  crc = CRC xor CRC_XOR
  i++
gehe zum Schleifenanfang

MFG
Falk

von Jens (Gast)


Lesenswert?

Danke!

@thomas das python dingen hab ich schonmal gefunden aber ich hab keine 
ahnung wie ich das ans laufen kriege :)

@Falk Also ich habe ein Byte, dass ist mein Index auf die Tabelle und 
der Inhalt dieses Feldes ist quasi mein Ausgangsbyte schon mit XOr 
Polynom verknüpft, soweit richtig?

das mach ich dann z.b. mit acht Bytes und habe 8 "Checksummen" diese 
verknüpf ich dann auch nochmal alle mit Xor und gut ist, und die tabelle 
erstelle ich so wie ichs oben beschrieben habe?

dann sollte das ja relativ einfach sein....bei dem empfangsmodul muss 
ich dann auch wieder so die crc summe berechnen und wenn die ungleich 0 
ist habe ich ein problem.
klingt ja einfach :D (wenn das alles so stimmt)

von Falk B. (falk)


Lesenswert?

@  Jens (Gast)

>@Falk Also ich habe ein Byte, dass ist mein Index auf die Tabelle und
>der Inhalt dieses Feldes ist quasi mein Ausgangsbyte schon mit XOr
>Polynom verknüpft, soweit richtig?

Ja.

>das mach ich dann z.b. mit acht Bytes und habe 8 "Checksummen" diese

Nein, du berechnest die fortlaufend.

>verknüpf ich dann auch nochmal alle mit Xor und gut ist, und die tabelle
>erstelle ich so wie ichs oben beschrieben habe?

Wo?

MFg
Falk

von Peter D. (peda)


Lesenswert?

Jens wrote:

> Da das ganze schnell sein soll wollte ich mit einer Tabelle arbeiten.

Mit wieviel Megabit sollen den die Daten kommen?

Geschätzte 100 Zyklen mit der bitweisen Berechnung, dauert 1 Byte bei 
20MHz 5µs.

Du kannst also bequem mit 2MBaud senden und hast trotzdem noch genug 
Zeit, im Hintergrund die CRC auszurechnen.


Peter

von Falk B. (falk)


Angehängte Dateien:

Lesenswert?

Ich hab mal vor einiger Zeit die verschiedenen CRC-Verfahren in ASM 
umgesetzt, hier der Vergleich. Es ist eine 8 Bit CRC. Die Rechenzeiten 
in C sollten in der gleichen Relation zueinander liegen und nur etwas 
länger dauern.

MfG
Falk

von Jens (Gast)


Lesenswert?

Ich hab nun ne Funktion geschrieben die mit der Tabelle die hier ist: 
http://www.maxim-ic.com/appnotes.cfm/appnote_number/27 arbeitet

anhand dieser Erklaerung wie die Tabelle arbeitet klappt das bei mir ja 
nun auch, was die ganze zeit dabei mein problem war und ist, ist nur 
leider dass ich nicht gesehen habe welches Polynom eignetlich verwendet 
wird. das ist ja ansich egal wenn man die tabelle hat habe ich ja nun 
gemerkt.

wäre aber schon interessant zu wissen welches das da wirklich ist.


ich wollte die daten per USART übertragen mit 1 Mbaud

es kommt ein Telegramm von 3-11 Bytes und 1-8 Bytes sind Daten. dann 
kommt noch ein Byte was die CRC Checksum ist. der sender muss die halt 
berechnen und der empfaenger berechnet sie auch, vergleicht und 
antwortet dann mit einem anderen telegramm oder einer fehlermeldung.


meien funktion arbeitet nun einfach so

UCHAR fctCRC(UCHAR *pucData, UCHAR ucDataLen){
  UCHAR ucI=0;
  UCHAR ucZwischenCRC = 0x00;

  for(ucI=0; ucI<ucDataLen; ucI++)
  {
    ucZwischenCRC = g_aucCRCArray[pucData[ucI] ^ ucZwischenCRC];
  }
  return ucZwischenCRC;
}


Die Tabelle ist halt von der Seite die ich oben auch angegeben wurde.

Ich hoffe das ist so richtig, oder irre ich mich???

Wenn es einer so ausm steh greif weiß, wäre es auch nett wenn er mir 
kurz sagt wie die Tabelle nun erstellt wird. Habe mir die links oben 
zwar durchgelesen aber die machen da immer sehr komische sachen...sieht 
immer so unsauber aus.

von Jens (Gast)


Lesenswert?

ahja eine frage noch:

Mit dem Wert 0x00 bei den Polynomen anzufangen ist doch unsicher, habe 
ich mal gehört

wenn ich nun weiß wie ich Tabellen erstellen kann, kann ich doch ein 
anderes Start Polynom nehmen und muss nur die Tabelle ändern und alles 
läuft ohne Probleme???

von Falk B. (falk)


Lesenswert?

@ Jens (Gast)

>Mit dem Wert 0x00 bei den Polynomen anzufangen ist doch unsicher, habe
>ich mal gehört

Ja. besser ist FF, weill dann auch bei 0x00 Am Anfang der Daten eine CRC 
Berechnung gestartet wird.

>wenn ich nun weiß wie ich Tabellen erstellen kann, kann ich doch ein
>anderes Start Polynom nehmen und muss nur die Tabelle ändern und alles
>läuft ohne Probleme???

Das Polynom bleibt gleich, aber der Initialisierungswert der CRC ändert 
sich. Damit kann/muss man die Tabelle neu berechnen.

MFg
Falk

von Jens (Gast)


Lesenswert?

danke für die antwort!


UCHAR CheckCRC(UCHAR *pucData, UCHAR ucDataLen, UCHAR ucCRC)
{
  UCHAR ucI=0;
  UCHAR ucZwischenCRC = 0x00;

  for(ucI=0; ucI<ucDataLen; ucI++)
  {
    ucZwischenCRC = g_aucCRCArray[pucData[ucI] ^ ucZwischenCRC];
  }
  if(ucZwischenCRC ^ ucCRC)) return 1; // Error => Bitfehler
  return 0; // OK
}

so sieht meine CRC Check funktion aus beim Empfänger...ist das so 
richtig??? ich könnte eignetlich auch Prüfen ob ucZwischenCRC == ucCRC 
ist anstatt die XOR verknüpfung oder? Aber ansich ist so doch die Logik 
von dem Verfahren, der eine sendet es und haengt das crc byte an, der 
empfaengt die daten, rechnet auch wieder nen crc byte aus und das muss 
mit dem übertragenen übereinstimmen...dann sollten die funktionen ja so 
arbeiten können.


@falk du meintest nun das ich die tabelle neu berechnen muss/kann ?

einmal aendert sich in meinem fall also meinem code die initialisierung 
der variable ucZwischenCRC, richtig? die würde ich dann z.B. mit 0xFF 
initialisieren und hab somit mein neuen Startwert.

Wann muss ich denn nun die Tabelle neu berechnen und in welchem Fall 
nicht???

uind wenn ich das muss/kann , wie geht das überhaupt ;) Das war ja mein 
anderes Problem.

Ich rechne dann meinemStartWert XOR Polynom für Index 0 der Tabelle und 
was ist dann Index 1 ? das ist dann Polxnom XOR Index0 ??? und immer so 
weiter??? wird so die Tabelle berechnet? dann wäre das ja total 
einfach...auf den seiten machen die immer sehr komischen und 
unübersichtlichen Code.

oder ich irre mich nun einfach mal wieder und weiß garnicht wie die 
Tabelle erstellt wird

von Falk B. (falk)


Lesenswert?

@ Jens (Gast)

1
UCHAR CheckCRC(UCHAR *pucData, UCHAR ucDataLen, UCHAR ucCRC)
2
{
3
  UCHAR ucI=0;
4
  UCHAR ucZwischenCRC = 0x00;
5
6
  for(ucI=0; ucI<ucDataLen; ucI++)
7
  {
8
    ucZwischenCRC ^= g_aucCRCArray[pucData[ucI]];
9
  }
10
  if(ucZwischenCRC != ucCRC)) return 1; // Error => Bitfehler
11
  return 0; // OK
12
}

>so sieht meine CRC Check funktion aus beim Empfänger...ist das so
>richtig???

Nein, Korrektur siehe oben.

> ich könnte eignetlich auch Prüfen ob ucZwischenCRC == ucCRC
>ist anstatt die XOR verknüpfung oder?

Das ist sogar besser, weil verständlicher.

> Aber ansich ist so doch die Logik
>von dem Verfahren, der eine sendet es und haengt das crc byte an, der
>empfaengt die daten, rechnet auch wieder nen crc byte aus und das muss
>mit dem übertragenen übereinstimmen...dann sollten die funktionen ja so
>arbeiten können.

Ja.

>@falk du meintest nun das ich die tabelle neu berechnen muss/kann ?

Uuups, Kommando zurück. Die CRC Initialisierung ändert natürlich nichts 
an der Tabelle.

>Wann muss ich denn nun die Tabelle neu berechnen und in welchem Fall
>nicht???

Nur wenn du ein anderes Polynom verwendest.

>Ich rechne dann meinemStartWert XOR Polynom für Index 0 der Tabelle und
>was ist dann Index 1 ? das ist dann Polxnom XOR Index0 ??? und immer so

Nein. Hab ich jatzt nicht im Kopf. Musst du in den angegebenen Links 
nachlesen.

>oder ich irre mich nun einfach mal wieder und weiß garnicht wie die
>Tabelle erstellt wird

Kann sein ;-)

MfG
Falk

von Jens (Gast)


Lesenswert?

hmm nun bin ich etwas verwirrt.....

du hast ja mein code so angepasst
das:
ucZwischenCRC ^= g_aucCRCArray[pucData[ucI]]; ist.

Damit kriege ich aber andere ergebnisse als die auf der Seite: 
http://www.maxim-ic.com/appnotes.cfm/appnote_number/27

und zwar in Table1. bei Example 3. DOW CRC Lookup Function


Table 1. Table Lookup Method for Computing DOW CRC
Current CRC Value (= Current Table Index)   Input Data   New Index (= 
Current CRC xor Input Data)   Table (New Index) (= New CRC Value)


Bei deiner Zeile greift man ja nur noch auf das Feld zu was zum 
Datenbyte passt ohne die vorherige CRC Checksumme mit 
einzubeziehen....ist das dann nicht Falsch? Ich kriege zumindest andere 
ergebnisse raus als vorher :D ist ja auch logisch. Vorher hatte ich halt 
die Werte wie in dem Beispiel und nun nicht mehr...

von Falk B. (falk)


Lesenswert?

@ Jens (Gast)

>Bei deiner Zeile greift man ja nur noch auf das Feld zu was zum
>Datenbyte passt ohne die vorherige CRC Checksumme mit
>einzubeziehen....ist das dann nicht Falsch? Ich kriege zumindest andere

Ohh, ist wohl heute nicht mein Tag :-(
Du hast Recht, der Code war schon OK.

MFG
Falk

von Jens (Gast)


Lesenswert?

War ja nicht weiter schlimm :)

Ach ist das Klasse wenn ein Programm nun endlich klappt :D auch wenn es 
nur ein sehr kleines heute war.

Vielen Dank für deine umfangreiche Hilfe @Falk

Habe mir nun auch nen define gemacht der für den Startwert des 
ucZwischenCRC Wertes ist

also #define CRCSTARTVALUE

und dann im code nur noch als deifnition UCHAR ucZwischenCRC = 
CRCSTARTVALUE

somit kann ich auch schön an einer stelle den Startwert ändern und habe 
nicht mehr das 0x00 Problem. SOmit sollte es ja schon relativ sicher 
sein (hoffe ich)

von S. L. (wostl)


Lesenswert?

Hallo,

das Thema ist zwar schon etwas älter, meine Frage passt aber ganz gut 
dazu:
Ich will einen CRC-Check in meinem Projekt implementieren. Dazu habe ich 
mir eine ganze Reihe an Theorie und Code durchgelesen, allerdings fehlt 
noch ein entscheidender Schritt:

Maxim hat in seiner Application Note AN27 einen CRC-Code mit 
Look-Up-Table erklärt und auch ein Beispiel dazu. Mein C-Code generiert 
die gleiche Tabelle und auch die CRC Checksumme ist identisch. Soweit so 
gut.

Allerdings würde ich gerne noch wissen, wie man die Tabelle von Hand 
ausrechnen kann. Würde gerne zur Kontrolle ein paar Werte nachrechnen, 
allerdings verstehe ich noch nicht ganz, wie dies gemacht wird...

Hier mein Ansatz:
Das verwendete Polynom (soll angeblich) immer an der 128. Stelle stehen: 
In diesem Fall wäre das dann 140= 0x8C= 10001100. Zur Berechnung wird an 
das Polynom eine führende "1" geschrieben, sodass ich mit 110001100 
weiterrechne.
Berechne ich nun den Tabellenwert für die Zahl 3 = 00000011 sieht das 
folgendermaßen aus:

0000 0011
0000 0000 0
 000 0000 00
  00 0000 000
   0 0000 0000
     0000 00000
      000 000000
       11 0001100
        1 10001100
          |------| <------- XOR
          10010100 = 0x94 = 148

In der Tabelle von Maxim steht aber an der vierten Stelle 226...

Kann mir hier wer auf die Sprünge helfen?

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
Noch kein Account? Hier anmelden.