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

Re: Initialization of checksums

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.

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.

Hans-Bernhard Broeker ( snipped-for-privacy@physik.rwth-aachen.de)

Even if all the snow were burnt, ashes would remain.

Re: Initialization of checksums

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

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

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

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

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

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

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

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)

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

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

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

- » Reverse current into a lithium battery
- — Next thread in » Embedded Programming

- » MC35 PPPstack transmit/receive counters?
- — Previous thread in » Embedded Programming

- » Static JSON parser for embedded
- — Newest thread in » Embedded Programming

- » Do we have to lease out 24GHz?
- — The site's Newest Thread. Posted in » Electronics Design