Forum: Mikrocontroller und Digitale Elektronik Mal wieder CRC (16)-CCITT (XModem).Berechnung von Hand?


von Kurt K. (Gast)


Lesenswert?

Guten Abend,
ich möchte gerne die CRC (16)-CCITT (XModem) von A90064 von Hand 
berechnen.
A90064 --> 1010 1001 0000 0110 0100
Generatorpolynom 0x8408 --> 1000 0100 0000 1000

Ich habs mal probiert, an meine Nutzdaten die Nullen (r=15) angehängt 
und mit dem Generatorpolynom ein polynomdivison durchgeführt. Allerdings 
komme ich nicht auf das gleiche Ergebnis wie wenn ich die Nutzdaten bei 
lammertbies.nl-Checksum Calculator (Input-Type Hex) eingebe. Was mach 
ich da nur falsch? Das Thema CRC wurde hier im Forum ja des öfteren 
durchgekaut, würde mich aber freuen, wenn mir jemand auf die Sprünge 
helfen könnte.
VG.
Kurt

von Kurt K. (Gast)


Lesenswert?

Keiner eine Idee? Ich finde im Netz kein Rechenbeispiel...

von Reinhard Kern (Gast)


Lesenswert?

Kurt K. schrieb:
> Keiner eine Idee? Ich finde im Netz kein Rechenbeispiel...

Hallo,

was hast du denn gegen die Online-Berechnung? Von Hand ist viel zu 
mühsam, selbst wenn du richtig rechnest.

Gruss Reinhard

von Hans (Gast)


Lesenswert?

>Guten Abend,

Moin Kurt... ich bin momentan nicht in der Naehe meiner
"CRC Unterlagen", daher nur 95%-Aussagen ;-) ...

>ich möchte gerne die CRC (16)-CCITT (XModem)

Nein. Polynom CCITT= (1)1000010000001000  <>
      Polynom XModem=(1)0001000000100001

> von A90064 von Hand berechnen.
> A90064 --> 1010 1001 0000 0110 0100

Nein, Verschreiber? 1010 1001 0000 0000 0110 0100

> Generatorpolynom 0x8408 --> 1000 0100 0000 1000
Nein, s.o.

>an meine Nutzdaten die Nullen (r=15)
Nein. Das ist der Startwert (s.u "crc = 0;")
ARGH! Das Anfuegegeruecht haelt sich hartnaeckig...

>lammertbies.nl-Checksum Calculator (Input-Type Hex) eingebe.
Mein Favourit ist pycrc. Das Teil generiert Dir anhand einer
"Commandline-Spec" den C-Code...

Bzw. man suche auf atmel.com nach "AVR350"
(Xmodem CRC Receive Utility for tinyAVR and megaAVR devices).

Zitat aus calcrc.c:

-x-x-x-x-x-x-x-x- snip -x-x-x-x-x-x-
...
int calcrc(unsigned char *ptr, int count)

{

    int crc;

    char i;



    crc = 0;

    while (--count >= 0)

    {

        crc = crc ^ (int) *ptr++ << 8;

        i = 8;

        do

        {

            if (crc & 0x8000)

                crc = crc << 1 ^ 0x1021;

            else

                crc = crc << 1;

        } while(--i);

    }

    return (crc);

}

...
-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-

> wenn mir jemand auf die Sprünge helfen könnte.

Die 24 Schleifendurchlaeufe schaffst Du manuell locker in einer
Viertelstunde bzw. man fuege an geeigneten Stellen ein stdio.h-include,
ein main() sowie ein paar printf's hinein.

Reicht das fuer den Sprung?

VG,
Hans

von Kurt K. (Gast)


Lesenswert?

Hi zusammen,

>Reicht das fuer den Sprung?

@Hans: Der war für den Anfang etwas zu hoch:-)

Shit, ich kapier´s einfach nicht...Echt deprimierend!

Was meinst du mit dem (1) in...

> Polynom XModem=(1)0001000000100001

Ich versteh das Prinzip nicht...Oje!

Gruß und nochmal Danke für die Antworten!

von Hans (Gast)


Lesenswert?

>Was meinst du mit dem (1) in...
>> Polynom XModem=(1)0001000000100001

Das ist die X^16, welche i.d.R. weggelassen wird. Wenn Du es haendisch
rechnet, muss die fuehrende Eins hingeschrieben werden.

Die naechsten "1" sind X^12, X^5 und X^0.

1 exor 1 = 0 .... right!??

Im der Routine erkennt man den Trick daran, dass das MSB Bit auf "1" 
getestet
wird, diese "1" exor der MSB-Polynom-(1) ist... = 0, also brauchen wir
diese nicht mehr hinschreiben (oder dafuer Speicherplatz verbrauchen).

Daher steht nur exor 0x1021 im Programm, weil wir wissen, dass Bit 16
auf 0 reduziert wird.

VG,
Hans

von Kurt K. (Gast)


Angehängte Dateien:

Lesenswert?

Hi Hans,
danke für die Antwort. ich glaube ich steig langsam etwas besser durch. 
Dann muss ich also die 15 Nullen bei der Berechnung per Hand weglassen?! 
OK...

Nutzdaten A90064 --> 1010 1001 0000 0000 0110 0100
Polynom 0x1021 --> 1 0001 0000 0010 0001

Berechnung dann ganz normal, also so...?

1010 1001 0000 0000 0110 0100
1000 1000 0001 0000 1
---------------------------------
 010 0001 0001 0000 1
.
.
.
.
.

Grafisch könnte man das ja mit Schieberegister darstellen. Also bei 
0x1021 dann so (siehe Anhang). Im Schiebe Register entstehen die CRC 
Bits, die dann am Ende des Byteblocks durch Umlegen des Schalters 
"ausgetaktet" bzw. nachgeschoben werden, oder?

Grüße

von Hans (Gast)


Lesenswert?

>Berechnung dann ganz normal, also so...?
genau.

>..., die dann am Ende des Byteblocks durch Umlegen des Schalters
> "ausgetaktet" bzw. nachgeschoben werden, oder?

Im Prinzip ja ;-) Aber da steht in einschlaegigen Buechern eine Menge
mehr dazu... (Teufel+Detail und so :-)

VG,
Hans

von Hans (Gast)


Angehängte Dateien:

Lesenswert?

pycrc.py --model=xmodem --check-string="1"
0x2672

VG,
Hans

von Hans (Gast)


Lesenswert?

Argh! Ich habe tgif(Linux) verwendet... Die Gatter sollen XORs sein,
aber tgif erlaubt mir nicht, so kleine Kreise mehr zu zeichnen...

VG,
Hans

von Hans (Gast)


Angehängte Dateien:

Lesenswert?

So ein Schmarrn! Wenn man im tgif "Snap to Grid" ausschaltet,
kann man bei Winz-Zeichnungen wesentlich freier gestalten.

Man moege mir bitte das vorher unrichtige 5kB PNG verzeihen!

VG,
Hans

von Hans (Gast)


Lesenswert?

Wenn man das Beispiel mit dem obenstehenden C-code durchspielt,
erhaelt man:

*ptr
0x31

count
1

crc  i
0x0000  8  Initialisierung crc
0x3100  8
0x6200  7
0xc400  6
0x9821  5
0x2063  4
0x40c6  3
0x818c  2
0x1339  1
0x2672  0

return(crc) -> 0x2672
HURRAY!

VG,
Hans

von Hans (Gast)


Lesenswert?

Ach ja, Ergebnis des urspruenglichen Problems:

> pycrc.py --model=xmodem --check-hexstring="A90064"
0xf2f

VG,
Hans

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.