www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Hilfe bei CRC!


Autor: MC (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Tag an alle,
ich habe leichte Verständnisschwierigkeiten bei der Generierung meines 
CRC-Wertes.
Wie ich meinen Rest der Polynomdivision auf dem Papier bilde, versteh 
ich.
Mein Problem ist, dass ich die Umsetzung im µC (ich programmiere ein 
8051-Derivat) nicht hinbekomme.
Ich dachte mir, dass ich erstmal einen CRC8 versuche. Dazu habe ich im 
Anhang einen Beispielcode aus dem Internet.
Ich verstehe die Generierung des Rests im µC noch nicht. Vorallem, da 
mein Generatorpolynom ja 9Bit hat, mein µC aber nur 8Bit Werte 
verarbeiten kann.

Danke schon mal für eure Hilfe,
MC

Autor: Hans Hein (hanshein)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das 9-te Bit steckt im Carry Flag.
Nach dem Schieben:
Carry=0 fuehre keine Subtrakation (=Exor) durch. Ergebniscarry =0
Carry=1 exor mit (1)00011000
        (1) exor Carry(=1) => 0, also              Ergebniscarry =0

-Gast

Autor: MC (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke schon mal für deine Antwort, aber was du versuchst, mir zu 
vermitteln, versteh ich noch nicht ganz.

Autor: Hans Hein (hanshein)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> aber was du versuchst, mir zu vermitteln

Es ist sinnlos ein Bit zu speichern, welches immer 0 ist
und im Endergebnis nicht benoetigt wird; Es muss da auch 0 sein,
denn ansonsten koenntest du das Polynom nochmals
"subtrahieren" (exoren).

-Hans

Autor: Hans Hein (hanshein)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
; Meine 8051 X^8 + X^5 + X^4 + 1 Lieblingsroutine:
; (Assembler as31 unter Linux)
; crc8 definieren(!) (notfalls ein Register)
; .... und an Initialisierung des crc8 denken.

crc8tab:mov     dptr,#CRC8_TAB
        xrl     a,crc8
        movc    a,@a+dptr
        mov     crc8,a
        ret

CRC8_TAB:       db      0x00, 0x5e, 0xbc, 0xe2, 0x61, 0x3f, 0xdd, 0x83
                db      0xc2, 0x9c, 0x7e, 0x20, 0xa3, 0xfd, 0x1f, 0x41
                db      0x9d, 0xc3, 0x21, 0x7f, 0xfc, 0xa2, 0x40, 0x1e
                db      0x5f, 0x01, 0xe3, 0xbd, 0x3e, 0x60, 0x82, 0xdc
                db      0x23, 0x7d, 0x9f, 0xc1, 0x42, 0x1c, 0xfe, 0xa0
                db      0xe1, 0xbf, 0x5d, 0x03, 0x80, 0xde, 0x3c, 0x62
                db      0xbe, 0xe0, 0x02, 0x5c, 0xdf, 0x81, 0x63, 0x3d
                db      0x7c, 0x22, 0xc0, 0x9e, 0x1d, 0x43, 0xa1, 0xff
                db      0x46, 0x18, 0xfa, 0xa4, 0x27, 0x79, 0x9b, 0xc5
                db      0x84, 0xda, 0x38, 0x66, 0xe5, 0xbb, 0x59, 0x07
                db      0xdb, 0x85, 0x67, 0x39, 0xba, 0xe4, 0x06, 0x58
                db      0x19, 0x47, 0xa5, 0xfb, 0x78, 0x26, 0xc4, 0x9a
                db      0x65, 0x3b, 0xd9, 0x87, 0x04, 0x5a, 0xb8, 0xe6
                db      0xa7, 0xf9, 0x1b, 0x45, 0xc6, 0x98, 0x7a, 0x24
                db      0xf8, 0xa6, 0x44, 0x1a, 0x99, 0xc7, 0x25, 0x7b
                db      0x3a, 0x64, 0x86, 0xd8, 0x5b, 0x05, 0xe7, 0xb9
                db      0x8c, 0xd2, 0x30, 0x6e, 0xed, 0xb3, 0x51, 0x0f
                db      0x4e, 0x10, 0xf2, 0xac, 0x2f, 0x71, 0x93, 0xcd
                db      0x11, 0x4f, 0xad, 0xf3, 0x70, 0x2e, 0xcc, 0x92
                db      0xd3, 0x8d, 0x6f, 0x31, 0xb2, 0xec, 0x0e, 0x50
                db      0xaf, 0xf1, 0x13, 0x4d, 0xce, 0x90, 0x72, 0x2c
                db      0x6d, 0x33, 0xd1, 0x8f, 0x0c, 0x52, 0xb0, 0xee
                db      0x32, 0x6c, 0x8e, 0xd0, 0x53, 0x0d, 0xef, 0xb1
                db      0xf0, 0xae, 0x4c, 0x12, 0x91, 0xcf, 0x2d, 0x73
                db      0xca, 0x94, 0x76, 0x28, 0xab, 0xf5, 0x17, 0x49
                db      0x08, 0x56, 0xb4, 0xea, 0x69, 0x37, 0xd5, 0x8b
                db      0x57, 0x09, 0xeb, 0xb5, 0x36, 0x68, 0x8a, 0xd4
                db      0x95, 0xcb, 0x29, 0x77, 0xf4, 0xaa, 0x48, 0x16
                db      0xe9, 0xb7, 0x55, 0x0b, 0x88, 0xd6, 0x34, 0x6a
                db      0x2b, 0x75, 0x97, 0xc9, 0x4a, 0x14, 0xf6, 0xa8
                db      0x74, 0x2a, 0xc8, 0x96, 0x15, 0x4b, 0xa9, 0xf7
                db      0xb6, 0xe8, 0x0a, 0x54, 0xd7, 0x89, 0x6b, 0x35

-Hans

Autor: MC (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>; Meine 8051 X^8 + X^5 + X^4 + 1 Lieblingsroutine:
so wie ich deine Lieblingsroutine verstehe, verxorst du immer den Inhalt 
des Akkus (da sind deine Daten drin, oder?) mit dem crc8 Register. Mit 
dem Ergebnis holst du aus einer Tabelle dann einen Wert, der in crc8 
dann reingeschrieben wird. Das soll dann bestimmt der Rest der Division 
sein, oder? Dann sollte bei der ersten Durchführung crc8=0 sein, oder?
Aber was machst du, wenn im Akku führende 0en sind? Der erste Durchlauf 
muss doch immer mit einer führenden 1 beginnen? Und bei der Division 
werden doch 9Bit mit eingeschlossen1!???

Bitte nehmt mir meine vielen dummen Fragen nicht übel, aber ich habe die 
genaue Funktionsweise noch nicht ganz geschnallt.

Autor: Hans Hein (hanshein)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>so wie ich deine Lieblingsroutine verstehe, verxorst du immer den Inhalt
>des Akkus (da sind deine Daten drin, oder?)
genau...

>mit dem crc8 Register. Mit
>dem Ergebnis holst du aus einer Tabelle dann einen Wert, der in crc8
>dann reingeschrieben wird. Das soll dann bestimmt der Rest der Division
>sein, oder?

genau.

> Dann sollte bei der ersten Durchführung crc8=0 sein, oder?
Kommt auf die Spec an, bei ISO-CRC8 ist das IMHO (steht in der Spec) so.
-> nachsehen.

Zum Startwert... und jetzt etwas "anschaulicher" formuliert:
Stell Dir vor, ich lasse Dich die ("normale") Division 17/7 ausfuehren.
Kein Problem. Right? Jetzt sage ich Dir, dass vorher schon eine
Uebertragung stattgefunden hat (bsp eine 8, aber das weisst
Du nicht(!!) ;-)  )....
und gebe Dir nur die Information, dass der bisherige Rest eine 1 ist.

Das ist der Startwert fuer Deine Division:
 1 17 / 7 = irgendwas  Rest 5  (Ueberraschung: 817/7=... Rest 5)

Bei den Startwerten <>0 (und mit Polynomen im GF(2) Koerper) wird
also vorher schon eine Datenuebertragung "_fingiert_", die einen
gewissen Rest (der der in der Spec definiert ist) hat. Nur den
(Start-)Rest muss man wissen.

Das hat Vorteile, naemlich wenn lange Folgen von 0en am
Uebetragungsbeginn sind (s.u.).

>Aber was machst du, wenn im Akku führende 0en sind? Der erste Durchlauf
>muss doch immer mit einer führenden 1 beginnen?
Nein. Aber waere sinnvoll :-)
Begruendung siehe oben.

>Und bei der Division
>werden doch 9Bit mit eingeschlossen1!???

Im Algorithmus ja. Das 9te Bit des Divisionsschrittes ist immer Null.

>Bitte nehmt mir meine vielen dummen Fragen nicht übel, aber ich
>habe die genaue Funktionsweise noch nicht ganz geschnallt.

Es gibt keine dummen Fragen, nur dumme Antworten ;-)

