Author Topic: Choosing the best CRC  (Read 2259 times)

0 Members and 1 Guest are viewing this topic.

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 6864
  • Country: fr
Re: Choosing the best CRC
« Reply #25 on: June 09, 2021, 04:54:49 pm »
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.
« Last Edit: June 09, 2021, 04:59:51 pm by SiliconWizard »
 

Offline ricko_uk

  • Frequent Contributor
  • **
  • Posts: 717
  • Country: gb
Re: Choosing the best CRC
« Reply #26 on: June 09, 2021, 05:37:34 pm »
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
« Last Edit: June 09, 2021, 05:51:22 pm by ricko_uk »
 

Offline voltsandjolts

  • Supporter
  • ****
  • Posts: 1184
  • Country: gb
Re: Choosing the best CRC
« Reply #27 on: June 10, 2021, 08:32:25 am »
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.
 

Offline T3sl4co1l

  • Super Contributor
  • ***
  • Posts: 17390
  • Country: us
  • Expert, Analog Electronics, PCB Layout, EMC
    • Seven Transistor Labs
Re: Choosing the best CRC
« Reply #28 on: June 10, 2021, 02:53:04 pm »
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
Seven Transistor Labs, LLC
Electronic design, from concept to prototype.
Bringing a project to life?  Send me a message!
 

Offline ricko_uk

  • Frequent Contributor
  • **
  • Posts: 717
  • Country: gb
Re: Choosing the best CRC
« Reply #29 on: June 10, 2021, 06:28:15 pm »
Thank you Tim and voltsandjolts :)
 

Offline peter-h

  • Frequent Contributor
  • **
  • Posts: 746
  • Country: gb
  • Doing electronics since the 1960s...
Re: Choosing the best CRC
« Reply #30 on: June 10, 2021, 08:42:36 pm »
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.


« Last Edit: June 10, 2021, 08:44:10 pm by peter-h »
Z80 Z180 Z280 Z8 S8 8031 8051 H8/300 H8/500 90S1200 32F417
 

Offline ricko_uk

  • Frequent Contributor
  • **
  • Posts: 717
  • Country: gb
Re: Choosing the best CRC
« Reply #31 on: June 10, 2021, 10:27:16 pm »
Thank you Peter :)
 

Online bson

  • Supporter
  • ****
  • Posts: 1931
  • Country: us
Re: Choosing the best CRC
« Reply #32 on: July 01, 2021, 09:46:07 pm »
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:



« Last Edit: July 02, 2021, 03:30:10 am by bson »
 

Offline ricko_uk

  • Frequent Contributor
  • **
  • Posts: 717
  • Country: gb
Re: Choosing the best CRC
« Reply #33 on: July 01, 2021, 11:46:52 pm »
Thank you Bson :)
 

Offline peter-h

  • Frequent Contributor
  • **
  • Posts: 746
  • Country: gb
  • Doing electronics since the 1960s...
Re: Choosing the best CRC
« Reply #34 on: July 02, 2021, 07:54:24 am »
"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.
Z80 Z180 Z280 Z8 S8 8031 8051 H8/300 H8/500 90S1200 32F417
 

Offline Siwastaja

  • Super Contributor
  • ***
  • Posts: 4079
  • Country: fi
Re: Choosing the best CRC
« Reply #35 on: July 02, 2021, 01:58:29 pm »
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.
« Last Edit: July 02, 2021, 02:02:04 pm by Siwastaja »
 
The following users thanked this post: voltsandjolts

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 6864
  • Country: fr
Re: Choosing the best CRC
« Reply #36 on: July 02, 2021, 05:01:57 pm »
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.
 

Online bson

  • Supporter
  • ****
  • Posts: 1931
  • Country: us
Re: Choosing the best CRC
« Reply #37 on: July 02, 2021, 10:11:32 pm »
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.
« Last Edit: July 02, 2021, 10:13:16 pm by bson »
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf