Re: [PIC:] 16F88 RS232 bootloader. by Byron A Jeff .

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: xors matches=1499985 sum matches=554578 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 following conditions: 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: http://www.monitor-computing.pwp.blueyonder.co.uk/projects/crc16 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. BAJ {Quote hidden}> > Howard Winter wrote: > > On Sat, 26 Jun 2004 17:50:44 +0200, Kyrre Aalerud wrote: > > > > > Is this better or wose than the sum method ? > > > > If I remember rightly (it's late so I can't think > > clearly enough to check!) if the last byte transmitted > > is the checksum, the result of a rolling XOR of > > everything before, when you XOR it you will end up with > > zero if all was sent correctly. So the receiver just > > XORs everything it receives and the result should be > > zero - easy! > > > > > Maby I can do both ? > > > > No need - it doesn't improve anything. > > XOR is much less robust than sum. See above comments. > Computation overhead is the same. > > Robert > > -- > http://www.piclist.com hint: The PICList is archived three different > ways. See http://www.piclist.com/#archives for details. -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.