Minimal but best checksum

Log in or register to post comments
Go To Last Post
15 posts / 0 new
Author
Message
MattBucknall
MattBucknall's picture
Level: Hangaround
Joined: Thu. Feb 14, 2002
Posts: 369 View posts
Location: UK
#1
Posted by MattBucknall: Thu. Dec 3, 2009 - 02:53 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hello,

I'm implementing a simple comms protocol where each packet must be 16 bytes in length.

The 1st byte indicates the packet type which determines the meaning of the following 15 bytes.

I only need 4-bits in the 1st byte to indicate packet type, which leaves 4 spare bits. I'd quite like to use these for some sort of checksum to detect bit errors in the rest of the packet.

What would you guys recommend as the best 4-bit checksum algorithm/CRC polynomial to use (where best = maximum number of bit errors detected)?

Cheers,
Matt.

Tags:

AVR Microcontrollers, megaAVR and tinyAVR
Top
Koshchi
Koshchi's picture
Level: 10k+ Postman
Joined: Wed. Nov 17, 2004
Posts: 15658 View posts
Location: Vancouver, BC
Posted by Koshchi: Thu. Dec 3, 2009 - 03:03 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I don't really see how it would matter much what method you use. With only 4 bits you will always have a 1 in 16 chance that bad data will get through.

Regards,
Steve A.

The Board helps those that help themselves.

Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 101835 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Thu. Dec 3, 2009 - 03:04 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You might as well just sum the bytes and use the lower 4 bits. I guess you could feed it into an 8bit CRC and use just the upper or lower 4 of that but I'm not sure that'll be any more "protective" than a simple 4 bit sum.

What's the transport medium anyway? If a wire you probbaly don't need to protect it - if RF or audio or some other modulated carrier that's susceptible to interference then maybe.

Top
Bronze Markdavid.prentice
david.prentice's picture
Level: 10k+ Postman
Joined: Sat. Feb 12, 2005
Posts: 30659 View posts
Location: Wormshill, England
Posted by david.prentice: Thu. Dec 3, 2009 - 03:04 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

It depends on how reliable your link is. If it is say a telephone modem, then you are going to have some but few errors. A radio link is certain to have errors, possibly many.

For the simple telephone link, use Xmodem with 8bit CRC. You request repeat packets if required.

Alternatively you encode the data and detect and correct errors as they arrive. Google Hamming etc. Any error-correcting encoding method uses extra bits. You may find it is more efficient to send the larger self-correcting packets and never have to negotiate a re-send.

David.

Top
ka7ehk
ka7ehk's picture
Level: 10k+ Postman
Joined: Fri. Nov 22, 2002
Posts: 22030 View posts
Location: Tangent, OR, USA
Posted by ka7ehk: Thu. Dec 3, 2009 - 03:40 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If it is a channel with substantial noise, a checksum of any sorts won't help much. The packet with "...AB.." will have the same sum as "...BA..", for example.

CRCs are the the next best, probably. But, in a packet that size, even just using the low 4 bits of an 8-bit CRC will get you very little (though, maybe more than nothing). You will find a substantial number of possible errors that result in the low 4 bits still being the same. If it was important data, I would use at least an 8 bit CRC appended to the end of the packet.

Jim

 

Until Black Lives Matter, we do not have "All Lives Matter"!

 

 

Top
glitch
glitch's picture
Level: Raving Lunatic
Joined: Sat. Jan 12, 2002
Posts: 8620 View posts
Location: Canada
Posted by glitch: Thu. Dec 3, 2009 - 04:00 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I would go with Jim's suggestion, but instead of just using the low 4 bits, XOR the high 4 bits with the low 4 bits, this way you still get *some* of the benefits of the full 8 bits. [there are also 4&5 bit CRC's which you can use]

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

Top
Koshchi
Koshchi's picture
Level: 10k+ Postman
Joined: Wed. Nov 17, 2004
Posts: 15658 View posts
Location: Vancouver, BC
Posted by Koshchi: Thu. Dec 3, 2009 - 04:20 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
You might as well just sum the bytes and use the lower 4 bits.

You can't do that since there would be absolutely no detection of errors in the upper nibbles. Either do what glitch said, or simply add all 32 nibbles.

Regards,
Steve A.

The Board helps those that help themselves.

Top
Bronze Markbobgardner
bobgardner's picture
Level: 10k+ Postman
Joined: Wed. Sep 4, 2002
Posts: 26609 View posts
Location: Orlando Florida
Posted by bobgardner: Thu. Dec 3, 2009 - 04:23 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

