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

metiu wrote:
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.

On 24 Mar 2006 06:07:29 -0800 in comp.arch.embedded, "Adrian"
<adrianbica@yahoo.com> wrote:

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.

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

"metiu" <metiu.uitem@gmail.com> wrote in message
news:1143208131.602805.297670@j33g2000cwa.googlegr oups.com...

"Thomas Magma" <somewhere@overtherainbow.com> wrote in message
news:Y9VUf.177422$H%4.21386@pd7tw2no...
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
http://www.fivetrees.com

metiu wrote:
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.
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
http://www.wescottdesign.com

Posting from Google? See http://cfaj.freeshell.org/google/

In article <1143208131.602805.297670@j33g2000cwa.googlegroups .com>,
metiu <metiu.uitem@gmail.com> 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.

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

metiu wrote:



--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Posting from Google? See http://cfaj.freeshell.org/google/

metiu wrote:
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?

"metiu" <metiu.uitem@gmail.com> wrote:

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

http://www.ece.cmu.edu/~koopman/rose...y_embedded.pdf

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 -- koopman@cmu.edu -- http://www.ece.cmu.edu/~koopman

Tim Wescott <tim@seemywebsite.com> wrote:

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 -- koopman@cmu.edu -- http://www.ece.cmu.edu/~koopman

Thanks a lot!

I found your paper very interesting!