>
> on Wed, 21 May 1997 06:44:13 -0700 Dan Mulally wrote
>
> > I've been seeing the messages on various error checking routines such as
> > Hamming and CRC. I had a project that uses 32 bit "packets" to transfer
>
> I have dabbled with Hamming, CRC, and checksums
>
> -SNIP-
>
> > best way but it was easy. I've read that the checksum method is not as
> > sensitive to detecting errors as other methods and I have no idea of the
> > odds of this method giving a correct checksum with errors in the data.
>
> If you just fed random numbers into your system as described you
> would get bad data slipping through every 1 in 256 times. As your
> checksum could hold any of 256 combinations and one of them must be
> correct. Because of this I have used 16bit checksums to cut down on
> the chances of this happening.
I wonder how this method would do for a specfic bit-error rate, say 1
error in 1000 bits (10E-3)? I'm actually using more than 8 bits because
I look for four good frames in a row to get frame sync and so random
data would be unlikly to cause it to acquire frame sync. If one frame is
bad after frame sync is aquired, that frame's data is discarded but it
doesn't give up on frame sync until it has 4 bad frames.
>
> >
> > Here is the code that does the checksum checking:
> >
> > ;*****************************************************
> > ;Checksum Sub
> > ;*****************************************************
> > chksum bcf flags, chksum_ok ;clear checksum flag
> > movf frame0, 0 ;move frame0 to W
> > addwf frame1, 0 ;add frame1 to W
> > addwf frame2, 0 ;add frame2 to W
> > addwf frame3, 0 ;add frame3 to W
> > xorwf frame4, 0 ;XOR checksum frame with W
> > btfsc status, z ;result = 0? q=yes
> > bsf flags, chksum_ok ;if yes, set checksum flag
> > retlw null ;return with null
> >
> I would be more inclined to XOR all the numbers in the frame together
> but otherwise I have used a 16bit version of what you show above.
It seems like adding would be better than XORing because I'm
"spreading" the information within the 8 bits by the carries
>
> I have also heard that CRC is more robust. It is supposed to be less
> susceptible to added leading zeros on your message. Though this would
> not apply in your fixed message length case. But as far as hard
> facts regarding how sensitive CRC is at detecting errors - I am as
> interested as you - If anyone out there knows this I would like to
> hear.
>
> TIA
>
> p.s. I have a CRC routine written in 6502 if you are interested!!!
> > If you just fed random numbers into your system as described you
> > would get bad data slipping through every 1 in 256 times. As your
> > checksum could hold any of 256 combinations and one of them must be
> > correct. Because of this I have used 16bit checksums to cut down on
> > the chances of this happening.
>
> I wonder how this method would do for a specfic bit-error rate, say 1
> error in 1000 bits (10E-3)? I'm actually using more than 8 bits because
> I look for four good frames in a row to get frame sync and so random
> data would be unlikly to cause it to acquire frame sync. If one frame is
> bad after frame sync is aquired, that frame's data is discarded but it
> doesn't give up on frame sync until it has 4 bad frames.
If your data rate is one error per 1000 bits, and all bit errors are
independent (i.e. every bit has a 0.001 chance of being bad, regardless
of whether any other bits are bad), then the likelihood of a wrong packet
passing a checksum/xorsum [assuming 56-bit data, 8-bit check] will be
about equal to the likelihood that at least one bit position will have two
faults out of eight. There are 56*8 ways that this can happen, and the
likelihood of any particular one of them occuring is (literally) one in a
million, so the likelihood of 'any' of them occuring is about 450/million,
or 1 in 2200.
With an eight-bit CRC, using error *detection*, there must be at least
four bits in error for a bad packet to slip through. The probability of
that happening is about 1 in 1.5 million. Since a CRC will detect the
majority of 4 bit errors (albeit not all) the likelihood of a bad packet
slipping through are reduced even further.
If the application requires error *correction*, then any packet which
contains a single bit error will be correctable, those containing
double-bit errors will always be flagged as invalid, and those containing
triple-bit errors may be misinterpreted. This gives us approximately...
1 in 500 probability of an unrecoverable packet (double-bit failure or
worse)
1 in 24,000 probability of a potential falsely-recognized packet (triple
bit failure or worse).
If the error rate on the input data stream is 1 in 1000 bits, then use of
anything less than an 8-bit CRC (not a mere checksum) is foolish if the
data is of any importance. A CRC will also permit probable reconstruction
of damaged packets, assuming all errors to be independent, albeit with a
higher risk of regarding a 'bad' packet as good. If there is any
likelihood of correlated bit errors (e.g. modem line noise) then unless
there are other mechanisms for detecting garbled transmissions (e.g.
framing errors or protocol violations) the dominant risk factor may be
that of a "random" packet (large numbers of random bits). CRC's,
checksums, and xor'sums all do about equally well in this case. If the
data contains eight or fewer consecutive bits which have been randomized,
all three methods are guaranteed to detect the error, but if nine or
more consecutive bits have been randomized, any method will have a 1 in
256 chance of passing a bad packet.
> > I would be more inclined to XOR all the numbers in the frame together
> > but otherwise I have used a 16bit version of what you show above.
There are pros and cons to checksum versus XORsum. Both methods are
substantially inferior to CRC at dealing with random errors, and all three
methods fare equally against cluster errors.
> It seems like adding would be better than XORing because I'm
> "spreading" the information within the 8 bits by the carries
The spreading of information via carries helps *a little*, but not
much. A CRC is much more effective at spreading information.
> > I have also heard that CRC is more robust. It is supposed to be less
> > susceptible to added leading zeros on your message. Though this would
> > not apply in your fixed message length case. But as far as hard
> > facts regarding how sensitive CRC is at detecting errors - I am as
> > interested as you - If anyone out there knows this I would like to
> > hear.
Essentially, every bit in a CRC'd message will change about half the bits
in the CRC (though each bit will change a different set of CRC bits). In
a good CRC, every bit change will change an *ODD* number of bits in the
CRC; consequently, changing an odd number of bits will alter the parity of
the message and be detected. Further, because every bit in the message
will change more than one bit in the CRC (actually, at least three bits)
and no two bits in the message alter the same set of CRC bits, it's also
impossible for any double-bit error to escape detection. CRC's are truly
an excellent method of error detection and on a PIC they can be coded
quite efficiently.
BTW, you may sometimes see reference to "Fletcher's Checksum". It's
computed as:
csum1 = csum2 = 0
for each byte of message:
csum1 = (csum1 + data) mod 255
csum2 = (csum2 + csum1) mod 255
at end:
send csum1 and csum2
Fletcher's checksum does look appealing, and would appear at first glance
to be robust. In fact, however, it has a number of weaknesses:
[1] Because 255 equals 3*5*17, every third, fifth, and seventeenth byte
from the end of the packet will be checksummed weakly by csum2 (i.e. may
be altered to one or more alternative values without altering csum2). For
example, if the sixth-to-last byte (6 is a multiple of 3) is supposed to
be a 5, then adding 85 or 170 (85 == 255/3) will not alter csum2.
[2] For packets of length 255 or greater, the 255th, 510th, etc. bytes
from the end will have no effect whatsoever on csum2 [this is just an
extension of problem 1]
[3] Problem [1] may be solved by using 251 (a prime number) as the modulus
instead of 255. In fact, for packets of length 250 or less, Fletcher's
checksum (mod 251) isn't all that bad. Even that, however, still has the
weakness that any data byte of 0, 1, 2, 3, or 4 may be substituted for
251, 252, 253, 254, or 255 without altering the checksum; this is perhaps
not as severe a weakness as with modulus 255 where a byte of 00 and FF
will checksum identically, but it's still not good.
If 16 bits are available for a check field (as Fletcher's checksum would
require) a CRC-16 is a much better choice. There is, however, from what
I've read at least one telecom standard that uses Fletcher's (mod 255 no
less!) so you should be aware of it.
> > I would be more inclined to XOR all the numbers in the frame together
> > but otherwise I have used a 16bit version of what you show above.
>
> It seems like adding would be better than XORing because I'm
> "spreading" the information within the 8 bits by the carries
I've been debating whether or not to answer the recent questions
regarding error-control coding... I've decided not to, because I
just don't have the time right now to do the subject justice
here on teh PICLIST. Maybe I'll put something up on my web page
in a week or so.
In the meantime, however, I can touch very briefly on the
addition-modulo-256 (ADD) vs. addition-modulo-2 (XOR) issue.
Dan: You're correct when you say that adding "spreads the
information". Unfortunately, it only spreads it LEFTWARD (i.e.,
toward the MSB)... Assuming that your checksum is no wider than
each of your information words, the most-significant bit of each
information word only affects (at best) the most-significant bit
of the checksum.
Unless you know that the errors are more likely to occur in the
least-significant bits of your information words, there's no
real advantage to ADDing over XORing.
Also, while both techniques will always detect a single error
and both can be fooled by two-bit errors, only the XOR method
will always detect all 3-bit errors (in fact, it'll detect ALL
errors that involve an odd number of bits).
> > It seems like adding would be better than XORing because I'm
> > "spreading" the information within the 8 bits by the carries
>
> In the meantime, however, I can touch very briefly on the
> addition-modulo-256 (ADD) vs. addition-modulo-2 (XOR) issue.
>
> Dan: You're correct when you say that adding "spreads the
> information". Unfortunately, it only spreads it LEFTWARD (i.e.,
> toward the MSB)... Assuming that your checksum is no wider than
> each of your information words, the most-significant bit of each
> information word only affects (at best) the most-significant bit
> of the checksum.
There are a number of easy improvements to get around this problem;
swapf'ing the checksum after every byte, for example, would allow changes
in bit 7 to result in changes to bit 4. The amount of spreading, however,
really is pretty small. Further, the carry-bit propagation makes it much
harder to do any substantive analysis of checksums' effectiveness that an
XORsum or CRC's.
> Unless you know that the errors are more likely to occur in the
> least-significant bits of your information words, there's no
> real advantage to ADDing over XORing.
Data should be checksum/crc'ed/whatever in whatever base was used in its
transmission. If the transmission takes pairs of bits and converts them
into tones (and the same bit positions are always paired) then it probably
makes sense to compute checksums on each 2-bit group. Since most
communication is binary, however, base-2 operations are probably best.
> Also, while both techniques will always detect a single error
> and both can be fooled by two-bit errors, only the XOR method
> will always detect all 3-bit errors (in fact, it'll detect ALL
> errors that involve an odd number of bits).
This is a point I'd not considered; I expect, however, that in practice a
checksum and xorsum are about equal in terms of what they'll
detect/correct while a CRC (though a little harder to implement) is much
better.
silver.sdsmt.edu>