To get error correction, imagine the bits as a matrix, take the parity of each row and col. That will pinpoint the bit that is bad.

Imagecraft compiler user

Top
Koshchi
Koshchi's picture
Level: 10k+ Postman
Joined: Wed. Nov 17, 2004
Posts: 15658 View posts
Location: Vancouver, BC
Posted by Koshchi: Thu. Dec 3, 2009 - 04:26 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

But with 16 bytes, that means 24 bits for the error data. The OP only has 4 bits.

Regards,
Steve A.

The Board helps those that help themselves.

Top
glitch
glitch's picture
Level: Raving Lunatic
Joined: Sat. Jan 12, 2002
Posts: 8620 View posts
Location: Canada
Posted by glitch: Thu. Dec 3, 2009 - 04:26 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

bobgardner wrote:
To get error correction, imagine the bits as a matrix, take the parity of each row and col. That will pinpoint the bit that is bad.

With 4 bits, you won't get error correction, only possible (and weak) detection.

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

Top
MattBucknall
MattBucknall's picture
Level: Hangaround
Joined: Thu. Feb 14, 2002
Posts: 369 View posts
Location: UK
Posted by MattBucknall: Thu. Dec 3, 2009 - 09:02 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks for all the suggestions. The whole thing is for a bit of a botch job really, transmitting over 1-wire + screen in a fairly noisy environment.

The error detection might not be necessary at all, but I figured as I had the bits to spare I may as well implement something. I'll go with an 8-bit CRC and XOR the lower and upper nibbles as that seems about as reliable as I can make things and its better than nothing.

Thanks again.
Matt.

Top
DocJC
DocJC's picture
Level: 10k+ Postman
Joined: Tue. Dec 11, 2007
Posts: 13455 View posts
Location: Cleveland, OH
Posted by DocJC: Thu. Dec 3, 2009 - 09:54 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Any chance to compress some of those data bytes so as to free up a byte or two for a real checksum or CRC?

JC

Top
Bronze Markdavid.prentice
david.prentice's picture
Level: 10k+ Postman
Joined: Sat. Feb 12, 2005
Posts: 30659 View posts
Location: Wormshill, England
Posted by david.prentice: Thu. Dec 3, 2009 - 10:13 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

So if you have a real wire connection, you are in the realm of "occasional glitch".

Do a CRC and resend as necessary. But your screened cable should solve most problems.

David.

Top
MattBucknall
MattBucknall's picture
Level: Hangaround
Joined: Thu. Feb 14, 2002
Posts: 369 View posts
Location: UK
Posted by MattBucknall: Fri. Dec 4, 2009 - 09:14 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Any chance to compress some of those data bytes so as to free up a byte or two for a real checksum or CRC

Nope, unfortunately the other 15 bytes must remain unmodified, so no chance of any compression.
Quote:
Do a CRC and resend as necessary. But your screened cable should solve most problems.

Comms is one-way only, so there is no way to trigger a resend.

Anyway, all sorted now. As I said, this is just a botch. I'm using it to monitor some kit on soak test, so this isn't for production use (I wouldn't let this setup out of the door in a million years!)

Matt.

Top
KKP
KKP's picture
Level: Resident
Joined: Tue. Jun 26, 2001
Posts: 842 View posts
Location: Silkeborg, Denmark
Posted by KKP: Fri. Dec 4, 2009 - 09:53 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

simple additive sums have non-uniform detection ability. If considering a 4 bit sum, two adjacent words getting a bit set will behave differently depending on bit number. 4+4=8, and will be detected, 2+2=4 and equally so. But 8+8=0, and will not be detected.

Thus the way the IP checksum works:
It adds the carry of the sum addition into the sum, thus 8+8=0x10=1+0=1, which will be detected.

The way to compute a 4 bit sum of this type in C is take a suitable integer, in this case a 16 bit integer, and sum all the bytes. The maximum value possible will be 16*255, so it won't overflow. Then fold it into a 4 bit quantity:

while (w>15) w=(w>>4)+(w&15);

This type of code is dramatically better than simple addition when used on a patterned media that tends to fail in one direction (such as flash), and somewhat better with random-direction failures. It won't detect a bit getting set, and another cleared, at 4 bit distance, but nor will simple addition.

As an aside, the ip (addition with carry feedback) sum is really neat because you can compute it using various worth length, block size, and endianness, and you still get the same resulting bit pattern.

/Kasper

Top