Initialization of checksums

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Can anybody let me know what is the ideal value for initial value of a
checksum, if at all there is one.Also what is ur idea about checksums
that employ simple addition - i mean their reliability??

Re: Initialization of checksums
Quoted text here. Click to load it

Nothing is to be gained from any particular initial value, in the
general case.  Or to turn it around: if you have to worry about the
initial value in any way other than possibly disallowing some
degenerate cases, the checksum is flawed anyway and not worth
bothering with.

Quoted text here. Click to load it

Impossible to tell without knowing what kind of fault you're trying to
checksum against.  Checksumming without a fault model is like
treatment without proper diagnosis: it'll just be useless if you're
lucky, but may be desastrous if you're not.

--
Hans-Bernhard Broeker ( snipped-for-privacy@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

Re: Initialization of checksums
Quoted text here. Click to load it
In CRCs an intial value of 0000 and a string of bytes with the
value 00 at the beginning would not allow you detect a missing
byte. So for CRCs a nonzero value like FFFF is usually used.
But in a checksum over memory missing byte is probably not a
problem.

For memory options are ( 8 bit CPU, code in assembler assumed ):
* addition: compact code, fast, insecure
* 8 bit CRC : compact code in slow implementation, insecure
              not much better then addition, only slower.
* Fletcher : a compromise in speed/code/security
* 16 bit CRC : probably too slow or bulky code for fast
               implementation ;
               but: good security

Fletcher is worth a look.
  As for "faultmodel": if one has time to play its educational to
fill an array with random numbers, flip a specified number
( 1 - 10 ) of bits with location given by a another random number
generator. And watch the different checksums detect or not detect.

MfG  JRD

Re: Initialization of checksums
@t-online.de:

Quoted text here. Click to load it


So is it fair to say that with a standard 8 bit addition CRC, any packet
sent has a 1/256 chance of being of being read as GOOD, when infact it is
BAD?

DaveC

Re: Initialization of checksums

Quoted text here. Click to load it

Not sure what an "addition CRC" is, but I don't think it matters.

Quoted text here. Click to load it

Yes. If you randomly change some of the data (including the
checksum), you have a 1/256 chance of the resulting
packet/checksum combination checking OK.  That's what you
meant, right?

With a 16-bit checksum (CRC or otherwise), a randomly generated
packet and checksum will be check OK with a probability of
1/56536.

--
Grant Edwards                   grante             Yow!  I'm pretending I'm
                                  at               pulling in a TROUT! Am I
We've slightly trimmed the long signature. Click to see the full one.
Re: Initialization of checksums

Quoted text here. Click to load it

We all know I meant 1/65536, right?


--
Grant Edwards                   grante             Yow!  I'm a fuschia bowling
                                  at               ball somewhere in Brittany
We've slightly trimmed the long signature. Click to see the full one.
Re: Initialization of checksums
On 12 Jul, in article

Quoted text here. Click to load it

Well I was thinking of following up then thought, no it is just a typo
that we all make from time to tiem....

--
Paul Carpenter        | snipped-for-privacy@pcserv.demon.co.uk
<http://www.pcserv.demon.co.uk/ Main Site
We've slightly trimmed the long signature. Click to see the full one.
Re: Initialization of checksums
comp.arch.embedded:

Quoted text here. Click to load it

I thought it was little-endian! ;)

--
Jack Klein
Home: http://JK-Technology.Com
We've slightly trimmed the long signature. Click to see the full one.
Re: Initialization of checksums
Quoted text here. Click to load it
Simple test i once did:
A field with 8 bytes, the last byte is the checksum.
The first 7 bytes are filled with random numbers, then the checksum
is calculated. 5 variants were used:
* addition
* XOR all bytes ( used in chipcards )
* 8 bit CRC Poly "TM"   8Ch = Dallas TouchMemory
* 8 bit CRC Poly "PDV"  E0h
* 8 bit CRC Poly "CRC8" 4Dh
Then 1 - 8 bits ( column "errors" ) in the 8 byte field were flipped,
location given by random number generator. Test was done 1000d times
( "samples" ). But when one is flipping 2 bits it may happen,
that the second time one is hitting the same location and so
the message isnīt changed at all ( "identical" ) and
there is no error to be detected.
This leaves the "deteteced" errors and more interesting the "missed"
errors.

All 8 bit CRCs arenīt created equal it seems, but i do not see them
as beeing much better then addition.

MFG  JRD




\ CRC TM
Errors01% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors02% Samples03%E8 Missed00%00 Detected03%D0 Identical00%18
Errors03% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors04% Samples03%E8 Missed00%06 Detected03%DF Identical00%03
Errors05% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors06% Samples03%E8 Missed00%05 Detected03%E3 Identical00%00
Errors07% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors08% Samples03%E8 Missed00%04 Detected03%E4 Identical00%00

\ CRC PDV-Bus
Errors01% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors02% Samples03%E8 Missed00%00 Detected03%D0 Identical00%18
Errors03% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors04% Samples03%E8 Missed00%10 Detected03%D5 Identical00%03
Errors05% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors06% Samples03%E8 Missed00%09 Detected03%DF Identical00%00
Errors07% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors08% Samples03%E8 Missed00%04 Detected03%E4 Identical00%00

