CRC / CHKSUM

Started by Eirik Karlsen February 15, 2004
To those of you that are more experienced (than me);
I've now started on a bootloader that will eventually transfer the 14KB program into the FLASH memory.
I'm thinking of breaking the transfer up into 16 or 32 byte frames.
Obviously when the program is finally in the memory every single bit must be correct. So how do you do this?

I can see a few ways of integrity check & error handling:
A: ask for the frame to be sent 3-4 times, and if all are equal then accept it as valid. (slow but safe).
B: checksum validation, resend frame if checksum error. (faster but certain errors may slip trough...unacceptable?)
C: CRC, slightly better than checksum. (fast but certain errors may still slip trough...unacceptable?)
D: error correcting codes like Hamming, Reed-Solomon, and others (somewhat slow and very complex).

I would prefer to go for A and although it is somewhat 'brute force' it is also 100% safe, and most of all it is simple.
Unless you have a better idea?
--
*******************************************
VISIT MY HOME PAGE:
<http://home.online.no/~eikarlse/index.htm>
LAST UPDATED: 23/08/2003
*******************************************
Best Regards
Eirik Karlsen



> I can see a few ways of integrity check & error handling:

- what bit error rate do you expect?
- what chance is acceptable for an erroneous image being accepted as
good? (note that a communication protocol that reduces this chance to 0
does not exist)

Wouter van Ooijen

-- -------
Van Ooijen Technische Informatica: www.voti.nl
consultancy, development, PICmicro products




You should probably consider where errors might occur and data
transmission is only one. Another could be degradation of the flash
over time.

For many years the Intel Hex format has been good enough - the
frames are limited to 16 bytes (32 chars) with checksum. Although
seldom implemented, you could check for extraneous chars between the
CRLF and the next ':'. I suppose you could limit the alpha chars to
upper case (that may be an existing condition of most code).

Another idea that is commonly used: the code itself runs a CRC of
the entire flash every time it starts up. The proper result is
usually in the last bytes of the program code. After all, it is the
code in memory that needs to be error free!

--- In , "Wouter van Ooijen" <wouter@v...>
wrote:
> > I can see a few ways of integrity check & error handling:
>
> - what bit error rate do you expect?
> - what chance is acceptable for an erroneous image being accepted
as
> good? (note that a communication protocol that reduces this chance
to 0
> does not exist)
>
> Wouter van Ooijen
>
> -- -------
> Van Ooijen Technische Informatica: www.voti.nl
> consultancy, development, PICmicro products




Can you read the code back and compare to original?

--- Eirik Karlsen <> wrote:
> To those of you that are more experienced (than me);
> I've now started on a bootloader that will eventually transfer the
> 14KB program into the FLASH memory.
> I'm thinking of breaking the transfer up into 16 or 32 byte frames.
> Obviously when the program is finally in the memory every single bit
> must be correct. So how do you do this?
>
> I can see a few ways of integrity check & error handling:
> A: ask for the frame to be sent 3-4 times, and if all are equal then
> accept it as valid. (slow but safe).
> B: checksum validation, resend frame if checksum error. (faster but
> certain errors may slip trough...unacceptable?)
> C: CRC, slightly better than checksum. (fast but certain errors may
> still slip trough...unacceptable?)
> D: error correcting codes like Hamming, Reed-Solomon, and others
> (somewhat slow and very complex).
>
> I would prefer to go for A and although it is somewhat 'brute force'
> it is also 100% safe, and most of all it is simple.
> Unless you have a better idea? >
> --
> *******************************************
> VISIT MY HOME PAGE:
> <http://home.online.no/~eikarlse/index.htm>
> LAST UPDATED: 23/08/2003
> *******************************************
> Best Regards
> Eirik Karlsen >


=====
My software has no bugs. Only undocumented features.

__________________________________



Hi Eirik
 
There is only one definate solution I have for you - use crc16 checksums.  We use it all the time in industrial comms in Modbus, Can, DF1 and you find it in most Fieldbusses.  I use it all the time to update flash via these busses and it is 100% reliable.  CRC is one of the most (if not the most) reliable check sums.  All our stuff are RTU's in remote areas and we have to have absolute reliability and it is not that difficult.
 
There are some ways to get even more reliability eg.  byte to indicate how many data bytes will follow but crc is still the best
 
regards
Martin
----- Original Message -----
From: Eirik Karlsen
To: p...@yahoogroups.com
Sent: Monday, February 16, 2004 3:44 AM
Subject: [piclist] CRC / CHKSUM

