Anyone want to do a term paper on CRCs?

Do you know any Math Majors that need a subject for a term paper?

The Embedded System community needs one written on CRCs that is practical rather than pedagogical like the texts books that address the subject. Here is a sample paper.

Resulting paper should have practical answers that people in embedded systems land like myself can understand and use. Reading Polynomials over Galois Fields tend to makes my eyes glaze over. My speed of Mathematics is more that of Trachtenberg Speed System of Basic Mathematics.

What brought this on today is the new Atmel XMega processor that I'm designing with, that uses the CRC polyonmial: x^24 + 4x^3 + 3x +1. That polynomial does not seem to be any of the standard ones, so what are its error detection properties?

Polynomial's have to have certain properties, while they may all be primes, not all primes make good CRC's. For example the properties that make good CRC polynomials will make a very bad random number generator, and vice-versa. Both are done with multi-tap shift registers. CRC generators do NOT generate maximal-length sequences. In fact, the polynomials are deliberately chosen to be reducible by the factor X + 1, because that happens to eliminate all odd-bit errors. -- Embedded Systems Programming Jan/1992 Jack Crenshaw. I admittedly have never understood why the "good ones" are the good ones. More of the math vs get the work done.

For some background take a look at these papers:

• The Great CRC Mystery by Terry Ritter.
• A Painless Guide to CRC Error Detection Algorithms.
• Efficient CRC calculation with minimal memory footprint By Yaniv Sapir and Yosef Stein.
• Slow and Steady Never Lost the Race by Michael Barr.
• Accelerating algorithms in hardware By Lara Simsic.
• Boost CRC Library.
• Several others.

I know that CRC is good only over a certain block length, but what is that block length? The syndrome length? Syndrome length-1?

One article stated "a 16 bit CRC is good for 4K bits minus one"; I have not figure out how that works out, so I question its accuracy.

I want to CRC my code in Flash, however I don't want to use a 16 bit CRC if I really should be using a 32 bit CRC. I know the odds of this making any real difference is minuscule, but never want to give those Lawyers an opening.

Andrew Tannenbaum, in Computer Networks is often quoted talking about 16 bit CRC being "99.9998%" good at detecting.... but how do you calculate these percentages for CRC's of various length and more importantly the polynomial in use?

Since we are doing polynomial division and the CRC is the residue of that division there will be many CRC's that have the same answer, which is not what you want. This is why longer CRC's are better over longer bit runs.

From Tannenbaum, in Computer Networks:

• Detect all single bit errors.
• Detect all occurrences of two single-bit errors for frames less than 2n-1 bits in length.
• Detect all odd number of bits errors.
• Detect all burst errors with a length less the n.
• Detect all but 1/2n-1 burst errors of length n + 1.
• Detect all but 1/2n other errors.

Where n = number of bits in CRC.

See also Algebraic Codes for Data Transmission, Cambridge University Press, 2002.

I've spent several years looking actually for some of these CRC answers, even in real books such as Algebraic Codes for Data Transmission, Cambridge University Press, 2002. The books that I have found are already written for people that understand the math, rather than people like me that just want to get the job done, and want to cite a reference in the source code.

My random CRC crib notes collected over many years:

• "Cyclic code for error detection" by W. Peterson and D. Brown, Proc. IRE, Vol 49, P 228, Jan 1961. This is the oldest reference to CRC I could find, and the most obtuse as far as 'getting the work done vs math'.
• "Error Correcting Codes" W. Peterson, Cambridge, MA MIT PRess 1961.
• Tannenbaum, Andrew. Computer Networks, 128-32. Englewood Cliffs, NJ Prentice-Hall 1981.
• "Technical Aspects of Data Communications", by McNamara, John E. Digital Press. Bedford, Mass. 1982
• Ramabadran T.V., Gaitonde S.S., A tutorial on CRC computations, IEEE Micro, Aug 1988.
• Advanced Data Communication Control Procedure (ADCCP). Federal Register / Vol. 47, No. 105 / Tuesday, June 1, 1982 / Notices
• CRC-32 (USA) IEEE-802: Polynomial $04C11DB7: X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X +1
• $DEBB20E3: PKZIP
• CRC-CCITT V.41 Polynomial $1021 X16 + X12 + X5 + 1
• "CRC generators do NOT generate maximal-length sequences. In fact, the polynomials are deliberately chosen to be reducible by the factor X + 1, because that happens to eliminate all odd-bit errors." -- Embedded Systems Programming Jan/1992 Jack Crenshaw

