Subject:
|
Re: LNP Repost (Checksum algorithm)
|
Newsgroups:
|
lugnet.robotics.rcx.legos
|
Date:
|
Wed, 28 Jul 1999 19:25:26 GMT
|
Viewed:
|
1041 times
|
| |
|
|
This has little (Err... nothing in fact) to do with Lego, but worth noting as
it is handy when you need a good SW checksum!
In lugnet.robotics.rcx.legos, Ben Laurie writes:
> Kevin Baker wrote:
> > ...may I suggest the following algorithm (Minus typos!):
> >
> > unsigned short
> > checksum(
> > unsigned char *data,
> > unsigned length
> > ) {
> > unsigned char a = 0xff;
> > unsigned char b = 0xff;
> >
> > while (length > 0) {
> > a = a + *data;
> > b = b + a;
> > data++;
> > length--;
> > }
> >
> > return a + (b * 256);
> > }
> > ....
>
> I remember that! But aren't you supposed to do it mod 255 for maximum
> effectiveness?
>
> Cheers,
>
> Ben.
Indeed, as you say the standard I mentioned does use mod 255 (See Annex C
ISO/IEC 8473-1 : 1994
[http://www.acm.org/sigcomm/standards/iso_stds/CLNP/index.html]). As far as I
can see this is for 2 reasons:
1) mod 255 is better at spotting some double bit errors.
2) 8473-1 includes the option of using '0' as the checksum if you haven't
calculated it!!!!
However, mod 256 is better at spotting burst errors (As it does not confuse 0
& 255), as mod 255 will generate the same checksum for both:
0x11 0xff 0x11
and
0x11 0x00 0x11.
The original algorithm is covered in "An Arithmetic Checksum for Serial
Transmission", John G. Fletcher. IEEE Transaction on Communications, Vol. COM-
30, No 1, January 1982.
To give an idea of effectiveness, see the following, which (I think) comes
from the Fletcher publication:
CRC Mod 255 Mod 256
0.001526% 0.001538% 0.001526% Fraction of all errors undetected.
none 0.000019% none Fraction of 16-bit burst errors undetected.
none none none Single bit errors undetected.
65535 2040 16 Min separation of undetected double bit errors.
Kevin.
|
|
Message is in Reply To:
 | | Re: LNP Repost
|
| (...) I remember that! But aren't you supposed to do it mod 255 for maximum effectiveness? Cheers, Ben. -- (URL) grandfather once told me that there are two kinds of people: those who work and those who take the credit. He told me to try to be in (...) (25 years ago, 27-Jul-99, to lugnet.robotics.rcx.legos)
|
21 Messages in This Thread:
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
