www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik IBM-CRC-16 Codierung der CRC


Autor: Andreas K. (all-finder)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Hallo!

Folgende Frage:

Wie wird die oben genannte CRC berechnet:

P(x) = x^16 + x^15 + x^2 + 1

Das heißt ich habe 6 Bytes einer Nachricht, für diese möchte ich die 
16bit CRC errechnen.

z.B.
Byte 0 = 1
Byte 1 = 9
Byte 2 = 254
...

Wie setze ich diese Werte ein? Addiere ich die jeweiligen Werte auf?

Danke, mfg

PS: ich möchte den logischen Rechenweg... nicht Tabellen zum Shiften / 
XOR'n ;)

Autor: oha (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der CRC ist eine Zustandsmaschine, mit dem CRC als gespeicheter Wert. 
Man beginnt mit Null. Dann rechnet man den CRC des ersten bytes und dann 
alle anderen bytes. Und der CRC Wert der Nachricht is der Wert der 
Maschine am Schluss. Wie man den CRC eines einzelnen Bytes ist klar ?

Autor: Andreas K. (all-finder)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das ging ja schnell ;).

"beginnt mit Null" hängt aber nicht mit dem Initwert zusammen, oder? 
Dieser wäre 0xFFFF in meinem Fall. Für die einzelnen Bytes würde ich den 
Wert jeweils einsetzen...

Dann hab ich z.B. P(1) = 4 und weiter?