To those of you that are more experienced (than me);
I've now started on a bootloader that will eventually transfer the 14KB program into the FLASH memory.
I'm thinking of breaking the transfer up into 16 or 32 byte frames.
Obviously when the program is finally in the memory every single bit must be correct. So how do you do this?

I can see a few ways of integrity check & error handling:
A: ask for the frame to be sent 3-4 times, and if all are equal then accept it as valid. (slow but safe).
B: checksum validation, resend frame if checksum error. (faster but certain errors may slip trough...unacceptable?)
C: CRC, slightly better than checksum. (fast but certain errors may still slip trough...unacceptable?)
D: error correcting codes like Hamming, Reed-Solomon, and others (somewhat slow and very complex).

I would prefer to go for A and although it is somewhat 'brute force' it is also 100% safe, and most of all it is simple.
Unless you have a better idea?
--
*******************************************
VISIT MY HOME PAGE:
<http://home.online.no/~eikarlse/index.htm>
LAST UPDATED: 23/08/2003
*******************************************
Best Regards
Eirik Karlsen


to unsubscribe, go to http://www.yahoogroups.com and follow the instructions


--- In , "martin de lange" <martin_de_lange@x>
wrote:
> There is only one definate solution I have for you - use crc16
> checksums. We use it all the time in industrial comms in Modbus,
> Can, DF1 and you find it in most Fieldbusses. I use it all the
> time to update flash via these busses and it is 100% reliable. CRC
> is one of the most (if not the most) reliable check sums. All our
> stuff are RTU's in remote areas and we have to have absolute
> reliability and it is not that difficult.

First of all, I agree that CRC is the way to go. But let's be real
here -- it is NOT 100% reliable. There are many types of errors
which a CRC simply will not detect. If it did work 100% then every
download off the internet would be perfect and let's face it, bad
downloads do occure occasionally (although rarely).

If you want the maximum reliability you would go with a MD5 checksum
but it is a much heavier algorithm and I don't think you would want
to do that in a PIC. Even MD5 is not 100% but it is so good that
statistically it is. (The odds of an error that isn't caught is
something on the order of 1 in billions.)


Hi,
Well....I'd like to avoid crc because of its complexity (and I've never used it before).
And I won't even touch MD5 for the same reason.
Apart from this I've got only 2KB memory left for the entire bootloader.
MD5 and CRC tried to get max performance with minimal extra 'formatting', but for downloading
14KB over a 2meter RS232 cable into a pic the speed is of little importance...
I'm willing to wait a few extra sec's.

So how about transmitting a 32byte frame 2-3 times, receiver compares those and if all are equal accept,
else start a new frame transmission.
And what are the odds of getting 1 or 2  'bad bits'.....same bits, same location, in 3 consecutive 32byte frames?
I dunno....must be 1 in fantazillions !
 
 
 

 

If you want the maximum reliability you would go with a MD5 checksum
but it is a much heavier algorithm and I don't think you would want
to do that in a PIC.  Even MD5 is not 100% but it is so good that
statistically it is.  (The odds of an error that isn't caught is
something on the order of 1 in billions.)
 


--
*******************************************
VISIT MY HOME PAGE:
<http://home.online.no/~eikarlse/index.htm>
LAST UPDATED: 23/08/2003
*******************************************
Best Regards
Eirik Karlsen
 


It's no soooooo complex to implement the CRC... Look at www.piclist.com and search there for CRC in the source code archive....
 
Best Regards
 

Mauricio D. Jancic
Janso Desarrollos - Microchip Consultant
www.janso.com.ar
i...@janso.com.ar
(54) - 11 - 4542 - 3519
Lugones 3238 "B" - C1430ECN
Capital Federal
Republica Argentina
(54) - 11 - 4542 - 3519
MSN: j...@hotmail.com

 


From: Eirik Karlsen [mailto:e...@online.no]
Sent: Lunes, 16 de Febrero de 2004 15:04
To: p...@yahoogroups.com
Subject: Re: [piclist] Re: CRC / CHKSUM

Hi,
Well....I'd like to avoid crc because of its complexity (and I've never used it before).
And I won't even touch MD5 for the same reason.
Apart from this I've got only 2KB memory left for the entire bootloader.
MD5 and CRC tried to get max performance with minimal extra 'formatting', but for downloading
14KB over a 2meter RS232 cable into a pic the speed is of little importance...
I'm willing to wait a few extra sec's.

