Choosing the best CRC

[ricko_uk]

Hi,
I always used either the ones clients asked for or just a CRC-16 I wrote years ago and kept using.

But there are very many CRCs and I was wondering what the logic of choosing one is...?

Thank you

[lapi]

The choice depends on what kinds of errors need to be detected and how long the messages are expected to be. Various kinds of errors and polynomials that detect them are discussed in a wikipedia article on CRC mathematics https://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks. These are discussed in many textbooks on communications, like "Data&Computer Communications" by William Stallings.

The "best" CRC can be chosen, for example, by running simulations of the messages sent over the chosen channel using channel models and the chosen coding, modulation etc. and looking for relative efficiency of detecting errors in the received messages (smallest probability of accepting a message which contains errors) between the candidate  CRC polynomials.

[T3sl4co1l]

You may also simply want to choose the one with hardware support -- many MCUs have a CRC module included.

Tim

[boB]

If you are wanting to connect to an already made system, then just use what is compatible with that system.  Polynomial, etc...

If you are rolling your own system with a microcontroller with built in CRC, then just use that CRC.

boB

[bugnate]

If you want to go down a rabbit hole on this: https://users.ece.cmu.edu/~koopman/crc/

[Siwastaja]

Pick some of the most popular. They are likely popular for a reason.

If worried about the reliability, instead of wasting years of time in the CRC rabbit hole trying to find optimized polynomial for your expected error profile (likely based on wrong assumptions, anyway), just increase the number of bits, for example use CRC32 instead of CRC16.

For example, the assumption that one bit in million is randomly flipped due to electrical noise is most likely incorrect. Actually an EMI failure would cause a burst of flipped bits during some time, or it could flip bits at some constant frequency, and the probability to flipping 0 to 1 is different to flipping 1 to 0. Also in case of synchronous buses like SPI, a clock glitch can shift the whole bitstream by one place.

[rounin]

FWIW I usually use CRC-16-CCITT or CRC32c or the ethernet CRC32. Otherwise I just jump to MD5 or SHA* or something like AES-GCM if i care about more than a single/double bit flip in a short message. (Use CRC-16 for packet framing / stream re-sync, AES-GCM to verify the multi-part firmware image is correct) The Koopman paper is nice to guarantee that eg CRC-16-CCITT is strong enough to detect single bit flips in your 593byte message or whatever.

Hopefully the physical layer has its own checksums too... I second Siwastaja comment that errors usually happen in large bursts. Fun tradeoffs in between packet size, error detection/re-transmission and protocol overhead.

[SiliconWizard]

Pick some of the most popular. They are likely popular for a reason.

If worried about the reliability, instead of wasting years of time in the CRC rabbit hole trying to find optimized polynomial for your expected error profile (likely based on wrong assumptions, anyway), just increase the number of bits, for example use CRC32 instead of CRC16.

Agreed. For some application with strict integrity requirements and a protocol potentially using very large packets, I implemented a CRC-64. Most of the time, a CRC-32 is adequate.
In many cases, a CRC-16 is fine. Even a very simple 8-bit checksum is fine in a number of cases.

For example, the assumption that one bit in million is randomly flipped due to electrical noise is most likely incorrect. Actually an EMI failure would cause a burst of flipped bits during some time, or it could flip bits at some constant frequency, and the probability to flipping 0 to 1 is different to flipping 1 to 0. Also in case of synchronous buses like SPI, a clock glitch can shift the whole bitstream by one place.

Agreed. All in all, the probability, in real life under reasonable conditions, that even a small CRC will be identical for two different messages is pretty low.
If you're working on some aerospace project, you may want to spend a little more time on this. Otherwise...

[Siwastaja]

Also it makes a huge difference whether you are checksumming against regular errors in unreliable link, or protecting against that one super rare occurrence. Checksumming an on-board 1-inch long MCU-to-MCU UART link (with properly designed layout and protection, passed EMC testing) is an example of latter; usual practice is no checksumming at all. Single error may happen once a 10000 years so it would be just extremely bad luck if it passed through CRC8 undetected.

And then again if you have megabytes long packets over a noisy optical link, CRC16 may be utterly inadequate.

[ricko_uk]

Thank you all for the detailed feedback!

In this case both micros are on the same PCB and the link is an SPI, with traces 120 mm (12 cm) long on a 4-layers PCB. The longest message is 96 bytes and the speed is up to 9 Mbits (at most - I can decrease it to half).

Based on the above feedback it sounds like a CRC-16 is plenty enough and probably even not needed. Correct?

Thank you as always!

[ajb]

Based on the above feedback it sounds like a CRC-16 is plenty enough and probably even not needed. Correct?

Well, probably, but not necessarily.  Is that PCB in a box that lives in a pretty friendly electromagnetic environment where an error in an SPI message will at worst cause the device to crash and reset?  Or is that PCB controlling the power stage of a 50kW variable frequency drive that will be used in a factory next to a whole fleet of arc welding equipment?

[SiliconWizard]