Autor: oha (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gut man kann auch mit FFFF beginnen. ja. Und dann einfach jeweils des 
CRC ueber das byte rechnen, ohne der Initialwert neu zu setzten. Das ist 
alles.

Autor: Andreas K. (all-finder)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dann hab ich für jedes Byte eine CRC, was mach ich dann damit?
CRC(Byte0) = 4
CRC(Byte1) = 2058911320946572 ?
...

Autor: Stefan Ernst (sternst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Andreas K. schrieb:
> Dann hab ich für jedes Byte eine CRC, was mach ich dann damit?

Die CRC ist ein "mitlaufender Wert". Die für Byte 0 errechnete CRC ist 
der neue Startwert für die CRC-Berechnung mit Byte 1, und so weiter.

Das Schema ist wie folgt:
CRC = 0xffff
Schleife(für jedes Byte):
   CRC = Berechnung(CRC,Byte)

Autor: Andreas K. (all-finder)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
is leider noch nicht angekommen.. ich habe das Polynome, welches nur x 
hat. Oder muss ich den aktuellen Wert aus der CRC des vorherigen mit dem 
aktuellen Wert kombinieren (jeweils 8Bit) und dann einsetzen!?

Zusätzlich ignoriere ich den Überlauf(e)? (bilde nur eine Funktin ab)

Autor: Stefan Ernst (sternst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ach so, es hapert an der grundsätzlichen Berechnung.

http://de.wikipedia.org/wiki/Cyclic_Redundancy_Check

Autor: KelleRassel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kopier doch einfach die Routinen und gut ist. Schieben und XOR.

Autor: Stefan Ernst (sternst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zusatz (ich bin nicht begeistert von der neuen Editierregelung):

Dein grundsätzlicher Irrtum liegt darin, das Polynom als 
Berechnungsformel zu betrachten. Wenn dein erstes Byte den Wert 10 hat, 
dann wird nicht diese 10 dort als Wert für x eingesetzt und das Ergebnis 
ist dann der CRC. Es ist schon etwas komplizierter. ;-)

Autor: Andreas K. (all-finder)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
okay, zu leicht gedacht...

Anderer Ansatz: ich überprüfe die CRC einer Berechnung auf dem µC und 
versuche diese abzubilden. Hierzu bräuchte ich das Generatorpolynom. 
Aktuell hab ich nur eine generierte Tabelle gegeben.

Wie bringe ich: P(x) = x^16 + x^15 + x^2 + 1 in den Zusammenhang?

Autor: Thomas Pircher (tpircher) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Andreas K. schrieb:
> Wie bringe ich: P(x) = x^16 + x^15 + x^2 + 1 in den Zusammenhang?

2^16 + 2^15 + 2^2 + 1 = 0x18005

Davon laesst du das MSB weg und du erhaelst 0x8005.

Ist die erste Zeile der CRC Tabelle vielleicht
0x0000, 0xc0c1, 0xc181, 0x0140, 0xc301, 0x03c0, 0x0280, 0xc241, ...

Autor: Andreas K. (all-finder)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ja...

Autor: Thomas Pircher (tpircher) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der folgende Code ist von pycrc generiert und sollte dir deinen CRC 
berechnen. Vor ein paar Tagen hat peda hier einen code gepostet, der 
etwas schoener anzuschauen ist, aber letzten Endes aehnlichen 
Maschinencode generieren sollte.

Du rufst die CRC Routinen wie folgt auf:
crc_t crc;

crc = crc_init();
// fuer alle Characters (oder Strings) in deinem datagramm:
    crc = crc_update(crc, (unsigned char *)data, data_len);
crc = crc_finalize(crc);

/**
 * \file stdout
 * Functions and types for CRC checks.
 *
 * Generated on Thu Aug 27 13:40:28 2009,
 * by pycrc v0.7.1, http://www.tty1.net/pycrc/
 * using the configuration:
 *    Width        = 16
 *    Poly         = 0x8005
 *    XorIn        = 0x0000
 *    ReflectIn    = True
 *    XorOut       = 0x0000
 *    ReflectOut   = True
 *    Algorithm    = table-driven
 *    Direct       = True
 *****************************************************************************/
#include "stdout.h"
#include <stdint.h>
#include <stdlib.h>

/**
 * Static table used for the table_driven implementation.
 *****************************************************************************/
static const crc_t crc_table[256] = {
    0x0000, 0xc0c1, 0xc181, 0x0140, 0xc301, 0x03c0, 0x0280, 0xc241,
    0xc601, 0x06c0, 0x0780, 0xc741, 0x0500, 0xc5c1, 0xc481, 0x0440,
    0xcc01, 0x0cc0, 0x0d80, 0xcd41, 0x0f00, 0xcfc1, 0xce81, 0x0e40,
    0x0a00, 0xcac1, 0xcb81, 0x0b40, 0xc901, 0x09c0, 0x0880, 0xc841,
    0xd801, 0x18c0, 0x1980, 0xd941, 0x1b00, 0xdbc1, 0xda81, 0x1a40,
    0x1e00, 0xdec1, 0xdf81, 0x1f40, 0xdd01, 0x1dc0, 0x1c80, 0xdc41,
    0x1400, 0xd4c1, 0xd581, 0x1540, 0xd701, 0x17c0, 0x1680, 0xd641,
    0xd201, 0x12c0, 0x1380, 0xd341, 0x1100, 0xd1c1, 0xd081, 0x1040,
    0xf001, 0x30c0, 0x3180, 0xf141, 0x3300, 0xf3c1, 0xf281, 0x3240,
    0x3600, 0xf6c1, 0xf781, 0x3740, 0xf501, 0x35c0, 0x3480, 0xf441,
    0x3c00, 0xfcc1, 0xfd81, 0x3d40, 0xff01, 0x3fc0, 0x3e80, 0xfe41,
    0xfa01, 0x3ac0, 0x3b80, 0xfb41, 0x3900, 0xf9c1, 0xf881, 0x3840,
    0x2800, 0xe8c1, 0xe981, 0x2940, 0xeb01, 0x2bc0, 0x2a80, 0xea41,
    0xee01, 0x2ec0, 0x2f80, 0xef41, 0x2d00, 0xedc1, 0xec81, 0x2c40,
    0xe401, 0x24c0, 0x2580, 0xe541, 0x2700, 0xe7c1, 0xe681, 0x2640,
    0x2200, 0xe2c1, 0xe381, 0x2340, 0xe101, 0x21c0, 0x2080, 0xe041,
    0xa001, 0x60c0, 0x6180, 0xa141, 0x6300, 0xa3c1, 0xa281, 0x6240,
    0x6600, 0xa6c1, 0xa781, 0x6740, 0xa501, 0x65c0, 0x6480, 0xa441,
    0x6c00, 0xacc1, 0xad81, 0x6d40, 0xaf01, 0x6fc0, 0x6e80, 0xae41,
    0xaa01, 0x6ac0, 0x6b80, 0xab41, 0x6900, 0xa9c1, 0xa881, 0x6840,
    0x7800, 0xb8c1, 0xb981, 0x7940, 0xbb01, 0x7bc0, 0x7a80, 0xba41,
    0xbe01, 0x7ec0, 0x7f80, 0xbf41, 0x7d00, 0xbdc1, 0xbc81, 0x7c40,
    0xb401, 0x74c0, 0x7580, 0xb541, 0x7700, 0xb7c1, 0xb681, 0x7640,
    0x7200, 0xb2c1, 0xb381, 0x7340, 0xb101, 0x71c0, 0x7080, 0xb041,
    0x5000, 0x90c1, 0x9181, 0x5140, 0x9301, 0x53c0, 0x5280, 0x9241,
    0x9601, 0x56c0, 0x5780, 0x9741, 0x5500, 0x95c1, 0x9481, 0x5440,
    0x9c01, 0x5cc0, 0x5d80, 0x9d41, 0x5f00, 0x9fc1, 0x9e81, 0x5e40,
    0x5a00, 0x9ac1, 0x9b81, 0x5b40, 0x9901, 0x59c0, 0x5880, 0x9841,
    0x8801, 0x48c0, 0x4980, 0x8941, 0x4b00, 0x8bc1, 0x8a81, 0x4a40,
    0x4e00, 0x8ec1, 0x8f81, 0x4f40, 0x8d01, 0x4dc0, 0x4c80, 0x8c41,
    0x4400, 0x84c1, 0x8581, 0x4540, 0x8701, 0x47c0, 0x4680, 0x8641,
    0x8201, 0x42c0, 0x4380, 0x8341, 0x4100, 0x81c1, 0x8081, 0x4040
};

/**
 * Reflect all bits of a \a data word of \a data_len bytes.
 *
 * \param data         The data word to be reflected.
 * \param data_len     The width of \a data expressed in number of bits.
 * \return     The reflected data.
 *****************************************************************************/
long crc_reflect(long data, size_t data_len)
{
    unsigned int i;
    long ret;

    ret = data & 0x01;
    for (i = 1; i < data_len; i++)
    {
        data >>= 1;
        ret = (ret << 1) | (data & 0x01);
    }
    return ret;
}


/**
 * Update the crc value with new data.
 *
 * \param crc      The current crc value.
 * \param data     Pointer to a buffer of \a data_len bytes.
 * \param data_len Number of bytes in the \a data buffer.
 * \return         The updated crc value.
 *****************************************************************************/
crc_t crc_update(crc_t crc, const unsigned char *data, size_t data_len)
{
    unsigned int tbl_idx;

    while (data_len--) {
        tbl_idx = (crc ^ *data) & 0xff;
        crc = (crc_table[tbl_idx] ^ (crc >> 8)) & 0xffff;

        data++;
    }
    return crc & 0xffff;
}

Autor: Thomas Pircher (tpircher) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sorry, ich vergass: die dazugehoerige header Datei ist:
/**
 * \file stdout
 * Functions and types for CRC checks.
 *
 * Generated on Thu Aug 27 14:02:29 2009,
 * by pycrc v0.7.1, http://www.tty1.net/pycrc/
 * using the configuration:
 *    Width        = 16
 *    Poly         = 0x8005
 *    XorIn        = 0x0000
 *    ReflectIn    = True
 *    XorOut       = 0x0000
 *    ReflectOut   = True
 *    Algorithm    = table-driven
 *    Direct       = True
 *****************************************************************************/
#ifndef __STDOUT__
#define __STDOUT__

#include <stdint.h>
#include <stdlib.h>

#ifdef __cplusplus
extern "C" {
#endif

/**
 * The definition of the used algorithm.
 *****************************************************************************/
#define CRC_ALGO_TABLE_DRIVEN 1

/**
 * The type of the CRC values.
 *
 * This type must be big enough to contain at least 16 bits.
 *****************************************************************************/
typedef uint16_t crc_t;

/**
 * Reflect all bits of a \a data word of \a data_len bytes.
 *
 * \param data         The data word to be reflected.
 * \param data_len     The width of \a data expressed in number of bits.
 * \return     The reflected data.
 *****************************************************************************/
long crc_reflect(long data, size_t data_len);

/**
 * Calculate the initial crc value.
 *
 * \return     The initial crc value.
 *****************************************************************************/
static inline crc_t crc_init(void)
{
    return 0x0000;
}

/**
 * Update the crc value with new data.
 *
 * \param crc      The current crc value.
 * \param data     Pointer to a buffer of \a data_len bytes.
 * \param data_len Number of bytes in the \a data buffer.
 * \return         The updated crc value.
 *****************************************************************************/
crc_t crc_update(crc_t crc, const unsigned char *data, size_t data_len);

/**
 * Calculate the final crc value.
 *
 * \param crc  The current crc value.
 * \return     The final crc value.
 *****************************************************************************/
static inline crc_t crc_finalize(crc_t crc)
{
    return crc ^ 0x0000;
}


#ifdef __cplusplus
}           /* closing brace for extern "C" */
#endif

#endif      /* __STDOUT__ */

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.