For my tank project, I’ll be sending parameters over radio to control the motors so the data packets should be checked to see if they’re valid or if the transmission was corrupted. This is a widely used concept in computing – almost every transaction comes with a checksum which lets you know whether the data that was sent is the same data that you received. If you’ve ever seen a cyclic redundancy check error on older versions of Windows, you’ve seen a bad checksum; the hard drive transmitted something that the operating system checked and found it wasn’t correct.
EDIT
Looks like someone has beaten me to it, and created something much better. Here is an implementation which uses the built-in CRC module on the Teensy 3 to improve CRC calculation speed, and also creates 32 bit checksums.
CRC vs XOR
A CRC check gets the entire packet, and goes byte-by-byte constructing the result, and finally outputs a number. This is done by the sending side, and the CRC result is added to the data packet before everything is sent. On the receiving end, the same CRC calculation is made, and then its result is compared against the checksum in the data packet. If the two match, we’re all good and the data packet can be used. If it fails, either a retransmission is requested or the packet is thrown away without any other action.
A CRC check is better than, say, a XOR checksum – as NMEA GPS sentences have – because with CRC the order of the data matters as well as the content. For example:
DATA: 49 50 51 52 53
XOR Checksum: 31
CRC8: 241 (0xF1)
But if we change the order of the data:
DATA: 50 49 53 51 52
XOR Checksum: 31
CRC8: 180 (0xB4)
As you can see, with a XOR checksum, the first and the second packets would pass. Think of it like a suitcase; XOR would check whether your suitcase has all of your belongings, while CRC would make sure you have everything and its packed in the right place. Granted, reordering errors are likely to be pretty slim with the data I’m sending however the functionality is there.
Implementing a CRC check is pretty easy as a bunch of people have already done it – there is nothing better than treading the same path as smarter people. In fact, my problem is that they have already implemented the better form of CRC; CRC32. Without getting too in-depth, the number after CRC is the number of bits that the resulting checksum will be. The lower the number, the more likely you’ll encounter collisions which is where two separate strings have the same checksum. This is a major issue for some in the IT security business, but for my little tank it shouldn’t be a problem.
Implementation
After reading leonardomiliani‘s post, it was easy to implement a check with an Arduino, but I would be sending data from a web server; most likely running PHP. I decided to knock up a script to do the same thing, and then I would have both sides using the same CRC calculation.
Now that we can create a checksum, the next step is figuring out comparing, retransmission, and other operations.
Arduino
[c]
// Found on http://www.leonardomiliani.com/en/2013/un-semplice-crc8-per-arduino/
//CRC-8 – based on the CRC8 formulas by Dallas/Maxim
//code released under the terms of the GNU GPL 3.0 license
byte CRC8(const byte *data, byte len) {
byte crc = 0x00;
while (len–) {
byte extract = *data++;
for (byte tempI = 8; tempI; tempI–) {
byte sum = (crc ^ extract) & 0x01;
crc >>= 1;
if (sum) {
crc ^= 0x8C;
}
extract >>= 1;
}
}
return crc;
}
[/c]
PHP
[php]
// This produces results the same as: http://www.leonardomiliani.com/en/2013/un-semplice-crc8-per-arduino/
function crc8($string) {
$len = strlen($string) – 1;
$crc = 0x00;
$i = 0;
while ($len–) {
$extract = ord($string[$i]);
for ($t = 8; $t; $t–) {
$sum = ($crc ^ $extract) & 0x01;
$crc >>= 1;
if ($sum) {
$crc ^= 0x8C;
}
$extract >>= 1;
}
$i++;
}
return $crc;
}
[/php]