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:
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.
Posts
