serial (5)

Using and Misusing CRCs

CRCs are used for error detection in communication systems and storage systems. They have a combination of several advantageous properties whilst only requiring a short FCS, but they do have their limitations. If you require error correction as well as detection then you have to look at a different class of algorithms and will have to add much more redundancy to the codeword. The rest of this post is about message systems, where if an error is detected, the link layer of the protocol will take various actions such as discarding the message, sending a NACK, requesting a retry, waiting for retry until a timeout occurs etc. Another use of CRCs is for protecting data in memory, where similar considerations apply but the corruption possibilities may be different so you have to consider if the single random bit-flips model is still appropriate. If you just need to protect a single 8, 16 or 32 bit value, choose from this list and use a non-zero seed. Unless your protocol design is such that the messages are fixed length, one of the fields in the message will be the message length or an equivalent which points to the position of the FCS.

Continue reading...

Choosing an Optimal CRC Polynomial

Most of the time engineers just have to implement communications protocols that are given to them: industry standards, decided by committees or established by the dominant players. But surprisingly often there is the opportunity to create a new protocol, either for proprietary internal use or as part of inventing a new standard for the industry, and in those cases we have to choose a CRC polynomial. Although the process sounds complicated, in many cases it can be quite simple. But first we must make sure we don't fall into one of the common pitfalls which leads to sub-optimal performance. Be wary of the many excuses for using a standard CRC Before you go ahead with a standard polynomial know that it is not the only choice and may well not be the best choice. What you are doing by choosing a standard one is saying don't blame me, everyone uses this. As it says on mathpages.com if you use a standard polynomial and subsequently it turns out to be particularly unsuitable for your circumstances, "This would be incredibly bad luck, but if it ever happened, you'd like to at least be able to say you were using an industry standard…

Continue reading...

You Are Probably Using A Sub-Optimal CRC

The designers of serial protocols like USB, Ethernet, CAN, or anything using "CRC-8" or "CRC-16 CCITT" did not have access to information on which CRC polynomials are the best for their bit-size and application, so were chosen on what seemed to be reasonable grounds but are now known to be sub-optimal. It is not necessarily that better polynomials were unknown in academic research but that the information had not reached an industrial design audience. In fact, it was widely believed that the performance of the polynomials was similar enough that you could just randomly pick one from a list in a book and it would be fine for your application. Koopman said CRCs have been around for a really long time. You would think that after all these years, the best CRC is a well solved problem. Unfortunately, it isn't really.... Until fairly recently, the compute power wasn't available to do an exhaustive search. ... The other problem is that the literature is poorly accessible to computer engineers, a lot of it is written in dense math that's hard to apply ... So as a result, practitioners mostly use what someone else used and they assume it's good and that…

Continue reading...

Hitting the Precision Limit of Excel; or 15 Digits Should be Enough for Everyone

Excel is a great all purpose tool, used by maybe 7% of the world's population. From shopping lists to budgets, Gantt charts and calendars to circuit simulators and digital music workstations, it can do it all. It is so good at so many things and so universally available to businesses that in many cases the biggest competition for software startups is not other specialized software solving the same problems but Excel. When it comes to using Excel for engineering tasks, there are lots of known pitfalls. Treating values as dates, or strings which are supposed to be hex like "51E67" as scientific format is one big category of pitfalls. Another is that although the probability of an error in any one cell is small, when you have a high number of cells all dependent on each other, the probability of error somewhere in the sheet means that the final result is likely to be wrong. The canonical case study is Reinhart and Rogoff, covered by a talk I highly recommend, Emery Berger's "Saving the World from Spreadsheets". So cross checking or auditing become necessary. Use CTRL-` to switch between formula view and value view. In common with many computer languages,…

Continue reading...

Sampling a Pulse Stream Mid Bit When the Clock Frequency Varies

When faced with the task of reading in an asynchronous bit stream (i.e. one without a separate clock pulse line), the best solution is to use an onchip UART peripheral. However, there are many cases where it isn't possible to use a UART, for example: The micro has no UARTS, or the ones it has are already used.The pin can't be assigned to UART receive function - simpler micros have fixed pin functions; even in more complex micros not all pins can be mapped to any function.The base clock doesn't allow for the right UART clock rate with any of the possible divider options.The bit stream doesn't correspond to UART format, for example - more than 9 data bits, Manchester encoding, non-standard number of start and stop bits.The bit stream has a wide variation in pulse width which is outside the UART capabilities (typically 2.2%)In these cases, the usual approach is to use an edge triggered interrupt to start a timer, measure the start bit, and then use the timer to sample in the middle of all subsequent bits. The success of this approach depends on the variation in the pulse widths and the number of bits in one frame.

Continue reading...