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.