Can anyone out there explain how to calculate the 15 bit CRC field for a Controller Area Network message (specifically the extended frame format)? I don't understand the code given in the Bosch specification (not even sure which language it's written in) and the only other example I found was very obfuscated C code. Any takers? -Will
Need an explanation for calculating the CRC for a CAN network
Started by ●April 15, 2008
Reply by ●April 15, 20082008-04-15
larkmore@aol.com wrote:> Can anyone out there explain how to calculate the 15 bit CRC field for > a Controller Area Network message (specifically the extended frame > format)? I don't understand the code given in the Bosch specification > (not even sure which language it's written in) and the only other > example I found was very obfuscated C code. Any takers? > -WillWhat is your problem with the formula given there for the coefficients of the generator-polynomial? X15 + X14 + X10 + X8 + X7 + X4 + X3 + 1. that is what I would call a mathematical description. The other code given there I know under the name of pseudo code. If that is something like the names of Bohemian villages for you, please search for "CRC calculation". Most literature you will find can explain it better than I can. Regards Heinz
Reply by ●April 15, 20082008-04-15
larkmore@aol.com wrote:> Can anyone out there explain how to calculate the 15 bit CRC field for > a Controller Area Network message (specifically the extended frame > format)?The CAN specification already explains it. And unless you're out to implement your own CAN controller (why?), there's hardly a point digging any deeper --- just use an off-the-shelf CAN controller, it knows how to do this.
Reply by ●April 15, 20082008-04-15
Heinz-J=FCrgen Oertel wrote:> What is your problem with the formula given there for the coefficients of > the generator-polynomial? > > X15 + X14 + X10 + X8 + X7 + X4 + X3 + 1. > > that is what I would call a mathematical description. The other code given=> there I know under the name of pseudo code. > If that is something like the names of Bohemian villages for you, please > search for "CRC calculation". Most literature you will find can explain it=> better than I can.I do not understand what "X" is in this case. Is it just a concatenation of all the bits in the SOF, Arbitration, Control and Data fields? If yes, then the resulting number would be much larger than 15 bits. Hence my confusion. The term "generator-polynomial" is also unfamiliar to me. I have searched extensively for CRC calculation and all the articles I have found to date say it is really nice thing to have, talk about the format in very vague and hand wavy terms that I guess they assume everyone already knows (like "generator- polynomial"!!!) and usually wind up saying that there are many different ways to derive one. Great. _WHICH_ method is the one used for CAN messages specifically?? As mentioned, only the Bosch specification and a really incomprehensible C code actually refer to CAN by name. I am very familiar with pseudo code in general but the specific flavor used in the Bosch document makes no sense to me. Hans-Bernhard Br=F6ker <HBBroe...@t-online.de> wrote:> The CAN specification already explains it. And unless you're out to > implement your own CAN controller (why?), there's hardly a point digging > any deeper --- just use an off-the-shelf CAN controller, it knows how to > do this.I am trying to write a simulator (in Java as it happens) that will show me what the picture on the oscilloscope should look like for an arbitrary CAN message. That way I can troubleshoot my hardware and firmware to figure out whether I am sending the message that I think I should be sending or if bugs are creeping in along the way. Everything is written and working except the CRC part. Right now I'm just setting all the bits to "1" but that winds up screwing with my bit stuffing.
Reply by ●April 15, 20082008-04-15
larkmore@aol.com wrote:> Heinz-J�rgen Oertel wrote: > >>What is your problem with the formula given there for the coefficients of >>the generator-polynomial? >> >> X15 + X14 + X10 + X8 + X7 + X4 + X3 + 1. >> >>that is what I would call a mathematical description. The other code given >>there I know under the name of pseudo code. >>If that is something like the names of Bohemian villages for you, please >>search for "CRC calculation". Most literature you will find can explain it >>better than I can. > > > I do not understand what "X" is in this case. Is it just a > concatenation of all the bits in the SOF, Arbitration, Control and > Data fields? If yes, then the resulting number would be much larger > than 15 bits. Hence my confusion. The term "generator-polynomial" is > also unfamiliar to me.A concise but readable description of the mathematics of CRC is in this article: http://en.wikipedia.org/wiki/Mathematics_of_CRC An implementation of CRC-CCITT calculation using shift registers and XOR gates (mistakenly labeled as CRC-16) is here: http://www.erg.abdn.ac.uk/users/gorry/course/dl-pages/crc.html These sites were just the top hits in a quick net search... You should be able to see how to implement the polynomial you cited in your original post from this information. Michael
Reply by ●April 15, 20082008-04-15
larkmore@aol.com wrote:>Heinz-J�rgen Oertel wrote: >> What is your problem with the formula given there for the coefficients of >> the generator-polynomial? >> >> X15 + X14 + X10 + X8 + X7 + X4 + X3 + 1. >> >> that is what I would call a mathematical description. The other code given >> there I know under the name of pseudo code. >> If that is something like the names of Bohemian villages for you, please >> search for "CRC calculation". Most literature you will find can explain it >> better than I can. > >I do not understand what "X" is in this case. Is it just a >concatenation of all the bits in the SOF, Arbitration, Control and >Data fields? If yes, then the resulting number would be much larger >than 15 bits. Hence my confusion. The term "generator-polynomial" is >also unfamiliar to me. I have searched extensively for CRC >calculation and all the articles I have found to date say it is really >nice thing to have, talk about the format in very vague and hand wavy >terms that I guess they assume everyone already knows (like "generator- >polynomial"!!!) and usually wind up saying that there are many >different ways to derive one. Great. _WHICH_ method is the one used >for CAN messages specifically?? As mentioned, only the Bosch >specification and a really incomprehensible C code actually refer to >CAN by name. >its a mathematical way of describing something that boils down to shiftregisters and xor gates in short X is the shift register, the numbers are bit positions. though I can't really get the numbers and the 0x4599 in the code to match up>I am very familiar with pseudo code in general but the specific flavor >used in the Bosch document makes no sense to me.looks a bit weird, helps if you know verilog or vhdl I guess. the pseudo in c would be something like this: (untestet, inefficient, written in 30 seconds ...) unsigned short CRC(unsigned short input) // input only one bit !!! { static unsigned short crc_rg; // shiftregister crc_rg = crc_rg << 1; // leftshift 1 bit if((input & 1) ^ ((crc_rg>>14)&1)) { crc_rg = crc_rg ^ 0x4599; } crc_rg = crc_rg & 0x7fff; // only 15 bits return crc_rg; } -Lasse
Reply by ●April 15, 20082008-04-15
Lasse Langwadt Christensen wrote:>> Heinz-J�rgen Oertel wrote:>>> X15 + X14 + X10 + X8 + X7 + X4 + X3 + 1.> though I can't really get the numbers and the 0x4599 in the code to match upWhy not? 0x4599 has bits number 0, 3, 4, 7, 8, 10 and 14 set. Ring a bell now?
Reply by ●April 15, 20082008-04-15
Hans-Bernhard_Br�ker <HBBroeker@t-online.de> wrote:>Lasse Langwadt Christensen wrote: > >>> Heinz-J�rgen Oertel wrote: > >>>> X15 + X14 + X10 + X8 + X7 + X4 + X3 + 1. > >> though I can't really get the numbers and the 0x4599 in the code to match up > >Why not? 0x4599 has bits number 0, 3, 4, 7, 8, 10 and 14 set. Ring a >bell now?yes, kept seeing 1 as bit 1, it is ofcourse bit 0 -Lasse
Reply by ●April 16, 20082008-04-16
> the pseudo in c would be something like this: > (untestet, inefficient, written in 30 seconds ...) > > unsigned short CRC(unsigned short input) // input only one bit !!! > { > static unsigned short crc_rg; // shiftregister > > crc_rg = crc_rg << 1; // leftshift 1 bit > > if((input & 1) ^ ((crc_rg>>14)&1)) > { > crc_rg = crc_rg ^ 0x4599; > } > > crc_rg = crc_rg & 0x7fff; // only 15 bits > > return crc_rg; > > } > > -LasseAh!!! This I can understand. Thank you very much. Unfortunately, when I run the above code I get a different CRC result than the one that shows up on the o-scope from my hardware :( Anyone know what I'm doing wrong? For what it's worth I also tried the inversion value to 0x4599 of 0x4CD1 as listed on the Wikipedia page for Cyclic_redundancy_check and it didn't work either. ??? -Will CAN Message as it appears on o-scope: 00010000010001100000110000010010000010000011000001001100101010011001101111111 bit stuffing removed: 00010000000011000001000000010000000000100000001100101010011001101111111 separated into fields: SOF IDT[28:18] SRR IDE IDT[17:0] RTR r1 r0 DLC Data(1 byte) CRC CRC_del. ACK ACK_del. EOF 0 00100000000 1 1 000001000000010000 0 0 0 0001 00000001 100101010011001 1 0 1 111111 so the hardware CRC for the above message is 100101010011001 or 19,097 All of my bits on the software (after stuffing) match the o-scope picture until the CRC, which does not match My software crc after each bit passes through: 000000000000000 = 0 000000000000000 = 0 000000000000000 = 0 100010110011001 = 17,817 001100110100010 = 6,562 011001101000100 = 13,124 010001100010001 = 8,977 001000100101011 = 4,395 011000011000110 = 12,486 010010000010101 = 9,237 001111100100011 = 7,971 010110011010110 = 11,478 101100110101100 = 22,956 111011011000001 = 30,401 011101010001011 = 14,987 010001000011111 = 8,735 001001100110111 = 4,919 011010011111110 = 13,566 010110001100101 = 11,365 100101001011010 = 19,034 001010010110100 = 5,300 010100101101000 = 10,600 001011101001001 = 5,961 011110000000010 = 15,362 011110110011101 = 15,773 010110000110011 = 11,315 000111101101111 = 3,951 100100111010111 = 18,903 000000100111110 = 318 000001001111100 = 636 000010011111000 = 1,272 000100111110000 = 2,544 001001111100000 = 5,088 010011111000000 = 10,176 000101000011001 = 2,585 000011010100010 = 1,698 000110101000100 = 3,396 001101010001000 = 6,792 111000010001001 = 28,809 011011000011011 = 13,851 011101100111111 = 15,167 010000101110111 = 8,567 001010111100111 = 5,607 011100101011110 = 14,686 011011100100101 = 14,117 011100101000011 = 14,659 110000000010110 = 24,598
Reply by ●April 17, 20082008-04-17
larkmore@aol.com wrote:>> the pseudo in c would be something like this: >> (untestet, inefficient, written in 30 seconds ...) >> >> unsigned short CRC(unsigned short input) // input only one bit !!! >> { >> static unsigned short crc_rg; // shiftregister >> >> crc_rg = crc_rg << 1; // leftshift 1 bit >> >> if((input & 1) ^ ((crc_rg>>14)&1)) >> { >> crc_rg = crc_rg ^ 0x4599; >> } >> >> crc_rg = crc_rg & 0x7fff; // only 15 bits >> >> return crc_rg; >> >> } >> >> -Lasse > > Ah!!! This I can understand. Thank you very much. Unfortunately, > when I run the above code I get a different CRC result than the one > that shows up on the o-scope from my hardware :( Anyone know what > I'm doing wrong? For what it's worth I also tried the inversion value > to 0x4599 of 0x4CD1 as listed on the Wikipedia page for > Cyclic_redundancy_check and it didn't work either. ??? > -Will > > CAN Message as it appears on o-scope: > 00010000010001100000110000010010000010000011000001001100101010011001101111111 > bit stuffing removed: > 00010000000011000001000000010000000000100000001100101010011001101111111 > separated into fields: > SOF IDT[28:18] SRR IDE IDT[17:0] RTR r1 r0 DLC Data(1 byte) CRC > CRC_del. ACK ACK_del. EOF > 0 00100000000 1 1 000001000000010000 0 0 0 0001 00000001 > 100101010011001 1 0 1 111111 > > so the hardware CRC for the above message is 100101010011001 or 19,097 > > All of my bits on the software (after stuffing) match the o-scope > picture until the CRC, which does not match > > My software crc after each bit passes through: > 000000000000000 = 0 > 000000000000000 = 0 > 000000000000000 = 0 > 100010110011001 = 17,817 > 001100110100010 = 6,562 > 011001101000100 = 13,124 > 010001100010001 = 8,977 > 001000100101011 = 4,395 > 011000011000110 = 12,486 > 010010000010101 = 9,237 > 001111100100011 = 7,971 > 010110011010110 = 11,478 > 101100110101100 = 22,956 > 111011011000001 = 30,401 > 011101010001011 = 14,987 > 010001000011111 = 8,735 > 001001100110111 = 4,919 > 011010011111110 = 13,566 > 010110001100101 = 11,365 > 100101001011010 = 19,034 > 001010010110100 = 5,300 > 010100101101000 = 10,600 > 001011101001001 = 5,961 > 011110000000010 = 15,362 > 011110110011101 = 15,773 > 010110000110011 = 11,315 > 000111101101111 = 3,951 > 100100111010111 = 18,903 > 000000100111110 = 318 > 000001001111100 = 636 > 000010011111000 = 1,272 > 000100111110000 = 2,544 > 001001111100000 = 5,088 > 010011111000000 = 10,176 > 000101000011001 = 2,585 > 000011010100010 = 1,698 > 000110101000100 = 3,396 > 001101010001000 = 6,792 > 111000010001001 = 28,809 > 011011000011011 = 13,851 > 011101100111111 = 15,167 > 010000101110111 = 8,567 > 001010111100111 = 5,607 > 011100101011110 = 14,686 > 011011100100101 = 14,117 > 011100101000011 = 14,659 > 110000000010110 = 24,598The Polynomial must be different Should it be 0xC599 ?