As a quick additional note, CRC or any other means of checking data integrity is not useful only for hardware-related mishaps/noise. Even if signal integrity is totally guaranteed, they are a useful tool for mitigating software bugs as well!

[ricko_uk]

Thank you SiliconWizzard and Ajb.

@SiliconWizzard, not sure I understand how that would be (unless the software bug is in the CRC calculation). Could you please explain it a little more?

@Ajb, yes, I forgot to mention that the PCB is well shielded and also in a very quiet environment.

Thank you

[ajb]

A CRC (or any message integrity check) will tend to catch errors in how messages are relayed between the software and the wire, so things like pointers to buffers being off-by-one, or a missed IRQ that skips words out of the message, or problems with framing that cause parts of two sequential messages to be interpreted as one message.  It will also catch buffers getting mangled, for example by rogue pointers. 

[ricko_uk]

Thank you Ajb

[SiliconWizard]

Yes, any bug that would yield an ill-formed packet, really. Possibilities are almost endless.

One "extreme" case I like to consider is a packet containing "random" data. You don't want random data to ever be accepted as a valid packet. (At least make this a very low probability...) One way I like to test the receiving end of comm protocol handlers is to send a certain amount of random data for a certain time, and check that 1/ it doesn't take as valid any invalid packet and 2/ it remains in a working state - meaning that any valid packet that would be sent after this "torture" period would still be correctly interpreted.

For this to be robust, a CRC may not be enough. You may additionally need things like synchronization words at the start of the packet header.

[ricko_uk]

Thank you SiliconWizard,
the very first character is just the command, and I am resetting the state machine after a timeout (or error). Sot he structure is this:
- command
- payload length
- payload
- CRC

Are you suggesting that to make it more robust I also add a sync character at the front like this:
- sync
- command
- payload length
- payload
- CRC
or something else?

The above would make it a little easier to parse. But why would that make it much more robust than just the CRC?

Thank you

[T3sl4co1l]

Note that, reserving an entire value (as a stateless start byte) means you need to escape that value anywhere in your payload, annoying for binary data.  If you ignore it during a payload, then you're susceptible to erroneous payload length values and packet lengths.

(I'm not sure if that's what you had in mind.)

Sync could also be like a TCP sequence value, which always increments (or whatever) from packet to packet, rejecting unexpected values.  With enough bits, it's extremely unlikely that random trash is received as valid data.  Though the data itself can also get rejected, or out of sync, so you need everything else TCP has: open, close, SYN/ACK, request data again, etc.

Which, is certainly something you can do, just slap TCP on top of a serial port, I forget what that's called but it's well enough known, back when that was a thing.

Also not sure if that's what they meant or not... I'm no expert on networking, I avoid it when I can...

Tim

[bill_c]

If you do decide to use some form of sync, you may want to look at COBS https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing

[rounin]

Note that, reserving an entire value (as a stateless start byte) means you need to escape that value anywhere in your payload, annoying for binary data.  If you ignore it during a payload, then you're susceptible to erroneous payload length values and packet lengths.

I use two CRCs to avoid this, one on the header and one on the payload. It seems to work well enough without any byte stuffing / data escaping. Also means you can do less CRC cycles before noticing the stream is de-synced. (Its not guaranteed to be proof of de-sync like it would be if you byte stuff, but it survives fairly aggressive fuzzing tests).

eg

- sync
- command
- payload length
- header CRC
- payload
- payload CRC

[mikerj]

Something I've done with a master/slave SPI comms is to have the slave transmit the status of the previous command along with a frame counter whilst it's receiving the next command. This gives no additional comms overhead on the bus and allows the master to check is any frames have been missed.

[voltsandjolts]

If you do decide to use some form of sync, you may want to look at COBS https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing

...and adding to that, here is an example of COBS framed serial packets with CRC16:
https://www.eevblog.com/forum/microcontrollers/implementing-uart-data-packets-with-consistent-overhead-byte-stuffing-(cobs)/

[Siwastaja]

Sync can be one of the commands. Being a fixed-length command, you can even precalculate the whole thing, including sync cmd, payload length (likely 0 or whatever, you may want to add magic numbers there), and the CRC, making detection easier.

[NorthGuy]

The above would make it a little easier to parse. But why would that make it much more robust than just the CRC?

Sync is much more important than CRC. Imagine someone unplugs the cable in the middle of the packet. When the cable re-connects you will think that you're in the middle of the packet while the transmitter is already transmitting a new packet.

If you don't have sync, you may lose the place where packets start and you may never be able to go back. With the sync, it's very easy to do. If you encounter sync in the middle of the packet, you just dismiss the beginning and start over - this puts you in sync again.

If you transfer ASCII data, reserve a number of characters to control transmission, or even reserve the the MS bit for control - if bit 7 is set, you know this is something special - a sync or a command.

If you transfer 8-bit data, you need to make sure that the sync never occurs in the middle of the packet, such as by using escape characters, or by using longer characters - e.g. 9-bit.

[voltsandjolts]

That's where COBS is great, you don't have to think about frame / sync anymore.
Just pass it any arbitrary data you like and let the COBS encoder/decoder deal with it.

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