Simple but reliable checksum for small controllers

Tilmann

Something like a Fletcher checksum is quick to calculate and better than a "plain" checksum.

Andrew

Andrew Jackson schrieb:

Fletcher (16 or perhaps 32 bit) sounds really good, I didn't knew this method before.

Thanks, Tilmann

Op Mon, 09 Jun 2008 09:38:12 +0200 schreef Tilmann Reh :

A compromise might be possible here: if you have enough RAM, you could calculate the table first and then use it from RAM.

A description in German is in the journal of FORTH e.V. 2004/4:

But the code is obviously not in C.

MfG JRD

Rafael Deliano schrieb:

The (english) Wikipedia page has sample code in C, which seems pretty straightforward for an implementation in assembler.

Thanks though, Tilmann

Boudewijn Dijkstra schrieb:

Those small micros also lack large RAM unfortunately... :-\

But I think Fletcher looks like the perfect solution.

Thanks, Tilmann

CRC is the most reliable method for a given number of check bits.

You don't have to compute CRC as one byte at a time; you can compute it in 4 bit chunks. In this case, the table has only 16 entries. So the table can fit into the internal RAM of x51 and addressed by @Ri. This results in the very fast and efficient implementation.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

Vladimir Vassilevsky schrieb:

I would like to see a direct comparison between CRC and Fletcher... (The Wikipedia article references an article at the IEEE, but that doesn't seem to be publicly available.)

I have done CRC by nibbles in another project already, but I didn't yet think of moving the table to RAM - this is a good idea. Maybe I will compare these two implementations (CRC 4-bit-wise with table in RAM vs. Fletcher) and pick the "better".

From my first impression, Fletcher will be somewhat faster due to the very simple arithmetics. For the given purpose, it might be the optimum.

Thanks, Tilmann

CRC is the perfect code with the guaranteed properties. No other code can perform better. For the small amount of random errors (~1%), the probability of the undetected error with CRC is orders of magnitude less then that of a checksum.

Very well could be. It is quite unlikely that the flash memory will be corrupt; the simple one byte checksum could be sufficient to detect that.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

You can calculate a in line coded CRC on a SiLabs 8051 in 36 clocks per byte (not counting the loop and memory access instructions). Using a 24 MHz clock, this comes to 1.5 usec per byte. The advantage of the CRC is also its biggest disadvantage: It is sensitive to every bit and its position. Setting the value over an entire block of memory requires some attention to detail.

The old HP Journal (now I am dating myself) had a great article on finding the best function to use in Signature Analysis. Turns out the SDLC CRC was better at this than most. To find lean code examples, search for SLDC, HDLC, or AHDLC CRC routines.

Blakely

The two different checksum schemes we use in check code generated by our compilers is a simple byte by byte sum mod 256 that results in 0. Compiler/linker creates a one byte pad byte that it sets in the generated code.

The second check that some of our tools use is a polynomial similar to a CRC. The actual polynomial varies somewhat because some silicon autochecks executable code with spare processor cycles.

Regards

-- Walter Banks, President Byte Craft Limited Tel. (519) 888-6911

If the 16 bit CRC is calculated with the CRC-CCITT polynomial, it can be calculated in 4 bit chunks pretty easily even without a table, as there are no taps nearer each other than 4 bits in the equivalent shift register implementation. This means that there are no feed-around bits in a 4 bit calculation.

The CRC-16 polynomial (used commonly in BISYNC communication and on disks) is a different beast, as there arre two taps beside each other.

You first need to be clear on what you are trying to accomplish.

In classic coding theory, a "codeword" is data with a checksum of some kind appended.

The Hamming distance of the code is the minimum number of bits that you need to flip to go from one codeword to another.

It isn't practical for 8-bit microcontrollers to use a code with a large Hamming distance. The key question, since generally a Hamming distance of only 2 is achieved, is how well the [minimum] Hamming distance lines up with probable data errors, introduced both by semiconductor defects and software errors.

One code that has worked well for us is to use a 16-bit quantity and to repeatedly roll left and XOR the next byte into the lowest 8-bits.

This type of code has the following properties:

a)No single byte error will create an undetectable corruption.

b)If two bit errors were to occur in the same position, they would have to be in bytes a multiple of 16 locations apart (improbable--the most common would be adjacent bytes).

c)It is cheap.

Additionally, it is cheap to implement if one notes that bytes spaced 16 locations apart are in an equivalence class--one can form this type of checksum with only 16 total left shifts, i.e.

UINT16 checksum = 0; int i, address;

for (i=0; i

Vladimir Vassilevsky schrieb:

Most probably a simple checksum would be sufficient - but if possible without too much effort, I prefer to use a "better" checksum. :-)

Tilmann

Tauno Voipio schrieb:

Thanks for that comment - I didn't realize this interesting difference between the two polynomials yet. Maybe the CCITT polynomial also is a method worth thinking about...

Tilmann

I might find the 8086 assembly code module for CRC-CCITT in 4 bit chunks. It should be somewhere in the old backup CD's.

David T. Ashley schrieb:

This seems similar to the one I mentioned.

It's probably one of the cheapest at all. :-)

I will consider this as well as Fletcher and CRC16 (CCITT flavour). They all will be reliable enough for the given purpose, but it will be interesting to compare the computing times...

Tilmann

I use the Fletcher checksum. It is standard (RFC 1146) and very efficient on 8-bits micros. Here is the code I use:

#include /* 8-bit Fletcher checksum (See RFC 1146). */ /* Adler-32 checksum is better but much slower on small uP's */ /* Assumes Big-endianness */ /* Returns A in MSB, B in LSB */

unsigned short fletcher8( unsigned char *data, size_t length ) { #if STANDARD_FLETCHER_CHECKSUM unsigned char A =3D 0x00; unsigned char B =3D 0x00; #else /* Algo enhanced for null-beginning files */ unsigned char A =3D 0xA5; unsigned char B =3D 0x5A; #endif while( length-- ) { A +=3D *data++; B +=3D A; } return ( A

Tauno Voipio schrieb:

I would appreciate it.

Many thanks, Tilmann