Minimal but best checksum

Go To Last Post
15 posts / 0 new
Author
Message
#1
  • 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.

  • 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.

  • 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.

  • 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.

  • 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"!

 

 

  • 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.

  • 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.

  • 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

  • 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.

  • 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.

  • 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.

  • 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

  • 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.

  • 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.

  • 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