Best checksum for short messages

Hi, I'm remodeling a serial communication protocol in a master/slave multi board device. The messages that are exchanged between the master and any slave are usually less than 50 bytes. Now, a CRC16 is used to check for the message to be valid, and the problem is that it's a waste of space (2 bytes over less than 50) and of time (the uC has to calculate it).

Is that overkill? Is there a simpler checksum we can use with a similar coverage? We just need integrity checking, not error correction.

By the way, is there a common very efficient protocol used to synchronize data among different processors? We'd like to have data structures (machine state) that have to be shared among all the boards (4), via a serial 422 channel.

Thank

Reply to
metiu
Loading thread data ...

Whatever checksum/CRC you will use, it will use at least one byte, so you can save only one byte which is not too much. I would use CRC5 instead.

Reply to
Adrian

With such small messages, I'd be tempted to use a simple two-byte sum. You'll never overflow with a 50-byte message, and it's quick and easy to calculate.

A simple but effective checksum I've used in the past works something like (in pseudo-assembly):

rol sum ; rotate sum left add sum,new ; add new byte into sum adc sum,0 ; if overflow, add carry back in

Hard to do efficiently in C, though. And like a lot of checksums, it doesn't handle leading zeros well unless you initialize the sum to a non-zero value.

Regards, -=Dave

--
Change is inevitable, progress is not.
Reply to
Dave Hansen

It depends on the level of certainty that want. A nice clean solution is to XOR all the bytes together as they come in or as they go out and use the single resultant byte as the checksum.

Thomas

Reply to
Thomas Magma

One variation of this that I've seen a lot is to start with a seed value, typically 0x55 or 0xAA, and then XOR all the bytes together. The idea there is to guard against a null message producing a null checksum.

Steve

formatting link

Reply to
Steve at fivetrees

Is the application already doing it with the table look-up method? If it's bit-banging the thing it can be significantly sped up at the cost of some ROM.

You haven't given enough information. Without knowing the raw probability of error, the cost of having an erroneous packet slip through, or your processor overhead you've asked an impossible question.

If your serial link is like most, however, your comms are probably either dead reliable or really, really sick. In that case you need the error detection for fault indication more than for propping up the protocol.

I would either just use a simple 8-bit sum, a CRC8, or I'd stick with the CRC16.

An 8-bit sum will catch all 1-bit errors, but there's a slew of 2-bit errors that it'll let through. It will (I think) catch 255 out of every

256 bad packets. On a value-per-bit basis it sucks, but it's dead easy to code.

A CRC8 will catch 255 out of every 256 bad packets, and if my intuition is correct a good one will catch all 3-bit errors*. This isn't good enough if someone will die if a bad packet gets through, but it's good enough to pop a fault indication when things go bad.

A CRC16 will catch 32767 out of every 32768 bad packets. Again assuming my intuition is correct it should catch all 7-bit errors. Again, not good enough if someone will die over a bad message, but more than good enough for popping a fault.

At this level everyone seems to roll their own, probably because it's easier to write the code than it is to learn someone else's API. You may want to web search on "field bus" and "RS-485" -- I think there are protocols out there that are used in the process control industry that may answer. You may spend more time learning than you would writing your own code, though...

  • I dug a little bit to find an answer to this, but didn't by the time I exceeded my 'free answer' time limit.
--
Tim Wescott
Wescott Design Services
 Click to see the full signature
Reply to
Tim Wescott

In article , metiu writes

Many years ago I implemented 16-bit plain checksums on such packets (mainly for development speed, one end was assembler, the other C, and I'd have had to do a manual assembler translation of a CRC algorithm and verify it was bug free and matched the original C version).

However, on some customer sites with longer cable lengths we occasionally noticed that errant packets containing two 1-bit errors were being accepted by the receiver, because a plain checksum often won't detect this. Fortunately we had enough packet logging running at one of the sites to actually verify this was what happened.

Since then, CRC16 at least, and if really vital, CRC32 at least. CRC's are particularly good at detecting small burst errors, as often found on lengthy or noisy serial communications. If I felt the data/check ratio per packet was too unpleasant, I'd considering increasing the data content per packet long before decreasing the check content.

Reply to
Bob

Ok, I'll try to answer:

The communications happen in a quite small machine (1m tall, around

0.5m wide and deep), and are quite reliable, since RS-422 is differential.

The machine is a medical device, but no one will die if a bad packet gets through: the boards have an internal monitor which won't allow bad configurations, so the odds of getting both a bad packet with a reasonable configurations are lower than the error rate of the serial link. However, having a good error checking mechanism is very good, especially when inspectors come around!

That's what has been done for our serial protocol in the past, but I just wanted to get some better ideas from other people's experiences.

Thanks very much

Reply to
metiu

-- snip--

Yes, I was hoping to see folks answer this part of your question, too.

--
Tim Wescott
Wescott Design Services
 Click to see the full signature
Reply to
Tim Wescott

The machine is a medical device, but no one will die if a bad packet gets through: the boards have an internal monitor which won't allow bad configurations, so the odds of getting both a bad packet with a reasonable configurations are lower than the error rate of the serial link. !!! And the space shuttle will not blowup because it has two O-Rings Does the math back you up? How many likely error combinations are valid. The proof math for CRCs reliability is quite interesting.

However, having a good error checking mechanism is very good, especially when inspectors come around!

!!! Good attitude?

Reply to
Neil

You can find a list of "good" CRC polynomials for various numbers of CRC bits and lengths of messages at:

formatting link

The reason to use a CRC instead of the other checksum techniques is that you avoid vulnerabilities to two-bit errors (and sometimes more -- check out the Hamming Distance ratings of the CRCs in that paper).

Cheers,

-- Phil

Phil Koopman -- snipped-for-privacy@cmu.edu --

formatting link

Reply to
Philip Koopman

In general a CRC8 is way better than a plain checksum.

Performance all depends on the length of the data word you are protecting with the CRC8. The best polynomial will detect 3-bit errors out to 119 bits of data word. No 8-bit polynomial does better than that.

Most polynomials don't do as well. For example, the standard CRC-8 polynomial catches 3-bit errors up to 85-bit payload lengths, but lets some 2-bit errors get by for any longer packets.

The best CRC16 only catches 7 bit errors out to 15 bits of data word. If you protect a longer payload you'll get worse performance.

I have another posting on this thread with a pointer to a paper that has more thorough data (see table 3 in that paper).

-- Phil

Phil Koopman -- snipped-for-privacy@cmu.edu --

formatting link

Reply to
Philip Koopman

Thanks a lot!

I found your paper very interesting!

Reply to
metiu

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.