Fuer die Herleitung der Tabellenversion ist u.U.

http://www.geocities.com/SiliconValley/Pines/8659/crc.htm

sinnvoll.

Zum kommandozeilenbasierten Spielen & Generieren der CRC Tabellen
(Parameter: Startwerte, Schieberichtungen, Iterativ/Tabelle,
Standard-CRCs)

http://www.tty1.net/pycrc/

(viele der Java/Javascript/...-CRC Webseiten sind kaputt...)

-Hans

PS: Willst Du verraten, fuer welche Anwendung Du den
ISO-CRC-8 einsetzen willst, ggf. waere da eine Tabellenversion
Overkill...

Autor: MC (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vielen Dank für die Links. So langsam versteh ich, was der Algorythmus 
macht!!!

>PS: Willst Du verraten, fuer welche Anwendung Du den
>ISO-CRC-8 einsetzen willst, ggf. waere da eine Tabellenversion
>Overkill...
Ich möchte mein Haus etwas automatisieren. Dazu habe ich mir ein 
Multi-Master System ausgedacht. Läuft soweit auch alles super, mit 
ausnahme der Netzwerkkommunikation. Dafür möchte ich jetzt ein richtiges 
Protokoll aufsetzen (momentan schicke ich die Informationen einfach so 
über die Leitungen). Auch eine Kollisionsvermeidung ähnlich wie beim 
CAN-Bus wird mit eingebunden.
Mein µC hat 12k internen Flash und kann auf bis zu 64k erweitert werden. 
Davon nutze ich im moment etwas mehr als 1k. Ein Speicher-Overkill ist 
also ausgeschlossen.

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.