\ CRC CRC8
Errors01% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors02% Samples03%E8 Missed00%0B Detected03%C5 Identical00%18
Errors03% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors04% Samples03%E8 Missed00%0F Detected03%D6 Identical00%03
Errors05% Samples03%E8 Missed00%05 Detected03%E3 Identical00%00
Errors06% Samples03%E8 Missed00%0B Detected03%DD Identical00%00
Errors07% Samples03%E8 Missed00%08 Detected03%E0 Identical00%00
Errors08% Samples03%E8 Missed00%06 Detected03%E2 Identical00%00

\ +
Errors01% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors02% Samples03%E8 Missed00%3D Detected03%93 Identical00%18
Errors03% Samples03%E8 Missed00%08 Detected03%E0 Identical00%00
Errors04% Samples03%E8 Missed00%12 Detected03%D3 Identical00%03
Errors05% Samples03%E8 Missed00%08 Detected03%E0 Identical00%00
Errors06% Samples03%E8 Missed00%06 Detected03%E2 Identical00%00
Errors07% Samples03%E8 Missed00%02 Detected03%E6 Identical00%00
Errors08% Samples03%E8 Missed00%0A Detected03%DE Identical00%00

\ XOR
Errors01% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors02% Samples03%E8 Missed00%63 Detected03%6D Identical00%18
Errors03% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors04% Samples03%E8 Missed00%24 Detected03%C1 Identical00%03
Errors05% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors06% Samples03%E8 Missed00%11 Detected03%D7 Identical00%00
Errors07% Samples03%E8 Missed00%00 Detected03%E8 Identical00%00
Errors08% Samples03%E8 Missed00%0D Detected03%DB Identical00%00

Re: Initialization of checksums
Quoted text here. Click to load it


I agree with the above, just want to add some...

The CRC's generally guarantee to detect any up-to-three bit errors and
any odd-number-of-bits errors if a proper generator polynomial is
chosen (go with a standard one). This holds for any distribution of
the errors within the checksummed area. They are also capable of
detecting any burst error shorter than the length of the crc itself
(15 bits for a CRC16). This makes CRC's very good for serial
communication lines where occasional single-bit errors or burst errors
are expected.

If only single bit errors with a low probability are expected a CRC8
will then outperform an additive 8-bit checksum by far since it will
never fail until you get four errors in the same message (with a
probability of 1/256) while the additive checksum may fail already at
two errors (with 1/256 probability). If the prbability of an error in
a message is P=1/1000 the probability of an undetected error using CRC
is P raised to 4 times a constant while using the additive checksum
the probability is P raised to 2 times the same constant. The
difference in detection capability in this example is about one to a
million.

If, on the other hand, the checksum is used for memory verification
where errors ususally don't distribute in this way but rather in
larger blocks of data that are totally corrupted, the above reasoning
is not very interesting. Then I would generally recommend a 32-bit
Fletcher checksum because of it's simplicity in implementation. In
this context it is also generally better than a CRC16 (but still not
quite as good as a CRC32...).


Fletche checksum:

int A = 0
int B = 0

for n = 0 to size
   A = A + M[n]
   B = B + A

A and B must be allowed to overflow at 0xFFFF. At the end A and B
holds the checksum

/Pär

Re: Initialization of checksums
On 12 Jul 2004 01:39:33 -0700, snipped-for-privacy@yahoo.co.in (vishal)

Quoted text here. Click to load it

If you're talking about checksums and not CRC's, then there's no real
advantage of having a particular initial value -- it  might as well be
0. You have a 1 in 256 chance of detecting an error for an 8 bit
checksum. If the data is of high criticality, then I would employ a
CRC-16 or more.

Ken.

+====================================+
I hate junk email. Please direct any
genuine email to: kenlee at hotpop.com

Re: Initialization of checksums
On 12 Jul 2004 01:39:33 -0700, snipped-for-privacy@yahoo.co.in (vishal)

Quoted text here. Click to load it

As others have pointed out, the reliability of a single byte checksums
is quite limited, but if you use it in some (communication) systems
with a (link) failure might appear as along string of 0x00 bytes, it
would be a good idea to avoid the initial value of 0x00, since the
checksum would match all the time.

Also if instead of checksum, you are using longitudinal parity (XORing
every byte) an error condition of all 0x00 would always go undetected
with an initial value of 0x00. An error condition of all 0xFF bytes
would go undetected 50 % of the cases with initial values of 0x00 or
0xFF. Thus, an initial value with only a few bits set (such as 0xA5)
might be a better idea.

In addition to communication links you might get all 0x00 or all 0xFF
error situations with unprogrammed EPROMS or EPROMS (or other chips)
missing from their sockets, so avoiding 0x00 and 0xFF as the initial
value for checksum or longitudinal parity might be a good idea. For a
routine EPROM consistency check, the checksum should be enough, unless
you expect high error rates e.g. due to radiation.

Paul
  

Site Timeline