Those of us that have been working in this field for a long time are referred to as ‘experienced’. Experienced is taken to mean that we have been doing this for long enough that we have experienced many of the problems common to embedded systems and thus know how to solve them. Although this is true for many things, I think there is a downside to it – namely that because we’ve successfully solved a particular problem a number of times that we fall into the trap of thinking that our solution is optimal. In order to guard against this it is essential to be proactive in seeking out new solutions to old problems. To illustrate my point, I’ll take you on an abbreviated trip through the memory lane of my career when it comes to that most prosaic of problems – transmitting serial data between microcontrollers.
Back when I was a lad I was by definition naive and so I just transmitted the data without any thought to how to detect errors beyond the use of a parity bit on each byte. Well it didn’t take me long to work out that a simple parity bit wasn’t exactly a robust way of detecting errors, and so I started appending a simple additive checksum to the message.
Well that worked for a while until the day it dawned on me that an additive checksum without an initial seed value was vulnerable to a stuck channel (e.g. all zeros). From that day on I started seeding my checksum computations with initial values. I tended to favour 0x2B (with apologies to Hamlet).
Somewhere along the road I switched from performing an additive checksum to using an XOR operation. I can’t remember why I did this – but it just seemed ‘better’.
This approach served me well for many years until I started investigating cyclic redundancy checks (CRC). I’d known about CRC’s for a long time of course. However all the ones I knew about used 16 or 32 bit values and had certain wondrous but rather unspecified properties for detecting certain classes of errors. To put it bluntly they seemed like complete overkill for sending a short message between two microprocessors – and so I didn’t entertain them. However this all changed the day I came across an 8 bit CRC. This changed my perspective dramatically. An 8 bit CRC designed for protecting small messages – excellent! Thus henceforth I eschewed the use of an LRC and instead opted for an 8 bit CRC to protect my messages.
Well this continued for a number of years. I learned more about CRCs, I got older until one day I decided to ask myself the question – is the 8 bit CRC I am using optimal? For regular readers of this blog, you’ll probably have noticed that ‘optimal solutions’ is a recurring theme. Anyway, with this thought in mind, I set off on a hunt to determine whether in fact the 8 bit CRC I was using to protect small messages was indeed optimal. That’s when I came across this paper by Koopman and Chakravarty. It’s entitled ‘Cyclic Redundancy Code (CRC) Polynomial Selection for Embedded Networks’. It’s a highly readable and informative paper. They essentially investigate what constitutes ‘optimal’ for a CRC polynomial and then exhaustively explore optimal polynomials for different data lengths and different polynomial lengths. Most interestingly they slay some sacred cows along the way, including the popular CRC-8 polynomial (x8+x7+x6+x4+x1+1).
Having read the paper, I discovered that the CRC I was using (the so called ATM-8 polynomial(x8+x2+x1+1)) wasn’t bad for my application – but it wasn’t optimal. Upon reflection this was hardly surprising since I had essentially selected it on the basis that it was designed for a similar application to mine – and thus must be decent. However as Koopman shows – this can be a very foolhardy assumption. I just got lucky.
More importantly from my perspective is that using Koopman’s paper I now have a logical methodology for determining the optimal CRC for any application. Thus after close to 30 years of doing this I think I’m finally homing in on the truly optimal solution to this problem.
Of course, the larger lesson to be learned here is that just because you have done something a certain way for many years means nothing unless you know that it is the optimal way of doing it. That’s when you are truly ‘experienced’.
Home
Adn then someone with far more experience then you comes along and shows you you're still wrong:http://embeddedstories.wordpress.com/2009/06/11/the-story-of-the-week-how-not-to-brag-about-your-accomplishments/Well, that happens to me, of course I still cannot be called experienced, but I'm getting there 😉