• 16-Bit CRC can detect:
• 100% of all single-bit errors
• 100% of all two-bit errors
• 100% of all odd numbers of errors
• 100% of all burst errors less than 17 bits wide
• 99.9969% of all bursts 17 bits wide
• 99.9985% of all burst wider than 17 bits (the same as the checksum)

All burst errors of 16 or fewer bits in length and all double-bit errors separated by fewer than 65,536 bits (or 8192 bytes). Dr. Dobb's Journal, May 1992 Fletcher's Checksum by John Kodis.

For $1021:
"T" $1B26
"THE" $7D8D
"THE,QUICK,BROWN,FOX,01234579" $7DC5

Byte-wise CRC Without a table, Crenshaw 1992 [This is the one I use the most, because it fits in 2K parts, where I rewrote it in C, and AVR ASM.]

B:Byte
CRC:16 Bit unsigned

B := B XOR LO(CRC);
B := B XOR (B SHL 4);
CRC := (CRC SHR 8) XOR (B SHL 8) XOR (B SHL 3) XOR (B SHR 4);

Build Table:

I:Index 0->255
Z:Byte

Z := I XOR (I SHL 4);
Table[I] := (Z SHL 8) XOR (Z SHL 3) XOR (Z SHR 4);

Update CRC using Table:
CRC := (CRC SHR 8) XOR Table[ Data XOR (LO(CRC) ];

"Calculating CRCs by Bits and Bytes" by Greg Morse; Byte Magazine September 1986.

CRC is ones complimented, then transmitted least significant byte first. The resulting magic number via a quirk of polynomial syndromes will always be $F0B8 if there where no errors. [No math book I've read has even mentioned it, let a alone explain it, but it is what I look for in all of my CRC code for "good" vs "bad" blocks.]

T = Dx XOR Rx
U =     T7 T6 T6 T4
XOR T3 T2 T1 T0

CRChi = R15 R14 R13 R12 R11 R10 R9 R8
CRClo = R7  R6  R5  R4  R3  R2  R1 R0
Data  = D7  D6  D5  D4  D3  D2  D1 D0
T     = T7  T6  T5  T4  T3  T2  T1 T0
U     = U7  U6  U5  U4  0   0   0  0

Bit *15 14 13 12 11 *10 9  8  7   6   5   4   *3  2   1  0
#1                           R15 R14 R13 R12 R11 R10 R9 R8
#2       U7 U6 U5 U4 T3  T2 T1 T0
#3                       U7 U6 U5 U4  T3  T2  T1  T0
#4                                                U7  U6  U5 U4

Line 1 is CRChi moved into CRClo; line 2 is the high nybble of U and the low nibble of T; line 3 is the line 2 byte shifted left by 3 bits; and live 4 is U shifted right by 4 bits.

If byte is "T" ($54), CRC = $FFFF, then answer should be $1B26.

Cyclic Redundancy Checks:

With a properly constructed 16-bit CRC, an average of one error pattern will not be detected for every 65,535 that would be detected. That is, with CRC-CCITT, we can detect 99.998 percent of all possible errors.

It is precisely this paragraph that lead me to ask the original questions:

"It should be noted that CRC polynomials are designed and constructed for use over data blocks of limited size; larger amounts of data will invalidate some of the expected properties (such as the guarantee of detecting any 2-bit errors). For 16-bit polynomials, the maximum designed data length is generally 2^15 - 1 bits, which is just one bit less than 4K bytes. Consequently, a 16-bit polynomial is probably not the best choice to produce a single result representing an entire file, or even to verify a single EPROM device (which are now commonly 8K or more). For this reason, the OS9 polynomial is 24 bits long."

"By some quirk of the algebra, it turns out that if we transmit the complement of the CRC result and then CRC-process that as data upon reception, the CRC register will contain a unique nonzero value depending only upon the CRC polynomial (and the occurrence of no errors). This is the scheme now used by most CRC protocols, and the magic remainder for CRC-CCITT is $1D0F (hex)."

No reference has every explained this "quirk". $1D0F is more commonly expressed as $F0B8, reverse bit order.

Software Safety blog reader Michael Barr has a new article Bug-killing standards for firmware coding on Embedded.com, where he discusses "Ten bug-killing rules" Michael also has his own blog.

There is also an interesting discussion going on in the comments section related to the article.

I even added a comment of my own:

Dale Shpak wrote:

" I have debugged millions of lines of code and have encountered the following type of error many times:

while (condition);

{

/* Execute conditional code */

}"

If you put this in your .emacs file:

(global-cwarn-mode 1)

Errors such as "if(condition);" and "while(condition);", as well as "if( x = 0 )" type errors are highlighted.

No need to use the One True Brace style when you are using the One True Editor... :-)

Also MISRA 21.1(a)/2004 requires the use of static analysis tools, that would never allow the passage of an always executing "conditional".

MISRA doesn't say much about style. It does say braces will always be used. I say that they should clearly show the nesting. Path coverage testing is hard enough without playing "find the matching brace" (EMACS helps out here too).

On a personal note, yesterday I received my re-certification papers from the American Society for Quality (ASQ). I am now officially certified for three more years as a Certified Software Quality Engineer (CSQE).

The CMMI Product Team has released Technical Report CMU/SEI-2009-TR-001:

"CMMI for Services (CMMI-SVC) is a model that provides guidance to service provider organizations for establishing, managing, and delivering services. The model focuses on service provider processes and integrates bodies of knowledge that are essential for successful service delivery."

Long hours link to dementia risk

Something I really like from the Agile Methodology is the 40 hour week. BBC News is reporting:

Long working hours may raise the risk of mental decline and possibly dementia, research suggests. The Finnish-led study was based on analysis of 2,214 middle-aged British civil servants. It found that those working more than 55 hours a week had poorer mental skills than those who worked a standard working week. The American Journal of Epidemiology study found hard workers had problems with short-term memory and word recall. “ This should say to employers that insisting people work long hours is actually not good for your business ” - Professor Cary Cooper University of Lancaster

In C are you a Righty or Lefty?

Do you write your code, like almost everyone does, like this (Those are Zeros if you have a funky font):

if( x == 0 ){...}

or do you do it correctly and do it this way?:

if( 0 == x ){...}

Why is the latter the correct way? It prevents you from making this mistake:

if( x = 0 ){...}

"Unless Debugging is an Obsession" put the constants on the left in any conditional test. Also use a lot of parentheses, you can never have to many parentheses, if there is more than one condition in the test. When you put the condition on the left, the compiler will refuse to compile the code at all, because you can not assign a value to a constant. Putting the constants on the right may elicit a warning if you are using a good quality compiler, if your lucky. I've been giving out this advice for years. The responses have been interesting:

I've never made that mistake. I don't need such crutches. -- AVR GCC List It does not read right. -- Well known Compiler Guru, in private email.

What is wrong with reading it as "if Zero is equivalent to X"? Do you want to ship products on time and under budget, or do you want to write code in the way that everyone else does?

Wanted: Experianced Embedded System Developer with a Brain

"I am a consultant and I am frequently hired by CEO's and CFO's who are at their whits end with the 'kids' that got hired by the other kids that got the job then decided the lights were brighter and more sparkley someplace else..." --- by FlyingGuy (989135) on SlashDot.org.

That seemed like a good introduction to this real Want Ad I saw on Craigs List this week. I have all of the experience they are looking, would you sign up based on this Ad (not that I'm looking right now)?:

EE / Embedded Control Hardware / Software Robot Instrumentation

Needed: One damn hot engineer to finish a robotics project for a very established company in East Pittsburgh Area.

This is a full time position but if you are some hot talented Carnegie Mellon University Robotics student we'll consider part time, as long as you perform and deliver ( unlike the previous degreed graduated CMU student.)

This is a robotics project but the robotics are simple. The little robot is designed to carry instrumentation into a tight, hot crack where no instrumentation has gone before.

Personal Requirement:

1.A brain. 2. A watch 3. A cell phone that you answer 4. Ability to give up girl friend for being paid professionally. 5. Working with us professionally between the hours of 7am and 7pm, and not the reverse.

Professional Requirements

An excellent understanding and experience with digital circuit design, layout and interfacing. You had darn well better know how to lay out circuit boards and use a hot air rework station to put down SMD if you have to. You need a full understanding of VLSI circuits as well as discrete circuitry. Motor control and instrumentation associated with robotics. Servo Motors, DC Motors, Step motors Motors, Encoders etc..

A phenomenal understanding of the ATMEL AVR type of chipsets and supporting circuits and an excellent command of the C language used for writing code for those chips. You must have a complete mastery of all of the chips features, A/D, I/O, all TX/RX methods, Counter Timers etc..because they are all in use. Reading the articles in Make Magazine do NOT count. Read the first line again; Phenomenal Understanding.

I would hope that you also have a competent ability to write software in a windows environment for the display of the data the robot sends back. Even if its liberty basic / visual basic that is ok, but we'd prefer a full C++ development environment expertise.

You need to have enough understanding of analog electronics to digitize, transmit, store and display the information as well as the use of DC power supplies and supporting instrumentation such as digital storage oscilloscopes. Don't go getting a funny look on your digital experience face if someone asks you about the impedance of your connection.

You must be able to produce and provide documentation. Schematics, illustrations, photo documentation of progress, component lists etc... so they don't have to be extorted from you if you no longer work for us.

You will be signed up with a non-disclosure and confidentiality agreement. You will have a police & background check performed on you as well as drug testing. No criminal history and no history of drug use. Period.

I personally don't care if you are a student, have a BS, MS, or a Ph.D. What we need is ability and capability along with a high desire (even desperation) to work and finish the project. We are looking or talent and I personally was probably doing assembly language programming and building circuits by hand before you were even dumping in your diapers...and I'll be the chief person interviewing you. Come prepared IF you make it to the interview process.

As with any project, there is a point where it ends but of course...what project have you seen that ever ends. A success of a project always moves to improvements and expansion of that project so there is the very very real potential for this to be full time unending employment. Full professional pay, full benefits, vacation time, medical, house, picket fence, 2.5 kids etc.

The work environment is professional in every sense. Nice office, large lab and work area, new Dell Computers for everything, excellent people to work for and just good natured and nice all around. No jag offs trying to make a joke at your expense. We guarantee that.

So you have a choice. The red pill or the blue pill. If you decide the blue pill than please wake up tomorrow and forget all about this. If you decide the red pill then please send back an email with your interest as well as your resume, experience, links to your website with photos /video of accomplishments/project (not your cat) etc...

The USA is basically in a depression and there millions of people out there with extreme talent looking for professional positions so if you want this position you had better make your submittal good.

Thank you, Steve.

Article: http://pittsburgh.craigslist.org/egr/1049407629.html

Steve sums up my view, and the views of many of today's HR departments. Some of the HR blogs indicate that they have turned into babysitting services, to keep the newly degreed young people from moving on when they are hit with the least bit of negativity.

Like FlyingGuy in the introduction, I do my own part time consulting gig. I get called in to clean up the mess left by people with lots of letters after their name.

I once went in to clean up a project that was designed by a committee of people spread all over the world. The unit was large moving equipment that if something went wrong, people might die. The unit was composed of several different CPU modules communicating on a property bus. Each modules software was written by a different group in a different part of the world.

The operators requested speed was input in Feet Per Minute. The output to a Variable Frequency Drive was in tenths of Hertzs. The tachometer feedback was in RPM, and to top it off all the internal calculations where done in Radians-Per-Second.

The first thing I did to get the project back on track was to adopt a standardized variable naming convention, that included the units. For example the Operator Request became operator_request_fpm_u16. You then knew immediately you where dealing with Feet Per Minutes, and that it was a 16 bit unsigned variable. After the variable name clean up may of the bugs became self documented, when you saw something like "operator_request_fpm_u16 / vfd_hz_s32" in the code, you knew there was a problem that needed fixed...

What has been your experiences with hiring people? Do you turn away people with experience in favor of people with degrees?

Embedded Systems A Volatile Business

At the end of Embedded systems - a volatile business Jack Ganssle says: Bob Paddock sent me the link [Embedded System Compilers generate dangerous code], and thereby wrecked my day.

Always happy to wreck a day, by pointing out Software Safety issues. :-)

I believe that Jack and I see eye-to-eye on most embedded system issues, but I have to disagree in one area. In his column Skip bugging to speed delivery Jack stated: We only inspect new code because there just isn't time to pour over a million lines of stuff inherited in an acquisition.

Development times are always shorter that we want, so not wanting to look at inherited code may seem like a good shortcut to save time. Myself I do not see it that way. Just because a bug is old, does not mean that it is something to be ignored. The Zune problem, that we have already covered here is a perfect example. The Board Support Package was 'inherited' so it seems no one bothered to inspect the code.

Atmel's new TouchLib product shows us an other example of code that can't be inspected at all. TouchLib is only available as a binary library file. The source code is not available, even under NDA (I asked), to allow for inspection. In Atmel's view this is their way of protecting their Intellectual Property.

If you take the trouble to actually read the three different TouchLib licenses, from registering, installing and in the TouchLib archive, all three more or less say: "If this product screws up it is not our problem".

Why would I want to use code that I can not verify as safe and correct? My company is the one that would have to deal with potential warranty issues, calls from angry customers etc. I should just tell them "Sorry, we used software that we got off the Internet for free, but have no idea how it works"? What would your reaction to that be as a customer? I don't think you'd be very happy. Unhappy customers don't come back as paying customers.