16F88 RS232 bootloader.
Byron A Jeff email (remove spam text)
On Sat, Jun 26, 2004 at 11:46:00PM -0600, Robert Rolf wrote:
> The problem with simple XOR checksums is that if any
> bit(s) are bad in an even number of bytes, you don't detect
> the error. e.g. LSB error for two bytes is not detectable.
> 1 xor 1=0 but error of 0 xor 0is also 0. With sum you get 2 or 0,
> which is a clearly detectable difference.
I do believe I said that sometime yesterday.
> Even a true 'checksum' misses any case where any even number of bytes
> have the MSB errored.
Until last night I would have agreed. However after some emperical testing
it's clear that the error rate is in fact the same. There's no difference in
the robustness of addition vs. xor when the checksum size is the same and the
sample size is large.
The next phase, which I did not take into account in my first run of
experiments is the fact that there will only be a few bits difference between
the target and the samples. In other words instead of a pseudo random
sampling of the entire message space we need to concentrate on messages with
a limited Hamming distance from the target. Systematically generated 1 and 2
bit errors should be enough to illustrate the difference since the argument
is that even bit error pairs will screw XOR up.
Since I already have the test frame in place this shouldn't take long
[virtual time passing...]
OK I'm back with interesting results. As expected both caught all 1 bit errors.
But the code went nuts on 2 bit errors with both algorithms (4 byte XOR and
4 single byte adds with no carry inbetween). But the add came out a lot better
The results on 100000 pseudo randomly generated targets:
The sums generated nearly 1/3 less matches than xor over the same sample set.
So the assertion hold true, that adding is better than xor for an even number
of bit errors. Note that there are multiple matches per target, hence the
number of matches coming out larger than the number of targets. That seems
to be a good metric: average number of matches per target. I'll use it from
now on. So the above numbers would be 14.99 and 5.54 matches per target (MPT).
So let's eliminate xor and move onto the checksum size and how important
carry is to the equation. Let's run the same 2 bit error experiment under the
1) 8 bit. Should easily be the worst.
2) 2 8 bits add with no carries inbetween. Should be better but not as good as
3) 16 bit add carrying between the bytes.
Note that we already have the results of a 32 bit checksum with no carries.
That's the 5.54 MPT number above. Also it's a waste of time to do a 32 bit
sum with carries on a 64 byte message because the sum cannot exceed 16 bits
anyway. I'll redo the 32 bit, no carries just to give context.
Be right back....
OK I'm back. Here's the numbers at the 10000 target mark
00000010000 targets analyzed.
total sum[0,8] matches=294811
total sum[0,16] matches=135050
total sum[1,16] matches=294811
total sum[0,32] matches=55342
Where [0,8] means no carries between bytes and an 8 bit checksum. So it's
clear that carries are totally irrelavent, so don't waste time on them.
Extending the number of bits in the checksum improves performance because it
spreads out the errors. Note that we get the same 5.53 MPT. Note that there
are 4032 2 bit error combos. So the 5.53 gives us a 99.86 percent error detect
rate. Not bad for 4 bytes of storage/transmission and 6 times better than
a simple 8 bit checksum.
The results are pretty clear. 8 bit sucks whether or not you split the sums
or not. 32 bits gives enough of an advantage to consider using. adding gives
a significant advantage over xor when multiple bit errors occur.
> CRC is about the only way to reliably detect bit errors.
Agreed. But the truth of the matter is that we're trying to implement a simple
check that won't take a lot of code.
CRC is my next test. I found some algorithms here:
But genpoly wasn't clearly specified and the optimized crc16 kept converging.
So no results yet. I'll try to take a look at it later.
http://www.piclist.com hint: The PICList is archived three different
ways. See http://www.piclist.com/#archives for details.
In reply to: <40DE5F18.6FEA3C84@UAlberta.ca>
See also: www.piclist.com/techref/microchip/ios.htm?key=rs232
You must be a member of the
piclist mailing list
(not only a www.piclist.com member) to post to the