Searching \ for '[Fwd: Re: Error checking]' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=error+checking+error
Search entire site for: 'Re: Error checking]'.

Exact match. Not showing close matches.
PICList Thread
'[Fwd: Re: Error checking]'
1997\05\22@205738 by Dan Mulally

flavicon
face
Message-ID: <spam_OUT3384930D.551BTakeThisOuTspamsilver.sdsmt.edu>
Date: Thu, 22 May 1997 11:40:13 -0700
From: Dan Mulally <.....dmulallyKILLspamspam@spam@silver.sdsmt.edu>
X-Mailer: Mozilla 3.01 (Win16; I)
MIME-Version: 1.0
To: Martin Lane <MLanespamKILLspammetrol.co.uk>
Subject: Re: Error checking
References: <.....19970521162741.055ba70e.inKILLspamspam.....metrol.wintermute.co.uk>> Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

{Quote hidden}

       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.

{Quote hidden}

       It seems like adding would be better than XORing because I'm
"spreading" the information within the 8 bits by the carries

{Quote hidden}

       I would like to see that routine. Thanks Martin.

Dan Mulally
EraseMEdmulallyspam_OUTspamTakeThisOuTsilver.sdsmt.edu

1997\05\23@022310 by John Payson

flavicon
face
> > 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.

1997\05\23@034538 by Andrew Warren

face
flavicon
face
Dan Mulally <PICLISTspamspam_OUTMITVMA.MIT.EDU> wrote:

> > 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).

   -Andy

=== Andrew Warren - @spam@fastfwdKILLspamspamix.netcom.com
=== Fast Forward Engineering, Vista, California
=== http://www.geocities.com/SiliconValley/2499

1997\05\23@215347 by John Payson

flavicon
face
> > 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.

More... (looser matching)
- Last day of these posts
- In 1997 , 1998 only
- Today
- New search...