Re: Opinions on 16-bit checksums.

From: David Brown (david_at_no.westcontrol.spam.com)
Date: 08/26/04

  • Next message: Ulf Samuelsson: "Re: Looking for 3 serial port processor" 
    Date: Thu, 26 Aug 2004 09:04:27 +0200

    "Grant Edwards" <grante@visi.com> wrote in message
    news:412d69d4$0$8087$a1866201@newsreader.visi.com...
    > On 2004-08-26, CBFalconer <cbfalconer@yahoo.com> wrote:
    >
    > >> In 20 years of embedded systems development when 16 bit (or bigger)
    > >> CRCs are used, I've witnessed no failures or oddities. During that
    > >> period I've had about a dozen failures with checksums. Simple
    > >> experience dictates it as such.
    > >>
    > >> Plus, I'm not a math whiz, but IIRC, CRC is significantly better
    > >> than checksum because it also has data position order and sequence
    > >> dependencies, and checksum doesn't.
    > >
    > > I can't prove it, but I contend that no single bit error can
    > > possibly result in an unchanged CRC checksum. I suspect that this
    > > applies to some possible maximum number of bit errors. There are
    > > other methods optimized to detect burst errors.
    >
    > Using a properly chosen generator polynomial, a CRC checksum
    > can detect:
    >
    > * any two bits in error
    > * any odd number of bits in error
    > * an error burst as long as the checksum
    >
    > [This is common knowledge and I'm not disputing it.]
    >
    > There are two big reasons CRCs are used in serial communications:
    >
    > 1) They can detect burst errors better than many other
    > algorithms.
    >
    > 2) They are very cheap to implement on-the-fly in hardware
    > using a shift register and a handful of exclusive-or gates.
    >
    > Because of thise, they are particularly well suited to a serial
    > processing of a bit stream of arbitrary length when errors tend
    > to come in bursts (e.g. due to Rayleigh fading).
    >
    > I don't see that either of these reasons is applicable when
    > verifying ROMs in software:
    >
    > 1) Nobody has ever shown me that ROM failures have "bursty"
    > characteristics similar to serial communications in a noisy
    > environment.
    >
    > 2) CRCs aren't particularly cheap to implement in software. [I
    > suspect that's why IP headers don't use CRCs.]
    >

    I would agree with this. The sort of errors that could turn up in flash
    can, I think, be divided into a number of groups:

    a) Serious muck-ups, such as half-finished program updates. The number of
    errors are so great that any 16-bit checksum would have a 1/65536 chance of
    spotting it. All 1's or all 0's should fail.

    b) Bad erasing (leading to too many 0's) or under programming (too many
    1's). There is no point about having an algorithm guarenteed to spot any
    two-bit error, when there is either no error, or a whole bunch of errors
    scattered about the sector.

    c) Hardware errors - bad address lines or bad data lines. For data lines,
    the effect will be similar to b), but for address lines you may get repeated
    data, or data in the wrong order. Here there will be a slight edge for
    algorithms that consider the order of the data as well as the value - a
    plain sum will not be as good as a crc.

    I think if you want some sort of guartentee of the errors your check can
    deal with, you have to use a much more serious algorithm like md5 that is
    made for big files. A 16-bit CRC might be fine for a 160-bit serial
    message - but if you are using it to check a 200k program, your scale is out
    by a factor of 10000. You can deal with the problem by making crc checks of
    small sections, and then checking them, but is it worth it? If you are
    using NAND flash, which is expected to have a realistic chance of failure,
    then the answer is yes. For normal NOR flash, the chances are tiny, other
    than through user (programmer :-) error, and so almost any check will be
    fine. A checksum where the sum is rotated (*not* shifted) left one bit
    before adding would be about as good as anything else, as far as I can see.

    > --
    > Grant Edwards grante Yow! Now KEN and
    BARBIE
    > at are PERMANENTLY
    ADDICTED to
    > visi.com MIND-ALTERING DRUGS...

  • Next message: Ulf Samuelsson: "Re: Looking for 3 serial port processor"

    Relevant Pages

    • Re: CRC versus CheckSum
      ... I have a situation where I have a byte in which to place either a checksum ... Our packets cannot have bytes in a packet swapped in order (the transport ... jsut as good as the CRC. ... Neither detect all errors (there are after all the same number of states for the sum in either case). ...
      (comp.arch.embedded)
    • Re: Opinions on 16-bit checksums.
      ... it's no longer a checksum, ... >> cancel themselves out, but a CRC would. ... I've witnessed no failures or oddities. ... I don't think it can be assumed that ROMs ...
      (comp.arch.embedded)
    • Re: Crc16 on power failure
      ... a checksum is faster to calculate than a CRC by software. ... True, they are faster, but they are not nearly as good at detecting ... coonsider running an EEC on each parameter instead of a block check. ...
      (comp.arch.embedded)
    • Re: Opinions on 16-bit checksums.
      ... out there besides CRC and "add up the bytes". ... There are other checksum ... I don't think it can be assumed that ROMs ... ROMs do have the same error characteristics as a serial data ...
      (comp.arch.embedded)
    • Re: UDP vs TCP
      ... therefore I need to do CRC check myself. ... So happen you mentioned serial communications, I am looking for some information on that as well. ... If two computers are connected via serial comm, it has nothing to do with UDP or TCP, correct? ... HOWEVER, the fact is, only the first message was screwed up, the second message was actually delivered properly. ...
      (microsoft.public.vb.enterprise)