Datum:
Hier eine Funktion für die Berechnung einer CRC-16 Prüfsumme bei einer
seriellen Datenübetragung.
//- calcCRC16r ------------------------------------------------------
unsigned int calcCRC16r(unsigned int crc, unsigned int c, unsigned int
mask)
{
unsigned char i;
for(i=0;i<8;i++)
{
if((crc ^ c) & 1) { crc=(crc>>1)^mask; }
else crc>>=1;
c>>=1;
}
return (crc);
}
//-------------------------------------------------------------------
Aufruf der Funktion im Programm:
{
//...
unsigned int DEVICE_CRC16=0;
DEVICE_CRC16 = calcCRC16r (DEVICE_CRC16,chr,0xA001);
//...
}
mask = "0xA001" = Polynom x^16 + x^15 + x^2 + 1
Die Funktion wird bei jeder Übetragung eines Bytes "c" aufgerufen.
Der Rückgabewert entspricht der CRC-16 Prüfsumme (2 Byte) der
gesendeten Bytes. Ich verwende diese Funktion in einem MSP430.
J.St.
www.SynaSys.de
Datum:
Das geht mit nem andren Polygon aber schneller:
crc=0; //am Anfang initialisieren
unsigned int calcCRC16r(unsigned int crc, unsigned int c)
{ // CCITT 16 bit (X^16 + X^12 + X^5 + 1).
crc = (unsigned char)(crc >> 8) | (crc << 8);
crc ^= c;
crc ^= (unsigned char)(crc & 0xff) >> 4;
crc ^= (crc << 8) << 4;
crc ^= ((crc & 0xff) << 4) << 1;
return (crc);
}
Keine Loop und fast nur byte oder nibble swaps. Über die Qualität
des Polygons kann ich aber nichts sagen.
Marcus
Datum:
Hi Markus, du bist "putzig" und schreibst: "Das geht mit nem andren Polygon aber schneller:" Du meintest natürlich Polynom ;) Ich bin mir auch nicht so sicher ob dein Algo. überhaupt eine Cyclic Redundance Check ist. Zb. hier crc ^= (crc << 8) << 4; crc ^= ((crc & 0xff) << 4) << 1; aus der ersten Zeile würde man crc ^= crc << 12; machen, und auch in der zweiten Zeile gäbe es so eine Optimeirung mit crc ^= (crc & 0xff) << 5; Denoch, es wäre nett wenn du mir sagen könntest wo du diesen Code her hast, er sieht mir überhaupt nicht nach einer CRC aus. Entweder Bitweise wie es J.St. zeigte oder aber du benutzt eine Lookup Tabelle mit min. 256 Einträgen. In deinem Vorschlag sehe ich nichts dergleichen. Gruß Hagen
Datum:
Ich nehme auch die obige CRC (mit 0xA001). Sie hat nämlich den Vorteil, daß die CRC mit sich selber immer 0 ist. D.h. beim Erzeugen der CRC schreibt man einfach die CRC in die letzen beiden Bytes. Und beim Prüfem macht man die CRC über den kompletten Datensatz und prüft dann auf 0. Es gibt dafür in einer Maxim-Application-Note eine sehr schnelle Implementation (schneller als Tabelle), aber die läuft nur auf dem 8051, da sie das Parity-Flag benötigt. Nachfolgend die Funktion in C und in Assembler, wie ich sie in meinem Codebeispiel Bootloader verwende. C: unsigned int crc; void get_crc( unsigned char d ) { int i; crc ^= d; for( i = 8; i; i-- ){ crc = (crc >> 1) ^ ((crc & 1) ? 0xA001 : 0 ); } } Assembler: ;---------------------------------------------------------------------- ; Receive Interrupt ;---------------------------------------------------------------------- URXCint: ldi xh, high(rx_buff) in ia0, UDR st x+, ia0 ; calculate CRC in savesreg, sreg eor crc_lo, ia0 ldi ia0, 8 _crc1: lsr crc_hi ror crc_lo brcc _crc2 eor crc_lo, poly_lo eor crc_hi, poly_hi _crc2: dec ia0 brne _crc1 out sreg, savesreg ; reti ;---------------------------------------------------------------------- Peter
Datum:
Unter betimmten Umständen ist es besser mit einem CRC Startwert <> 0 anzufangen. So wie es Peter schon sagte bekommt man bei einer CRC Berechnung mit einem Startwert von 0 am Ende der Beerchnung wieder 0 raus. Allerings hat diese Weise der Berechnung mit obigen Polynom einen gravierenden Nachteil. Bitfehler die mit Daten entstehen die viele führende Nullen enthalten und der Bitfehler in einer Null resultiert werden nicht erkannt. Deshalb nimmt man meistens einen Startwert von 0xFFFF statt 0. Diese Fehler enstehen oft auf Grund von schlechten Hardwaresynchronisationen eines Bitstromes. Gruß Hagen
Datum:
Ich hätte für den Generator (x^16 + x^15 + x^2 + 1) noch folgende Lösung
anzubieten. Dies ist eine Mischung aus einer Tabelle und
Schiebebefehlen, aber ohne Schleife. Die Lösung ist aber nicht auf
meinem Mist gewachsen. Ich habe den Code mal in einem alten Programm
gefunden. Allerdings habe ich keine Ahnung wer der Autor ist.
static ushort CRC16;
static ushort oddparity[16] = {0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0};
ushort docrc16(ushort data)
{
data = (data ^ (CRC16 & 0xff)) & 0xff;
CRC16 >>= 8;
if (oddparity[data & 0xf] ^ oddparity[data >> 4])
CRC16 ^= 0xc001;
data <<= 6;
CRC16 ^= data;
data <<= 1;
CRC16 ^= data;
return CRC16;
}
Datum:
Hallo Ihr CRC Leutchen! Mal ne Frage: Angenommen ich kann nicht alle CRC Ergebnisse die ich generiert habe darstellen, sondern statt z.B. bei eniem CRC8 statt 8 Bit nur 7 (ASCII), kann ich dann mehrere gültige Polynome generieren lassen, und mir das beste aussuchen oder gibt es zu jedem Eingangscodewort nur genau 1 CRC Ergebnis ?
Datum:
Hallo CRC-Interessierte, ich bin auf der Suche nach dem Source zum Bilden des 16 Bit-CRC (CRC16) mit unterschiedlichen Polynomen. Die Polynome sollten vorgebbar sein (z.B. X16+X15+X2+1, X16+X12+X5+1 ....). Der Einsatz einer Tabelle oder Teil-Tabelle ist dafür wohl nicht so geeignet. Es sei denn sie wird auch generiert. Hat jemand ein solches Programm parat oder weis wo ein solches zu finden ist. Ich benötige dies in einer Microcontroller-Anwendung mit dem 8051 und zur Überprüfung mit dem PC. Danke für eure Hilfe Klaus
Datum:
@Hagen Der Code von Marcus Müller ist die Berechnung von HDLC/X.25 ^16+^12+^5+1 und ist vollkommen in Ordnung. Deine Optimierungen können manche Compiler nicht verkraften :-( Für CRC-16 bei HDLC/X.25 ist aber ein Init mit 0xFFFF notwendig und bei Verwendung mit Ethernet zum Schluss ein XOR mit 0xFFFF! Der Code ist übrigens von Eagle Air Australia Pty.LTD. Gruß S.Müller
Datum:
In der RFID-Norm ISO 15693 ist im Anhang ein Codebeispiel für eine crc16-berechnung. In dem Sourcecode könnte man bestimmt das vorgegebe Polynom austauschen. Dice
Datum:
@Siegfried, mag sein, daß der Code in Ordnung ist. Scheinbar sieht er sehr schnell aus, da keine Loop. Dafür enthält er aber zu viele Schiebeorgien "<<". Möchte nicht wissen, wie das Compilat dazu aussieht.
Datum:
@Dice Hallo Dice, konnte das Code-Beispiel noch nicht finden. Hast du vielleicht zufällig das Beispiel parat und könntest mir dies zukommen lassen? Danke für die Mühe und schöne Grüße Klaus
Datum:
Guck mal auf www.wg8.de, unter Projekts suche ISO 15693 - 3 Transmission Protocol. Dort im Anhang ist das Codebeispiel. Dice
Datum:
mal dumm gefragt: wie kommt man von der Maske 0xA001 auf das Generatorpolynom x^16 + x^15 + x^2 + 1 ??? 0xA001 binär is 1010 0000 0000 0001, das kanns ja wohl nicht sein. Also wo ist der Zusammenhang..? mfg.mat
Datum:
Hallo mat,
bei der Anwendungen des CRC16 in den USA, wird dort häufig als
zusätzliche Sicherheit, ein bitgedrehter Bitstring verwendet.
Da der CRC16 nur 16 Bit lang ist bleibt X^16 unberücksichtigt.
So wird aus:
X^16+X^15+X^2+1
zuerst
1000 0000 0000 0101 (X^16 entfallen)
dann
1010 0000 0000 0001 (Bitgedreht Bit 0 wird Bit 15,
Bit 1 wird Bit 14 usw.)
So das ist das ganze Geheimniss.
Freundliche Grüsse
Klaus
Datum:
ahaa.. und was bedeutet x^16 entfaellt..? Das es in der Maske entfaellt und fest im Algorithmus ist (auch wenn er kurz ist, ich hab noch keine der Implementierungen wirklich durchschaut, vielleicht grade weil sie so optimiert sind :-)) ) Oder bedeutet entfallen, dass die x^16 weder in der Maske noch im Algorithmus ansich zu finden sind..? mfg.mat
Datum:
Hallo mat, richtig. X^16 wird überhaupt nicht berücksichtigt. 16 Bit bedeutet ja Bit 0 bis 15. Bit 16 bei einem CRC16 gibt es nicht. Freundliche Grüsse Klaus
Datum:
hallo, Ich hab Peters code ausprobiertund komme nicht auf die Ergebnisse in der ISO 15693-3. In der ISO15693-3 wird das Polynom x^16 +x^12 +x^5 +1 mit "8408" angegeben! Normalerweise ist dies doch "A001"oder hab ich da etwas misverstanden?? Wie kommen die auf diesen Wert? Gruß
Datum:
Beim avr-gcc ist eine optimierte CRC16-Routine bereits enthalten #include <avr/crc16.h>
Datum:
Hm, ja, das mag ja sein, ich programmiere aber in CodeVison und möchte zudem den Sinn noch verstehen. Gruß
Datum:
Ich sach ma, da in der crc16.h für 0xA001 und für 0x8408 zwei völlig verschiedene Routinen stehen, kann die CRC garnicht übereinstimmen. Peter
Datum:
Hallo, X^16+X^15+X^2+1 ergibt 0xA001, X^16+X^12+X^5+1 ergibt 0x8408 jeweils Bitgedreht. Somit 2 verschiedene Polynome und natürlich unterschiedliche Ergebnisse. Gruß Klaus
Datum:
ich hab mit dem gute erfahrungen gemacht
/* CRC16 implementation acording to CCITT standards */
unsigned short crc_tab[16] =
{
0x0000, 0x1081, 0x2102, 0x3183,
0x4204, 0x5285, 0x6306, 0x7387,
0x8408, 0x9489, 0xA50A, 0xB58B,
0xC60C, 0xD68D, 0xE70E, 0xF78F
};
unsigned short crc_update (unsigned short crc, unsigned char c)
{
crc = (((crc >> 4) & 0x0FFF) ^ crc_tab[((crc ^ c) & 0x000F)]);
crc = (((crc >> 4) & 0x0FFF) ^ crc_tab[((crc ^ (c>>4)) &
0x000F)]);
return crc;
}
Datum:
habt ihr auch schon mal an eine modifizierte adler-16-prüfsumme gedacht?
Datum:
So gehts auch:
int crc16_table[256] = {
0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78};
int crcval;
char rx_c;
crcval = (crcval >> 8) ^ crc16_table[rx_c ^ (crcval & 0xff)];
Datum:
Hallo Peter, welches Generatorpolynom liegt denn deinem Algorithmus zu Grunde?
Datum:
Hallo Paul, x^16 + x^12 + x^5 + 1 mit Anfangswert 0. Ich setze diese Berechnung problemlos in zwei verschiedenen Anwendungen ein. Peter
Datum:
Hier ist nochmal das gleiche zur Berechnung des CRC, geht natürlich langsamer als der Lookup Table. Ich habe allerdings nie die Ausführungszeit gemessen, das ist kein Problem bei meinen Anwendungen. q_crc = (crcval ^ rx_c) & 017; crcval = (crcval >> 4) ^ (q_crc * 010201); q_crc = (crcval ^ (rx_c >> 4)) & 017; crcval = (crcval >> 4) ^ (q_crc * 010201); Peter
Datum:
Danke Peter ich werde deine Algorithmen mal ausprobieren. Aber ich hab noch eine Frage: Wendet man den CRC eigentlich auf jedes übertragene Byte einzeln an und hängt diesem die Prüfsumme an, oder berechnet man die Prüfsumme über mehrere übertragene Bytes ?
Datum:
normalerweise über mehrere übertragene bytes, aber ich frage mich wie groß ich die Packet-größe wählen sollte bei größeren Datenübertragungen?
Datum:
das hängt von deiner Anwendung ab. Normalerweise bildet man ein CRC für einen Datensatz oder Datenblock. CRC nur für ein Byte geht natürlich auch, aber damit verdreifachst du die Menge der übertragenden Bytes. Bei CRC für einen Block muss eben der ganze Block noch einmal übertragen werden, aber erfahrungsgemäss passiert das kaum. Peter
Datum:
Der Beitrag von Marcus Mueller scheint i.O. zu sein.
Bis anhin hatte ich mit einer vor-initialisierten Table den CRC16 Wert
berechnet:
#define POLYNOMIAL 0x1021
WORD crc_table[256];
void InitCRC_Table(void)
{
register WORD b, v;
register signed char i;
for( b = 0; b <= 255; ++b )
{
for( v = b << 8, i = 8; --i >= 0; )
{ if ( (v & 0x8000) != 0x0000 )
v = ( v << 1 ) ^POLYNOMIAL;
else
v = v << 1;
}
crc_table[b] = v;
}
}
Die Berechnung erfolgte dann mit:
WORD CRC_calculation(BYTE *msg, WORD cnt)
{
while( cnt-- != 0x0000)
crc_value = (crc_value << 8) ^ crc_table[(crc_value >> 8) ^
*msg++];
return( crc_value );
}
Da mit der Platz im RAM zu eng wurde, musste ich auf eine 'softige'
CRC-Methode ausweichen. Dabei stellte ich fest, dass die von Marcus
Mueller vorgeschlagene Methode dieselben Werte liefert.
Die Geschwindigkeit sind etwas langsamer:
30 Bytes: 750us / 580us
512 Bytes: 12,5ms / 9,6ms
MfG
Datum:
weiss es zufällig jemand wie diese CRC-16 Prüfsumme im Assembler gehen würde?!
Datum:
Schau in den crc-Header der avr-libc. Die Funktionen sind in inline-Assembler implementiert.
Datum:
Hallo zusammen, ich habe mir den Beitrag durchgelesen und habe da wohl noch ein Brett vor dem Kopf ! Also, wenn ich 10 Bytes + CRC16 senden möchte, wie muss dann der Aufruf der CRC-Funktion sein ? Werden die einzelnen CRC dann addiert ? Etwa so, CRC[BYTE01] + CRC[BYTE02] + ... + CRC[BYTE10] ? Ich hoffe Ihr könnt mir helfen. Gruss Slomo
Datum:
nee, die meisten gehen etwa so: neuer_crc_wert = crc (vorheriger_crc_wert, byte[n]);
Datum:
kann jemand mir die genaue Algorithmus für die CRC-Berechnung mit Hilfe Tabellenverfahren. auch die algorithmus für die Tabellen-Berechnung danke
Datum:
Ich muss mal diesen alten Thread wieder hervor holen Ich habe mich mal mit den hier geposteten Wegen zur CRC-Berechnung beschäftigt Ich komme aber mit den Ansätzen auf unterschiedliche Ergebnisse, obwohl die Bedingungen die selben zu sein scheinen Mit dem Code aus dem ersten Post von J.St. und mit der kurzen Variante von peter dannegger im 4. Post komme ich auf das gleiche Ergebnis Mit dem Lookuptable von Peter Beitrag "Re: CRC-16 Prüfsumme (serielle Übertragung)" allerdings nicht Obwohl er ja schreibt das Polynom sei das gleiche wie oben und der Startwert auch 0 Zudem habe ich noch diesen CRC Rechner gefunden http://www.flechtmann.net/crc/index.php Dieser rechnet scheinbar richtig, auf jeden Fall kann ich damit mehrere handgerechnete Ergebnisse bestätigen und auch einige aus dem netz Er liefert aber noch mal andere Werte als die 3 Funktionen aus diesem Thread Ich denke ich mache irgendwo einen Fehler, weiß aber nicht wo!
Datum:
Hier ist's mit den Startwerten, Polynimen hinreichend dargestellt: Beitrag "CRC von Hand (mit Startwert) berechnen" Hier ist etwas, was parametrisierbar C-Code aus vorgegebenem Polynom, Startwerten und Speicherbedarf (Schleife, 4-bit, 8-bit table) erzeugt. Must-have! http://www.tty1.net/pycrc
Datum:
Das ist lustig, unsere Kommunikation mit den von mir geposteten CRC Berechnungen läuft problemlos. Die Gegenseite sind Geräte diverser Hersteller, also nicht irgend was selbstgefummeltes. Sowohl der Lookup Table, als auch die Berechnung funktionieren. Startwert definitiv 0.
Datum:
Hi Leute, muss eine Prüfsumme über mehrere Bytes machen, habe auch einen Quellcode den ich einfach einbinden soll, weis aber nicht ob er wirklich was taugt. Was meint ihr?
uint16 Crc16_MC::computeCrc16( uint8* data, uint16 len)
{
uint16 help_value;
uint16 m_crc_value = 0xFFFFu;
uint16 m_crc_polynomial_16 = 0x1021u;
while (len-- > 0)
{
uint8 i; /* loop counter 1..8 */
m_crc_value ^= ((uint16)(*(data++)) << 8);
for (i = 0; i < 8; i++)
{
//0x8000 = binary 1000 0000 0000 0000
if ((m_crc_value & (uint16)0x8000u) > 0)
{
m_crc_value = (m_crc_value << 1) ^ m_crc_polynomial_16;
}
else
{
m_crc_value <<= 1;
}
}
}
help_value = m_crc_value;
m_crc_value = 0xFFFFu;
return help_value;
}
|
Ich verstehe ihn irgendwie überhaupt nicht.
Datum:
Wie macht man das eigentlich, wenn man über mehrere Bytes die CRC bilden möchte? Bisher kenne ich nur Lösungen, bei denen über 1 Byte eine CRC erstellt wird. (Lustig wird es eine 16bit CRC über ein Byte zu machen hehe)
Datum:
@ JDHawk (Gast) >Wie macht man das eigentlich, wenn man über mehrere Bytes die CRC bilden >möchte? Einfach die berechnete CRC wieder mit den neuen Daten anwenden. Siehe CRC, ganz unten die Links. >Bisher kenne ich nur Lösungen, bei denen über 1 Byte eine CRC erstellt >wird. Was reichlich sinnfrei ist. MFG Falk
Datum:
also sollte man doch lieber die "table-driven"-Variante nehmen, da schneller. ein fertiger korrekter Code wäre nicht schlecht, meinen versteh ich irgendwie nicht.
Datum:
JDHawk wrote: > also sollte man doch lieber die "table-driven"-Variante nehmen, da > schneller. Nö. Man sollte die Variante nehmen, die schnell genug ist. Z.B. in meinem Bootloader verwende ich ne Software-UART, die berechnet die 16Bit-CRC über jedes Datenbit, kostet also keinerlei zusätzliche Rechenzeit. Peter
Datum:
So, habe mal bisschen recherchiert: mein Algo sollte der CCITT-CRC16 sein, denn er rechnet für das char A die CRC 0xB915 genauso wie beim folgenden Rechner: http://zorc.breitbandkatze.de/crc.html Ein angeblich exakterer Algo ist hier, wo für char A der CRC 0x9479 rauskommt, soll auch ein CCITT-CRC16 sein. Was meint ihr welcher ist denn richtig, denn sie rechnen schon bisschen anders, oder ist es egal welchen man nimmt?
Datum:
Hier ist eine C# Version, mit der für komplette Byte-arrays eine 2 Byte
CRC-16 berechnet werden kann. Ohne Lookup-Table.
/// <summary>
/// CRC16S
///
/// The S stands for "Simple", because we use no lookup table here.
/// calculates the CRC16 Checksum of a given byte array
/// using the x^16+x^15+x^2+1 generator polynom (0xA001)
/// processing each byte without using a lookup table
/// </summary>
/// <param name="Data">a byte array of data</param>
/// <returns>2 byte CRC Checksum</returns>
public static byte[] CRC16S ( byte[] Data )
{
ushort Polynom = 0xA001;
ushort Register = 0xFFFF;
ushort temp = 0x00;
// loop through the entire array of bytes
for ( int i = 0; i < Data.Length; i++ )
{
temp = Data[i];
// shift all 8 data bits once
for ( int y = 0; y < 8; y++ )
{
if ( ( ( Register ^ temp ) & 0x01 ) == 0x01 )
{
Register >>= 1;
Register ^= Polynom;
}
else
{
Register >>= 1;
}
temp >>= 1; // shift data 1 bit right, dividing it by 2
} // end of inner for loop (bit shift loop)
} // end of outer for loop (data loop)
// now we have got our overall 2-byte CRC "Checksum" number
return new byte[2] { (byte) ( Register / 256 ), (byte) ( Register %
256 ) };
} // end of CRC16S Method
Datum:
Hallo zusammen,
auf der Visual Basic Seite habe ich untenstehenden Code gefunden.
Frage: Was heißt wohl "hier nacheinander die Werte (0-255)...einsetzen?
Es können doch unterschiedlich viele Datenbytes übertragen werden,
ergibt sich dabei immer eine Prüfsumme von 2 Bytes? Mir ist nicht ganz
klar wie ich das anfangen soll mit diesem Code.
Grüße
Olaf
Private Sub Button_Click(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles Button.Click
Dim CRC16 As UShort = 0
Dim Zahl As Byte
Zahl = X ' hier nacheinander die Werte (0-255), über die die
Prüfsumme gebildet werden soll einsetzten
CRC16 = CRCBerechnung(CRC16, Zahl)
Label.Text = Str$(Val(CRC16))
End Sub
Private Function CRCBerechnung(ByVal CRC As UShort, ByVal C As Byte) As
UShort
Dim I As Byte
Dim P As UShort = 40961 ' bitinvertierte Polynommaske 2^15 +
2^2+1
For I = 0 To 7
If ((CRC Xor C) And 1) > 0 Then
CRC = ((CRC / 2) Xor P)
Else
CRC = CRC / 2
End If
C = C / 2
Next
Return CRC
End Function
Datum:
@gruser Hallo Olaf, mach 'ne Schleife über alle Bytes Deiner Nutzdaten und rufe CRCBerechnung jedesmal mit dem aktuellen Byte an Stelle von Zahl auf. Falls Deine Nutzdaten überdurchschnittlich viele Nullen enthalten (typischer Fall), ist es besser, den Startwert von CRC16 von 0 auf 2^16-1 zu ändern. Schöne Grüße, Peter
Datum:
Hallo, ich hatte auch eine CRC16-Version gepostet, allerdings in Assembler. Beitrag "CRC16 Berechnung mit Tabelle" Gruß, Martin
Datum:
Moin moin. Ich scheine hier also ein Forum mit vielen Fachleuten entdeckt zu haben. Perfekt für einen unwissenden wie mich. Die Aufgabe die sich z.Zt. stellt ist folgende: Aus einem Datensatz mit insgesamt 62 Bytes und einer CRC-16 im 55. Byte soll aussschließlich das 39. Byte nach vorherigem Vergleich mit dem 23. und ausgegeben werden. Damit meine Anzeige aber keinen unsinn ausgibt und artig weiterfunktioniert und bei einem Fehler nicht aufgibt, wüsste ich gerne ob und wie ich die CRC-16 Prüfsumme in das Programm mit einbinden kann. Gruß Nico
Datum:
Hallo, ich habe den Code ganz oben von J.St. ausprobiert. Leider steht - egal welche Zahl ich in die Funktion setze - am Ende immer nur eine "1" in der Variablen DEVICE_CRC16 (bzw. DEVICE_CR16.high8 = 0 und DEVICE_CRC16.low8 =1). Sieht wer vielleicht woran es eventuell liegen könnte? Gruß Olaf
Datum:
Ich habe den Code wie folgt eingebaut, eigentlich müsste es doch
funktionieren - nur leider klappt es nicht - Tipps erwünscht:
//- calcCRC16r ------------------------------------------------------
unsigned int calcCRC16r(unsigned int crc, unsigned int c, unsigned
int mask)
{
// mask = 0xA001; // = Polynom x^16 + x^15 + x^2 + 1
unsigned char i;
for(i=0;i<8;i++)
{
if((crc ^ c) & 1) { crc=(crc>>1)^mask; }
else crc>>=1;
c>>=1;
}
return (crc);
}
//-------------------------------------------------------------------
//******* Hauptprogramm
*************************************************
void main(void)
{
//.....//
char test;
unsigned int DEVICE_CRC16=0;
test = 0b.0111.1001;
DEVICE_CRC16 = calcCRC16r (DEVICE_CRC16,test,0xA001);
//.....//
}
Datum:
@ Klaus Conzelmann @ matmaxx Die Aussage zum CRC-16: "16 Bit bedeutet ja Bit 0 bis 15. Bit 16 bei einem CRC16 gibt es nicht." ist so nicht korrekt. CRC-16 bedeutet zunächst nur, dass das höchstwertige Polynomglied den Grad 16 besitzt, daher besitzt jedes CRC-16-Polynom ein Glied x^16 (wobei CRC-Polynome wiederum keine Polynome im engeren, mathematisch korrektem Sinne sind - dies hat sich im Fachjargon nur so eingebürgert - sondern eine andere Darstellung einer binären Datenfolge unter Verwendung der polynominalen Darstellung mit Koeffizienten 0 oder 1). Eine wichtige Randbedingung für alle Generatorpolynome: Sowohl das höchstwertige Polynomglied (x^k bei einem Polynom vom Grad k) als auch das niederwertigste Polynomglied (x^0) müssen immer =1 sein. Betrachtet man jetzt eine "klassische" Polynomdivision mit mod2 (Berechnung ohne Überträge, also Addition = Subtraktion = exklusives OR): Es kann nur durch etwas geteilt werden, dass größer oder gleich dem Teiler ist. In der mod2-Algebra muss also die Bedingung erfüllt sein, dass das höchstwertige Bit des Dividenten die gleiche oder eine höhere Wertigkeit besitzen muss wie das höchstwertige Bit des Divisors ist, um mit Rest teilbar zu sein. Anders formuliert: Die partielle mod2-Polynomdivision wird nur an den Stellen durchgeführt, an denen sich vom Divisor und Dividenten eine 1 gegenüberstehen.... wer das einmal von Hand durchrechnet wird erkennen, dass das x^k des Teilerpolynoms immer wegfällt (es sein denn, die gesamte Nachricht ist Null, was einen (häufig behandelten) Sonderfall darstellt). Aufgrund dieser Tatsache wird oft das Vorgehen der CRC-Berechnung vereinfacht beschrieben: - man nehme den Datenrahmen und hänge so viele Nullen an die niederwertige Seite des Datenrahmens, wie der Grad des Generatorpolynoms - teile dieses erweiterte Polynom durch das Generatorpolynom - ziehe den Rest von der erweiterten Bitkette ab (mit mod2) -> man erhält als Ergebnis die Ursprungsnachricht, welche um den CRC ergänzt wurde (CRC befindet sich an der Stelle, an der die niederwertigen 0-Bits angehangen wurden). Eine solche Polynomdivision funktioniert mit ALLEN Generatorpolynomen gleichermaßen (und ist in allen Universalberechnungen abgebildet). Das Weglassen des höchstwertigen Bits des Generators ist lediglich eine Eigenschaft der implementierten Algorithmen. Die meisten Implementierungen, die bitweise schieben, untersuchen lediglich das zu teilende Polynom (ein unendlicher Bitstream) und entscheiden anhand der gesetzten Bits, ob eine XOR-Operation durchgeführt werden muss oder nicht. Für diese XOR-Operation kann dann das höchstwertige Bit des Teilerpolynoms weggelassen werden, wenn das Entscheidungsbit im Datenstrom für die XOR-Berechnung ebenfalls unter den Tisch fällt, da die XOR-Operation nur dann durchgeführt wird, wenn das Bit im Datenstrom gesetzt ist. Vielen Lesern sind die Hintergründe von CRC-Algorithman (ob verallgemeienert oder spezialisiert weil optimiert) oftmals nicht klar, was wilden Spekulationen führt, also Vorsicht! Vieles was im Internet zum CRC dokumentiert ist, ist nicht frei von Fehlern. Gruß, subitus
Datum:
@ Peter (Freizeitbastler) Zitat: "Falls Deine Nutzdaten überdurchschnittlich viele Nullen enthalten (typischer Fall), ist es besser, den Startwert von CRC16 von 0 auf 2^16-1 zu ändern." Die Initialisierung des CRC-Registers mit einem Wert ungleich 0 (gew. mit (2^k)-1) soll verhindern, dass anfängliche "Nullen" im Datenstrom unerkannt bleiben. Hingegen sollte sich die Wahl des Generatorpolynoms nach der Art der Nutzdaten richten. Um es Klarzustellen: Die Startwertinitialisierung hat keinen positiven/ negativen Einfluss auf das CRC-Ergebnis, wenn in den Nutzdaten überwiegend Nullen vorkommen (warum auch?), nur das Teilerpolynom und weitere CRC-Parameter wie das (Spiegeln bzw. Nibbeln von Datenbytes, zusätzliche XOR-Masken usw.) entscheiden hier über die Qualität des Ergebnisses! Es gibt jede Menge standardisierte CRC-Generatorpolynome mit entsprechenden Parametern, die für einen bestimmten Einsatzzweck besser geeignet sind als andere. Hier hilft nur ein Blick in die Literatur und eine sinnvolle Beurteilung des eigenen Systems. Gruß, subitus
Datum:
Hallo, Therorie schön und gut ;) aber vielleicht hat trotzdem noch jemand eine Idee warum mein (geklautes) Programm 3 Beiträge über diesem hier nicht funktioniert. Gruß Olaf
Datum:
Hallo, sehe gerade dass es hier offenbar etwas besseres gibt, werde einmal den Code von Marcus Müller ausprobieren, die gleiche Struktur habe ich auch auf der Microship-Seite gefunden: http://www.microchipc.com/sourcecode/index.php#crc
Datum:
Tja - leider motzt mein C-Compiler bei diesem Code. Deshalb habe ich den
Code vom allerersten Beitrag probiert:
//- calcCRC16r ------------------------------------------------------
unsigned int calcCRC16r(unsigned int crc, unsigned int c, unsigned int
mask)
{
unsigned char i;
for(i=0;i<8;i++)
{
if((crc ^ c) & 1) { crc=(crc>>1)^mask; }
else crc>>=1;
c>>=1;
}
return (crc);
}
//-------------------------------------------------------------------
Aufruf der Funktion im Programm:
{
//...
unsigned int DEVICE_CRC16=0;
DEVICE_CRC16 = calcCRC16r (DEVICE_CRC16,chr,0xA001);
//...
}
Es lässt sich auch alles einwandfrei kompilieren - wenn ich die beiden
Bytes abfrage kommt jeweils immer eine "1" als Ergebnis raus.
Was mache ich falsch? Wenn ich aus 3 Bytes einen CRC-Wert ermitteln
möchte, muss ich die Funktion doch einfach nur 3x aufrufen:
DEVICE_CRC16 = calcCRC16r (DEVICE_CRC16,Wert1,0xA001);
DEVICE_CRC16 = calcCRC16r (DEVICE_CRC16,Wert2,0xA001);
DEVICE_CRC16 = calcCRC16r (DEVICE_CRC16,Wert3,0xA001);
Die beiden Bytes frage ich mit DEVICE_CRC16.low8 bzw. DEVICE_CRC16.high8
ab. Bei den Deklarationen von Wert1-3 habe ich bereits alles probiert
(uns16/ uns8, char) - am Ergebnis hat es nichts geändert.
Any ideas?
Datum:
Hallo Olaf, in jedem Falle enthält "if((crc ^ c) & 1)" keine Zuweisung, d.h., die Bedingung wird zwar geprüft, es fehlt aber crc = crc ^ c. Also versuch mal if((crc = crc ^ c) & 1) bin aber kein c-Spezi... Gruß Wolfgang
Datum:
Ich habe eine Frage zu CRC16 Tabellen von Peter ist der Code frei oder lizensiert? Wo kann man die Tabelen für CDR16 und CRC8 "legal" downloaden? Ich habe die Tabelle implementiert muss aber die Quelle angeben. Vielen Dank im Voraus.
Datum:
Rund um die CRC-Berechnung gibt es viele Gerüchte und fehlerhafte
Implementierungen - selbst die Codes von scheinbar zuverlässigen Quellen
beinhalten Fehler (z.B. Software-Consults). Eine wirklich zuverlässige
Informationsquelle ist die beschreibung vom CRC-Papst ('CRC-Bibel'):
http://www.cs.waikato.ac.nz/~312/crc.txt
Darin ist auch ein Quellcodebeispiel enthalten. Ich habe mir daraufhin
einen universellen CRC-Stack für CRC8/16/32 erstellt, der sowohl
statische und dynamische Sprungtabellen, als auch dynamische Polynome
berechnen kann.
@freak:
Bei Bedarf kann ich gerne eine CRC16-Tabelle erstellen.
mfGruß,
subitus
Datum:
Hallo zusammen, dieser Artikel ist sehr interessant und vielleicht kann mir einer aus der Runde hier weiterhelfen, es geht auch wieder mal um CRC. Ich arbeite an einen Vintage Disk-Simulator( DEC RL02 ) und muss die Daten Struktur auf einer SD-card nachbilden und quasi somit auch vorformatieren. Dabei gibt es eine Header-Struktur , bestehend aus 3 16-bit Wörten mit einen CRC im letzten Wort. Dazu 3 Beispiele: A) Header = 0111001000001000 immer 0 = 0000000000000000 CRC = 1111111111100000 B) Header = 0001100110000111 immer 0 = 0000000000000000 CRC = 1111111111111100 C) Header = 0000010010000000 immer 0 = 0000000000000000 CRC = 1000000000000000 Obige Daten habe ich mit einen logic Analyser ausgelesen und ich weiss nicht nach welchen Algorithmus hier das CRC gebildet wird. Wenn mir jemand helfen kann, wäre ich mehr als dankbar ! .... sonst muss ich alle 4096 Sectoren durch meine MFM decoder laufen lassen und das ist viel viel Arbeit, die ich mir sparen will. Besten Dank und viel Grüsse, Reinhard
Datum:
>B) >Header = 0001100110000111 >immer 0 = 0000000000000000 >CRC = 1111111111111100 Was bedeutet hier "immer 0"? Wieviel (16-Bit-(?))Stellen sind das? Werden die Bits MSB oder LSB first übertragen? Bist Du sicher, dass das verwendete Verfahren eine CRC ist? Mal ein Beispiel parat, wo die "1"-en nicht von links aufgefüllt aussehen?
Datum:
"immer 0" bedeutet 16 bit 0 . Die Übertragung erfolgt mit LSB first. Wegen dem Verfahren bin ich mir schon sicher. Im Controller befindet sich ein 9401 chip und der überprüft lt. Schaltplan den CRC. Der Header besteht aus 3 mal 16bit Worten. Wort 1: 0-5 = Sector , 6 = head, 7-8 = Cylnder Wort 2: 0-15 = immer 0 ( wurde wohl nie benützt ) Wort 3: CRC ( dann kommen die Daten von jeweils einen sector mit 128 16-bit wörtern, bzw. 256 Byte und am Schluss von den Daten kommt auch noch ein 16bit CRC )
Datum:
Diverse Versuche mit pycrc haben nicht das anvisierte Ergebnis
gebracht:
>Header = 0111001000001000 (0x7208)
LSB first = 0001 0000 0100 1110 (0x104e)
pycrc-0.7.6$ ./pycrc.py --model=ccitt --check-hexstring=104e0000
0x99cb
pycrc-0.7.6$ ./pycrc.py --model=crc-16 --check-hexstring=104e0000
0xd764
...
pycrc-0.7.6$ ./pycrc.py --model=ccitt --check-hexstring=72080000
0x827c
...
Laut "Scheibenkleister" v. Claus Brod (S.192) wird bei dem
im ATARI verbauten Floppy-Controller X^16+X^12+X^5+1 (--model=ccitt)
genommen. Da damals sich einer vom anderen hat "inspirieren"
lassen, liegt die Vermutung nahe, dass dieses Polynom heiss
sein koennte ;-)
So wie ich aus dem eben referenzierten Werk entnehme,
ist das SYNC Byte 0xa1 oder 0xc2 (S.191), welche
laut S.192 als Adressmarke wohl mit in die CRC-Berechnung
einfliessen soll!? Kannst Du anhand des (CRC-)Taktsignals
feststellen, wann genau das Schieberegisterkonstrukt loslaeuft?
S.195 besagt, dass das CRC Register mit 0xCDB4 (ungewoehnlich!)
oder mit 0xFFFF (wie im --model=ccitt) initialisiert wird.
-Tiramisu
Autor:
Abdul K.
(ehydra)
Datum:
Das mit dem Inspirieren ist doch immer noch so. Macht ja auch Sinn. Sagt mal, wie lautet denn der aktuelle Link dazu: http://www.cs.waikato.ac.nz/~312/crc.txt Der geht nicht mehr!
Datum:
Hallo, ich sag mal herzlichen Dank für die Bemühungen. Mal sehen wie ich da weiterkomme. Den aktuellen Link finde ich übrigens auch nicht.
Datum:
Guten Tag, Ich stehe momentan vor einem praktischen Problem mit einem CRC-16 algorithmus. Ich habe ein Endgerät welches über 128 Datenregister mit dem CRC-16 verfahren(G(x) =x^16 + x^15 + x^2 + 1) eine Prüfsumme bildet. Die oberen 8 Bit werden nicht genutzt, da der Generator sich Byteweise durcharbeitet. Dieses wird einmal beim Gerätestart getan und der Wert wird festgehalten. Ich möchte nun über eine Konfigurationssoftware diesen algorithmus nachbilden um einen Vergleichs CRC-Wert zu haben. Folgende Werte sind vorgegeben: Startwert: 0x004B; Polynom: 0x8005; Ist dieser algorithmus dafür geeignet? Beitrag "Re: CRC-16 Prüfsumme (serielle Übertragung)" Ich bin mir etwas unsicher, da ja die oberen 8 Bit beim prüfen nicht genutzt werden. manfred
Datum:
Manfred schrieb: > Ich bin mir etwas unsicher, da ja die oberen 8 Bit beim prüfen nicht > genutzt werden. Das scheint mir doch sehr fraglich zu sein. Warum sollte man einen CRC-16 nehmen, und dann 8 Bit verwerfen? Dann könnte man ja auch gleich einen CRC-8 nehmen. Manfred schrieb: > Die oberen > 8 Bit werden nicht genutzt, da der Generator sich Byteweise > durcharbeitet. Es besteht kein Zusammenhang zwischen der Größe des CRC und der Größe, in der der Generator die Daten entgegen nimmt.
Datum:
Stefan Ernst schrieb: > Manfred schrieb: >> Ich bin mir etwas unsicher, da ja die oberen 8 Bit beim prüfen nicht >> genutzt werden. > > Das scheint mir doch sehr fraglich zu sein. Warum sollte man einen > CRC-16 nehmen, und dann 8 Bit verwerfen? Dann könnte man ja auch gleich > einen CRC-8 nehmen. > > Manfred schrieb: >> Die oberen >> 8 Bit werden nicht genutzt, da der Generator sich Byteweise >> durcharbeitet. > > Es besteht kein Zusammenhang zwischen der Größe des CRC und der Größe, > in der der Generator die Daten entgegen nimmt. text 1:1 aus dem Datenblatt: " Note that upper 8bits are unused as the genrator steps byte-wise over the configuration data! " wenn ich den oben genannten algorithmus anwende und keines von den 128 Datenregistern ändere müsste man als CRC den initial value von 0x004B wiederbekommen? oder ist diese annahme falsch? Momentan komme ich auf 0xc63c. Kann es leider noch nicht praktisch testen, da die Schnittstelle zwischen Programm und Hardware noch nicht fertig gestellt ist.
Datum:
Manfred schrieb: > text 1:1 aus dem Datenblatt: " Note that upper 8bits are unused as the > genrator steps byte-wise over the configuration data! " Wenn sich das "upper 8bits are unused" tatsächlich auf die CRC beziehen soll, dann macht der Satz gar keinen Sinn. Poste doch mal einen Link zum Datenblatt. Manfred schrieb: > wenn ich den oben genannten algorithmus anwende und keines von den 128 > Datenregistern ändere müsste man als CRC den initial value von 0x004B > wiederbekommen? oder ist diese annahme falsch? Vielleicht ja, vielleicht nein. Vielleicht ist dieser ungewöhnliche Startwert tatsächlich so gewählt, dass er zusammen mit dem Default-Inhalt der Register wieder als CRC herauskommt. Nochmal: Datenblatt zeigen.
E-Mail-Benachrichtigung einschalten
Neu: Seitenaufteilung einschalten