mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Hilfe CCITT CRC 16 Verständnisproblem


Autor: Sebastian Sobierajski (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Zusammen,

ich hab ein CRC Code gefunden der auch wunderbar funktioniert.
Mein Problem ist das ich diesen nicht wirklich verstehe......

Die Polynom Division hab ich an mehreren kleinen Beispielen per Hand
mal nachgerechnet aber dieses Wissen bringt mich nicht weiter wenn ich
versuche diesen Code zu verstehen...

C Syntax ist nicht das Problem !!!
Was hat sich der Erfinder dabei gedacht....
Absolut keine Kommentar.

Kann mir jemand den Code erklären ????

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

Bewertung
0 lesenswert
nicht lesenswert
NB: der Renesas / Hitachi M32C hat eine CRC-unit in Hardware
http://www.mikrocontroller.net/forum/read-1-296191.html

siehe auch
http://www.mikrocontroller.net/forum/read-1-321069...

Da der folgene Text im Breitformat besser lesbar ist, auch nochmal im
Anhang.


Der Code ist genauso einfach wie trickreich.
Es gibt zahllose Beschreibungen, z.B. Dallas/Maxim AppNote27
http://pdfserv.maxim-ic.com/en/an/AN27.pdf
oder als hmtl:
http://www.maxim-ic.com/appnotes.cfm/appnote_number/27

Den von Dir genannten Code kann man weiter optimieren, und zwar
 - den Übertrag des Bits an den Anfang des Schieberegisters (Stage 1)
kann man mit dem XOR mit-erledigen
 - die Reihenfolge der einzenen Schritte kann günstiger gelegt werden.

Das Ergebnis dieser Überlegungen kannst Du hier lesen:
http://www.mikrocontroller.net/forum/read-1-296191.html

zuerst eine Wertetabelle für xor
x y  e
0 0  0
0 1  1
1 0  1
1 1  0
d.h. das Ergebnis ist 0, wenn die Bits x und y gleich sind  oder
x wird invertiert, wenn y=1   oder
y wird invertiert, wenn x=1

Machen wir doch mal das Beispiel der AppNote27 (Figure 4 links):

Variable  j  c                 d         b         b&1 c/=2  d/=2
c/=2^p
BitNummer    fedcba9876543210  76543210  76543210
          0  9   0   f   1     7   5     8   4     0   4878  3a
             1001000011110001  01110101  10000100

zuerst xor-en wir das Low-Bit (das entspricht in Figure 3 dem rechten
XOR-Gatter (x15 xor Input Data (gemeint ist

das Bit 0 davon))).
Das mache ich in 2 Schritten:
 b=c^d   xor des ganzen (low-)Bytes  (f1 xor 75 = 84)
   b&1   nur Bit0 ist von Interesse  (84 and 01 = 00)

Wenn das Ergebnis (entspricht X0 in Figure3) 0 ist, braucht man nur CRC
nach rechts schieben, da von links eine 0

reingeschoben wird und x2 und x15 nicht invertiert werden.

Wenn das Ergebnis 1 ist, schiebe ich CRC nach rechts und invertiere die
Bits f, d und 0 (vor dem Shift waren das

die Bits X0, X2 und X15), indem ich CRC mit 40961 (0xa001 = 1010 0000
0000 0001) xor-e.
das könnte man mit if(b&1)crc^=0xA001; bewerkstelligen,
jedoch ist         b&1?crc^=40961:0;   2 Buchstaben kürzer, was mit
persönlich gefällt
                                       (das :0 braucht man nur aus
syntaktischen Gründen).
                                       (außerdem geht if() nicht in der
runden for-Klammer s.u.)

also, geschoben werden muss immer:

c=c >> 1  gleichbedeuten mit c>>=1  gleichbedeutend mit c/=2
(zumindest wenn c unsigned ist)

Beim nächsten Durchgang ist Bit1 von Input Data von Interesse, also
schiebe ich es an die Stelle d0:
d=d >> 1  c>>=1  c/=2

statt  for(j=0;j<8;j++)  schreibe ich  for(j=8;j;j--)   wieder 2
Buchstaben gespart  (-; (das mittlere j ist eine

Kurzform für j!=0)

und statt
for(j=8;j;j--){b=c^d;c/=2;d/=2;if(b&1)crc^=0xA001;} schreibe ich kurz
for(j=8;j;j--,b=c^d,c/=2,d/=2,b&1?c^=40961:0); schade, dass das
überflüssige :0 syntaktisch sein muss


Das war's auch schon.

Variable  j  c                 d         b         b&1 c/=2  d/=2
c/=2^p
BitNummer    fedcba9876543210  76543210  76543210
          0  9   0   f   1     7   5     8   4     0   4878  3a
             1001000011110001  01110101  10000100

          1  4   8   7   8     3   a     4   2     0   243c  1d
             0100100001111000  00111010  01000010

          2  2   4   3   c     1   d     2   1     1   121e  0e
b21f
             0010010000111100  00011101  00100001

          3  b   2   1   f     0   e     1   3     1   590f  07
f90e
             1011001000011111  00001110  00010011

          4  f   9   0   e     0   7     0   9     1   7c87  03
dc86
             1111100100001110  00000111  00001001

          5  d   c   8   6     0   3     8   5     1   6e43  01
ce42
             1101110010000110  00000011  10000101

          6  c   e   4   2     0   1     4   3     1   6721  00
c720
             1100111001000010  00000001  01000011

          7  c   7   2   0     0   0     2   0     0   6390  00
             1100011100100000  00000000  00100000

          8  6   3   9   0    <-- Ergebnis
             0100001110010000

CRC8  CRC16  CRC32 unterscheiden sich nur in der Breite der Variablen
c und dem Wert (Polynom) von p.

Weitere Fragen / Kommentare ? Bitte hier posten.

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.