So how about transmitting a 32byte frame 2-3 times, receiver compares those and if all are equal accept,
else start a new frame transmission.
And what are the odds of getting 1 or 2  'bad bits'.....same bits, same location, in 3 consecutive 32byte frames?
I dunno....must be 1 in fantazillions !
 
 
 

 

If you want the maximum reliability you would go with a MD5 checksum
but it is a much heavier algorithm and I don't think you would want
to do that in a PIC.  Even MD5 is not 100% but it is so good that
statistically it is.  (The odds of an error that isn't caught is
something on the order of 1 in billions.)
 


--
*******************************************
VISIT MY HOME PAGE:
<http://home.online.no/~eikarlse/index.htm>
LAST UPDATED: 23/08/2003
*******************************************
Best Regards
Eirik Karlsen
 

to unsubscribe, go to http://www.yahoogroups.com and follow the instructions

--
Incoming mail is certified Virus Free.
Checked by AVG Anti-Virus (http://www.grisoft.com).
Version: 7.0.211 / Virus Database: 261.9.4 - Release Date: 16/02/2004


--
Outgoing mail is certified Virus Free.
Checked by AVG Anti-Virus (http://www.grisoft.com).
Version: 7.0.211 / Virus Database: 261.9.4 - Release Date: 16/02/2004



Eirik Karlsen wrote:

> Hi,
> Well....I'd like to avoid crc because of its complexity (and I've never
used it before).
> And I won't even touch MD5 for the same reason.
> Apart from this I've got only 2KB memory left for the entire bootloader.
> MD5 and CRC tried to get max performance with minimal extra 'formatting',
but for downloading
> 14KB over a 2meter RS232 cable into a pic the speed is of little
importance...
> I'm willing to wait a few extra sec's.
>
> So how about transmitting a 32byte frame 2-3 times, receiver compares
those and if all are equal accept,
> else start a new frame transmission.
> And what are the odds of getting 1 or 2 'bad bits'.....same bits, same
location, in 3 consecutive 32byte frames?
> I dunno....must be 1 in fantazillions !

No, CRC is very very easy. Fast CRC is a little bit more complicated. I can
let you have the source for the simple solution written in XCSB if you would
like (it's only about 10 lines of code). I don't think the fast version
would be worth the overhead of using the required 512 byte table.

Regards
Sergio Masci

http://www.xcprod.com/titan/XCSB - optimising structured PIC BASIC compiler


A checksum simply adds the recieved
bytes together, discarding any overflow.
It won't catch reversed bytes -- but that's
a fairly rare communication hit.

A simple checksum will catch many of the
typical hits you're likely to find in a
short local link. That's why it was so
popular in XModem, and in the Intel
download format.

People use the more robust CRC because it
can catch single-bit hits and reversed
bytes. Plus, implementing
it in hardware is very straightforward.

For your application, having the sending
program calculate an 8-bit checksum for
32 bytes sent, then sending the checksum
so the reciever can verify it, should be
sufficient, and would be really fast compared
to sending the data three times.

--- In , Eirik Karlsen <eikarlse@o...> wrote:
> Hi,
> Well....I'd like to avoid crc because of its complexity (and I've
never used it before).
> And I won't even touch MD5 for the same reason.
> Apart from this I've got only 2KB memory left for the entire
bootloader.
> MD5 and CRC tried to get max performance with minimal
extra 'formatting', but for downloading
> 14KB over a 2meter RS232 cable into a pic the speed is of little
importance...
> I'm willing to wait a few extra sec's.
>
> So how about transmitting a 32byte frame 2-3 times, receiver
compares those and if all are equal accept,
> else start a new frame transmission.
> And what are the odds of getting 1 or 2 'bad bits'.....same bits,
same location, in 3 consecutive 32byte frames?
> I dunno....must be 1 in fantazillions ! >
>
> >
> >
> > If you want the maximum reliability you would go with a MD5
checksum
> > but it is a much heavier algorithm and I don't think you would
want
> > to do that in a PIC. Even MD5 is not 100% but it is so good that
> > statistically it is. (The odds of an error that isn't caught is
> > something on the order of 1 in billions.)
> >
>
> --
> *******************************************
> VISIT MY HOME PAGE:
> <http://home.online.no/~eikarlse/index.htm>
> LAST UPDATED: 23/08/2003
> *******************************************
> Best Regards
> Eirik Karlsen