Choosing the best CRC

[SiliconWizard]

And with all that said about sync, depending on your exact protocol and application, a time-out, as you mentioned, may be adequate.

There are cases though - such as "continuous" packet streaming - for which it's not necessarily an adequate solution.

One way of making a simple time-out scheme, without sync, work reasonably well is to implement a protocol in which every packet sent must be acknowledged by the receiving end. So, actually both communication ends do implement a time-out. That may be too much overhead for some applications though. But I've used that quite often.

Either way, as I - and others - have mentioned, this is always a good idea to actually test the robustness of your communication scheme using some kind of "torture" tests. Don't wait until something goes wrong in the field by pure chance to see how robust your implementation is.

[ricko_uk]

Thank you all for the feedback and suggestions! Very much appreciated!

With COBS, I assume the idea is to encode the entire message including the payload, before sending it. Which means that I would then have to wait for the entire message to be received before decoding it and find out if there were any errors. Is that correct?

Thank you

[voltsandjolts]

With COBS, I assume the idea is to encode the entire message including the payload, before sending it.

That would be the simplest way.
For very long messages where that method would require too much RAM, the COBS encoding can be done with a 300-ish byte ring buffer, so transmitting can begin while encoding is ongoing.

Which means that I would then have to wait for the entire message to be received before decoding it and find out if there were any errors. Is that correct?

Yes, but that is true for any packet format, not just COBS.
You need to receive the whole packet before you can calculate and test the CRC, ensuring integrity of the packet data.
That might influence your choice of packet length.

[T3sl4co1l]

Well, you can stream the bytes into an iterated CRC, assuming you're consuming the data (for purpose) in the same manner as well; if not, you have to buffer it anyway.

Tim

[ricko_uk]

Thank you Tim and voltsandjolts

[peter-h]

I've just spent a load of time on this stuff...

A couple of useful sites:
https://www.lammertbies.nl/comm/info/crc-calculation and
https://reveng.sourceforge.io/crc-catalogue/16.htm

I also had some old CRC code, labelled CCITT but actually it turns out to be nothing like the CCITT ones in the above links. And I suspect there is a lot of this around...

I doubt that, for a given CRC size, different CRCs offer widely differing reliability, especially as most of the time one has little idea of the sort of corruption to be expected. Obviously, there is a chance of a CRC being "right" accidentally, for any random data. In the 1980s, before ethernet became (relatively) cheap to implement, I designed a token ring LAN (for the interconnection of a printer/plotter sharing product called a Multibuffer). This used an 85C30, in SDLC mode, with the SDLC 16-bit CRC (and a Z180 with some dual-port RAM, etc). A totally standalone LAN card, with a nice simple API, much easier to use than an ethernet controller, and a ~2mbps data rate. MIL-STD-1553 physical layer, transformer isolated. To test the reliability I built a pulse generator which would corrupt some portion of a packet. And sure enough, running this over several days, with error counters etc, I was getting close to 1/64k probability of a good CRC on a duff packet. This rate could be vastly reduced by simple measures e.g. a checksum would bring it down to 1/(64k*256). And in reality one would also do sanity checks on stuff like addresses...

In any system which uses CRCs, you are likely to need to implement the higher layers. For example a packet not acked may have been received well; it was just the ack packet which got lost. Lots of permutations of this stuff... To avoid sending the same packet twice in this situation, you have to implement a serial number in the packet. And that serial number has to be "sensible" in relation to ones seen before it, so again you are getting more sanity checks.

Regarding decoding on the fly, in many products where you don't have a lot of power but need to do CPU intensive stuff (e.g. floats, esp. double) it is normal to decode the data speculatively and prepare the response (or whatever action) on the assumption that the CRC will be good.

[ricko_uk]

Thank you Peter

[bson]

The size of the CRC determines the burst error length it can detect.  A 16-bit CRC for example detects up to 16-bit error bursts.  A 32-bit up to 32 bits.  In addition, for data communications you want a non-burst like initializer, so avoid 0x0000.  That's because a lost signal that looks like all zeros will have a CRC of zero and becomes undetectable.  0xffff is slightly better, but the best is to use some non-repeating bit pattern that's unlikely to be the result of interference (or rather, no more likely than any other pattern).  So, 0xf0f0 is bad, as if 0x5555 or 0xaaaa. Other than that, there are many good initializers, but it's a bit of an arcane art to choose one for an application.  Not to mention the polynomial itself! For a selection, check out https://users.ece.cmu.edu/~koopman/crc/

Here are two EXCELLENT introductions to CRCs and their implementation for electrical engineers:

[ricko_uk]

Thank you Bson

[peter-h]

"A 16-bit CRC for example detects up to 16-bit error bursts.  A 32-bit up to 32 bits."

Surely that is not true.

[Siwastaja]

No, it's not true indeed. Maybe with some badly chosen polynomial. In reality CRCs are much better than that. Also the point about initializers is some made up mumbo jumbo so basically that post was based on misconceptions alone.

Choice of the polynomial itself is critical, use one of the widely used and tested unless sure about what you are doing.

All ones or all zeroes are the most typical initializers in the real world.

[SiliconWizard]

Agreed.

If there's a topic with a lot of misconceptions, that's CRCs. Even seasoned engineers often have misconceptions about them.

But, like many engineering activities, one common approach is to reuse something that is industry-standard in some context, and apply it to your context which looks the most similar. It's a bit like reusing nuts and bolts. You're not going to reinvent them every time you need some, except for very particular cases, or if it's your main job. This is often where pure science and engineering differ.

[bson]

Any burst larger than the polynomial can produce an error that divides by the polynomial.  For an error smaller than the polynomial it's guaranteed not to divide (obviously).  For a burst larger than the polynomial bit size the probability is inversely proportional to the polynomial itself.