Preprint: The International Conference on Dependable Systems and Networks, DSN-2004.

Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks
Philip Koopman
ECE Department & ICES
Carnegie Mellon University
Pittsburgh, PA, USA
koopman@cmu.edu

Tridib Chakravarty
Pittsburgh, PA, USA
tridib@alumni.carnegiemellon.edu

Abstract

least one combination of 6 bits that, when corrupted as a set
within a message, is undetectable by that CRC. An additional property of interest is burst error detection capability, but all codes we will discuss can detect burst errors up
to the size of the CRC width. Other possible evaluation
criteria exist such as unidirectional bit error detection(which depends on data values) and high-noise detection.
Unfortunately there does not seem to be any authoritative
characterization of faults in embedded networks. Our interactions with industry indicate that HD for random independent errors on a binary symmetric channel is usually the
primary factor considered in embedded network CRC design, and thus is the metric we use in this paper.
After a series of protocol evaluations for industry applications in which the question arose as to whether it would
be possible to achieve a given Hamming Distance (HD)with a given CRC size, we decided to explore the design
space of CRC size, message length, and attainable
Hamming Distance. The results indicate that there are significant opportunities for improving CRC effectivenessbecause some commonly used CRCs have poor performance. Moreover, many sources used in industrial practice teach engineers to select a polynomial without taking
into account the length of the data being error checked,
which ignores an important engineering tradeoff. And,even if engineers want to make detailed design tradeoffs,
tools and data tables on polynomial performance are scarceand often difficult to apply.
This paper presents a small set of polynomials that provides good overall performance while including message
length as a key design parameter. After discussing background and previous work, a methodology for defining“good” CRC designs is proposed, and the results of applying that methodology are presented. Comparisons of published CRCs to the proposed designs reveal both strengths
and serious weaknesses in the existing state of practice.

Cyclic Redundancy Codes (CRCs) provide a first line ofdefense against data corruption in many networks.
Unfortunately, many commonly used CRC polynomials
provide significantly less error detection capability thanthey might. An exhaustive exploration reveals that mostpreviously published CRC polynomials are either inferior
to alternatives or are only good choices for particularmessage lengths. Unfortunately these shortcomings andlimitations often seem to be overlooked. This paper
describes a polynomial selection process for embedded
network applications and proposes a set of good
general-purpose polynomials.
A set of 35 newpolynomials in addition to 13 previously publishedpolynomials provides good performance for 3- to 16-bit
CRCs for data word lengths up to 2048 bits.

1. Introduction
Cyclic Redundancy Codes (CRCs) are commonly used
for error detection in embedded networks and other applications. But many applications employ CRCs that provide
far less error detection capability than they might achieve
for a given number of CRC bits. This is largely because
there is little published guidance and less quantitative data
upon which to base tradeoff decisions. To help improve
this situation, this paper proposes “good” general purpose
CRCs for error detection applications that encompass
many current and future embedded network protocols andother uses having data words up to 2048 bits in length.
While various CRC designs can be found in standards
and folklore, most of them are far from optimal for the
short messages found in embedded networks. For embedded networks, the property of interest is usually the
Hamming Distance (HD), which is the minimum possible
number of bit inversions that must be injected into a message to create an error that is undetectable by that message's CRC-based Frame Check Sequence. For example,
if a CRC polynomial has HD=6 for a given network, thatmeans there are no possible combinations of 1-, 2-, 3-, 4-,
nor 5-bit errors (where a bit error is an inversion of a bit
value) that can result in an undetected error, but there is at

2. Background
A CRC can be thought of as a (non-secure) digest function for a data word that can be used to detect data corruption. Mathematically, a CRC can be described as treating a

1

binary data word as a polynomial over GF(2) Table 1. Example Hamming weights for data word size 48 bits.
(i.e., with each polynomial coefficient being
Hamming weights for number of bits corrupted:
CRC Size
CRC PolynomialHDzero or one) and performing polynomial di(bits)
1 bit 2 bits 3 bits 4 bits 5 bits
6 bitsvision by a generator polynomial G(x),16
CCITT-16
0x8810 4
0
0
0
84
0
2 430
which is commonly called a CRC polynomial. (CRC polynomials are also known as
16[Baicheva00] 0xC86C 6
0
0
0
0
0
2 191
feedback polynomials, in reference to the15
CAN 0x62CC 6
0
0
0
0
0
4 314
feedback taps of hardware-based shift register implementations.) The remainder of that12
CRC-120xC07 4
0
0
0
575
0
28809
division operation provides an error detec12
0x8F8 500001 452 13 258
tion value that is sent as a Frame Check Se8
DARC-80x9C 2066
02 039 13 122 124 248
quence (FCS) within a network message orstored as a data integrity check. Whether im8
CRC-8
0xEA 4
0
0
0
2 984
0
253 084
plemented in hardware or software, the CRC
7
CRC-7
0x48 30
0
216 2 690 27 051 226 856
computation takes the form of a bitwise convolution of a data word against a binary ver7
0x5B 4
0
0
0
5 589
0
451 125sion of the CRC polynomial. The data word
nomials have error detection performance inferior to availsize is the data protected by the CRC but not including theable alternatives, and appear to have been chosen to miniCRC itself. [Peterson72] and [Lin83] are among the commize the number of “1” bits in the feedback value at a time
monly cited standard reference works for CRCs. [Wells99]
when each such bit had substantial hardware implementaprovides a discussion for non-specialists.
tion cost. [Lin83] states that polynomial selection is “aError detection is performed by comparing an FCS
very difficult problem” and says that some good cyclic
computed on data against an FCS value originally comcodes have been discovered, but provides no details. Most
puted and either sent or stored with the original data. An
coding theory and practice books are similar to [Wells99]
error is declared to have occurred if the stored FCS andin that they give only a handful of published polynomials
computed FCS values are not equal. However, as with all
and little or no guidance on polynomial selection tradeoffs.
digital signature schemes, there is a small, but finite, probA Hamming weight N is the number of errors, out of allability that a data corruption that inverts a sufficient numpossible
message corruptions, that is undetected by a CRC
ber of bits in just the right pattern will occur and lead to anusingaparticularpolynomial. A set of Hamming weights
undetectable error. The minimum number of bit inversions
capturesperformancefor different numbers of bits correquired to achieve such undetected errors (i.e., the HD
ruptedinamessageata particular data word length, withvalue) is a central issue in the design of CRC polynomials.
each
successively
longerdata word length having set ofUsing the right polynomial is central to CRC-based erHamming
weights
withhighervalues. The first non-zeroror detection schemes. The prime factorization of the genHamming
weightdeterminesacode’sHamming Distance.
erator polynomial brings with it certain potential
Table 1 shows some example Hamming weights forcharacteristics, and in particular gives a tradeoff between
CRC polynomials at a data word size of 48 bits, which is a
maximum number of possible detected errors vs. data word
representative length for many embedded networks. The
length for which the polynomial is effective. Many polyfirst polynomial shown is the ubiquitous CCITT-16 polynomials are good for short words but poor at long words,
nomial 0x8810. 0x8810 is a hexadecimal representation ofand the converse. Unfortunately, factorization of a polynothe polynomial x16 +x12 +x5 +1, with x16 as the highest bit
mial is not sufficient to determine actual HDs. A polynoand an implicit +1 term, as is common in software-based
mial with a promising factorization might be vulnerable to
CRC implementations. It has only three “feedback” bits
some combination of bit errors, even for short message
set in the polynomial, which was advantageous for early
lengths. Thus, factorization characteristics suggest potenhardware implementations. For data words that are 48 bits
tial capabilities, but specific evaluation is required of any
in length, CCITT-16 detects all 1-bit errors (as does any
polynomial before it is suitable for use in a CRC function.
CRC polynomial), and all 2- and 3-bit errors. However, it
Conventional wisdom is that the best way to select aonly provides HD=4 at this length because, as shown by
CRC polynomial is to use one that is already commonly
the weights in Table 1, it fails to detect 84 of all possible
used. For example, [Press92] lists 16-bit polynomials and4-bit errors. In comparison, the 16-bit polynomial 0xC86C
states the choice of polynomial “is only a matter of conven[Baicheva00] attains HD=6 at this length.
tion.” This approach assumes that those polynomials wereWe can also do better than CCITT-16 for this example
selected for optimal error detection, which in some cases isusing smaller CRCs. The well known CAN 15-bit polynoincorrect. For example, several standardized 16-bit poly-2

Baicheva later surveyed all 16-bit CRCs for data words
up to 1024 bits in length [Baicheva00], identifying various
polynomials as both “good” in general and optimal for particular data word lengths.
A later survey paper[Kazakov01] extended those results to longer data words,
focusing on computing a point-by-point optimal bound for
16-bit CRC effectiveness. We have included their resultsin our evaluation of alternatives.
While 8 and 16 bit CRC sizes are often used, it is also
common to use other CRC sizes in embedded network applications to conserve bandwidth while achieving a particular desired HD. As illustrated by CAN’s use of a 15-bit
instead of 16-bit CRC, even saving one bit on the FCS field
makes a difference that matters.
Finding a comprehensive list of well known polynomials in print is difficult. [Peterson72] gives a list of irreducible polynomials of degree 16 or less, but does not give an
evaluation of error detection capabilities when those polynomials are used for CRCs. A search revealed publishedpolynomials for 3-, 4-, 5-, 6-, 7-, 8-, 10-, 12-, 14-, 15-, and16-bit CRCs. In many cases there is more than one recommended polynomial for a given CRC size. Worse, in thecase of the CRC-12 polynomial, there are three different
polynomials given under the same name, with most references evenly split between two of them. In the words of
one of the more complete listings of polynomial candidates, “These [polynomials] differ in bit 1 and calculations
using them return different values. With citations evenly
split, it is hard to know which is correct” [Jaffer03]. Givena lack of published quantitative analysis, popularity contests are a common method for selecting polynomials.
This paper seeks to publish readily usable engineering
guidelines for CRC selections of polynomial sizes 3 to 16
bits for embedded networks. CRC performance was determined by performing a complete evaluation of every possible undetected error pattern in messages as described in[Koopman02], yielding an exact result rather than an approximation. The balance of this paper first presents somecase studies illustrating the severity of current problems,then describes a methodology for selecting “good” general
purpose polynomials, and finally presents data for choosing embedded networking polynomials.

mial 0x62CC, which is optimized for data word sizes of up
to 112 bits, provides HD=6 at this length, missing only
4,314 of all possible 6-bit errors while using one less bit forits 15-bit CRC. Perhaps a surprise, though, is that 12-bit
polynomial 0x8F8 can achieve HD=5 at this length, while
the best published 12-bit CRC, 0xC07, achieves only
HD=4. The 8-bit CRC-8 polynomial 0xEA also achieves
HD=4 at this length – but a designer would have to know to
use that published polynomial rather than the published
DARC-8 polynomial, which does not. The smallest CRC
polynomial achieving HD=4 at this length is the 7-bit CRC
0x5B (albeit with a higher weight than CCITT-16), although the best published 7-bit CRC achieves only HD=3.
This example points out two fundamental problems withcurrent practice: there are gaps in the set of published polynomials, and there is a need for specific guidance on whichpolynomials to use when.
Proposing to make changes to decades of entrenched
CRC folklore and standardization is no small task. Whilesome might think that there is little need for new CRC
polynomials because networking standards force the use ofexisting polynomials, this is often not the case for embedded networks. New embedded networks are continually
being developed, each with unique performance and error
detection tradeoffs. The Train Control Network (TCN) is a
recent example for which we provided a CRC effectiveness evaluation that demonstrated an 8-bit CRC could haveprovided HD=4 protection compared to the 7-bit CRC plus
parity bit scheme used that provided only HD=3 protection[Koopman01]. In all fairness, TCN was constrained bylegacy compatibility to use a 7-bit CRC; but many protocols for new application areas are not so constrained.
Moreover, proprietary embedded network development
happens continually in industry. Given that there is no end
in sight to the proliferation of application-specific network
protocols, it makes sense to find out what the best CRC
polynomials are so that they can be used by new applications and emerging standards.

3. Previous work
Previous published work on CRC effectiveness has
been limited by the computational complexity of determining the weights of various polynomials. Only a few detailed surveys of polynomials have been published.
Baicheva surveyed 8-bit CRC polynomials with certain
factorization structures up to data word length 127[Baicheva98]. Baicheva proposed a good polynomial thatwas better than the ATM Header CRC polynomial. But, as
discussed below, the actual optimal polynomial for the
ATM Header data word length has a factorization that was
not evaluated in that survey. This illustrates the importance of an exhaustive search of polynomials when designing a CRC for an application.

4. Case studies of current protocols
Adopting a previously published polynomial has two
potential problems. One problem is that some polynomials
in use simply provide very poor error detection capabilities
overall. A second problem is that even a “good” polynomial is of necessity optimized for message sizes of a particular length, and will do poorly when misused for messagesof a different length. Some case studies of current polynomials in use illustrate these points.

3

4.1.

1e-12

USB vs. ITU for 5 bit CRCs

0x15

P

ud

P

ud

5-bit CRCs are used, among other places, for providing
HD=2
1e-15
error detection for Universal Serial Bus (USB) tokens andby an ITU standard for telecommunication systems. Figure 1 shows the performance of these polynomials com1e-18
pared to the best achievable bound. The probability of
0x12
undetected error Pud is summed from the probability of
HD=3
1e-21
successively higher numbers of bit errors at an assumed
Bit Error Rate (BER) of 10-6 weighted by the percentage oferrors caught per corresponding polynomial weights for
0x15 CRC-5
1e-24
0x12 USB-5
each data word length. The bound line shown assumes a
Bound
HD=4
different, optimal, polynomial is selected for each length,
1e-27
and thus is a firm bound on performance. Lower numbers
8
16
32
64
128
256
512
1024
2048
are better, indicating a lower probability of undetected erData Word Length (bits)
ror slipping past the CRC.
The USB 5-bit CRC standard, “USB-5,” is hexadeci- Figure 1. Performance of published 5-bit CRCs.
mal value 0x12 = x5 + x2 + 1 [USB00]. This polynomial is
1e-12
0x9C
used by USB to protect data words of length 11 bits.
0xEA
1e-15
USB-5 is optimal for 11-bit messages, and is nearly optiHD=20x97
mal for longer data word lengths. It is, however, not neces1e-18
sarily a good choice for data words sized 10 and lower,
because it is a full bit of HD worse than the bound.
1e-21
HD=3
ITU G.704 [G704] uses a 5-bit polynomial CCITT-5,
5
3
1e-24
0x15 = x + x + x + 1. Figure 1 shows CCITT-5 as optimalat length 10. However, CCITT-5 is a full bit of HD worse
1e-27
HD=4
0x9C DARC-8
that USB-5 at lengths 11-26, and more than a factor of 2
0xEA CRC-8
worse than the bound (and USB-5) at longer lengths. ITU
0x97
1e-30
Bound
G.704 uses CCITT-5 for a data word length of 3151 bits,
HD=5
which is clearly a length at which this is an inefficient
1e-33
8
16
32
64
128
256
512
1024
2048
CRC. (At 3151 bits USB-5 is optimal, and is 2.077 times
Data Word Length (bits)
better at error detection that CCITT-5.).
CCITT-5’s polynomial is divisible by (x+1), which re- Figure 2. 8 bit, HD=4 CRC performance.
sults in an ability to detect all odd numbers of bit flips andthe most commonly used 8-bit polynomial is “CRC-8”,
is commonly said to be desirable (e.g., [Tanenbaum96]).
which is 0xEA = x8+x7+x6+x4+x2+1. Figure 2 shows thatIndeed, at a data word length of 3151, CCITT-5 is the best
this polynomial provides HD=4 up to length 85. However,polynomial out of all 5-bit polynomials divisible by (x+1).
at lengths 86 to 119 it provides only HD=2 compared to aUSB-5, on the other hand, is not divisible by (x+1) and perbound of HD=4. At lengths above 119 it provides the sameforms better than CCITT-5 at all lengths above 10 bits. To
HD=2 as the bound, but with a significantly higher Pud.
understand why USB-5 does so much better in Figure 1, it
Overall, this polynomial is adequate up to length 85, but
is helpful to examine the weight structure at length 3151,
could be improved upon. Many uses of CRC-8 in current-6
shown in Table 2. For a BER of 10 , most messages ofsystems are therefore questionable, because they attempt tolength 3151 suffer zero-, 1-, or possibly 2-bit errors, with
provide error detection for a large data word (such aseach increasing number of erroneous bits less likely. As
across a long message or a large block of memory data).
Table 2 shows, USB-5 is almost twice as effective at detecting 2-bit errors, and the 3-bit error
weight for USB-5 is not high enough for
it to outweigh this advantage. Thus, Table 2. Weights for CCITT-5 and USB-5; data word size 3151 bits.
USB-5 is superior for this BER.

4.2.

8-bit polynomials

8-bit polynomials are commonly usedbecause they are efficient for 8-bit
microcontroller applications. Perhaps

PolynomialHD

USB-5 0x12
CCITT-5 0x15

Hamming weights for number of bits corrupted:
1 bit

2 bits20

159 075 163 552 409 128 929 654 767 81 278 805 135 219

2

0

330 435

4

3 bits0

4 bits257 909 068 726

5 bits0How can a designer do better than CRC-8? One way is
to take advantage of published improved polynomials. In
this particular case, [Baicheva98] has published polynomial C2, with value 0x97 = x8+x5+x3+x2+x+1 . Figure 2
shows that 0x97 has the same or better performance as
CRC-8 at every data word length (this is also true at lengths
beyond 2048 bits as well). Because of this, 0x97 dominates CRC-8 and therefore is an unconditionally better
polynomial choice given our fault assumptions. Moreover,
0x97 has optimal performance at length 119, the largest
possible length at which HD=4 can be achieved with an
8-bit CRC. Unfortunately, such analysis for polynomials isdifficult to find for other situations; there are no publishedcomplete surveys for other CRC sizes except those alreadymentioned.
The ATM-8 HEC polynomial 0x83 = x8 + x2 + x + 1(said to be from ITU standard I.432) does not dominate
CRC-8, but is close to C2. The two polynomials performessentially the same at lengths above 112 bits, but ATM-8
degrades to 45% worse than C2 at length 8 bits. For a
32-bit ATM data word, C2 is 4.9% more effective thanATM-8 at error detection for moderate to low BERs.
A pitfall of choosing a published polynomial is that it
might not be good for most data word lengths. For example, the DARC polynomial [ETSI02] 0x9C =x8+x5+x4+x3+1 is optimal for length 8, but provides only
HD=2 at lengths 10 and above with rather poor Pud performance as shown in Figure 2. The DARC application uses
this polynomial for data word lengths 16 through 48 bits,
where it performs poorly.
Figure 2 makes it clear that there are two missed opportunities even when choosing the best published 8-bit CRC
polynomials. The first is that they miss the HD=3 “ledge”
on the bound curve between lengths 120 and 247. The second is that none of them are close to optimal for lengths of
248 and higher. For example, CRC-8 is a factor of 3.3
worse at 1024 bits. Other published CRCs such as the
ATM HEC do no better than a factor of 2.3 worse than thebound at 1024 bits and higher. But, there are polynomials
that are far better than commonly used ones for HD=3 and
HD=2 applications. Figure 3 shows that 0xA6 = x8 +x6 +x3+x2 +1 maintains HD=3 up to 247 bits, and indeed is optimal at that length. Moreover, 0xA6 gives performance almost indistinguishable from the bound at lengths of 120
and up.
Two examples of real protocols help to illustrate the potential of improved CRCs: SMBus and Xmodem. SMBus
is a low speed communication bus used for “smart” batteries and portable electronic device power management applications. Version 1.1 of SMBus added a CRC-8
polynomial [Smbus00], presumably inherited from theolder I2C bus standard. Many of the messages are between
16 and 40 bits in length, and are suitably protected by

CRC-8 at HD=4. However, there is a data packet transfer
command that results in 35-byte (280 bit) message payloads. The protection afforded by CRC-8 is only HD=2 formessages 11 bytes and longer. The ATM-8 polynomial
might have been a better choice because it would have held
HD=4 for longer messages, and provided better error detection for HD=2 operating regions.
One can make the case that 0xA6 would have been aneven better choice for SMBus, depending on the expected
message workload. Longer messages make bigger targets
for random bit errors, and are therefore more likely to accumulate multiple errors. If the message workload for
SMBus in a particular application makes heavy use of longmessages, the HD=3 operating region of 0xA6 and thebetter performance for HD=2 operating regions might outweigh the penalty of increased vulnerability (HD=3 instead of HD=4) for short messages. The details depend on
the weighted sum of undetected error probabilities formessages of each length, which would vary by application.
But the point is that sometimes it is worth giving up a little
error detection at short message lengths to gain better protection for longer messages. (An alternate strategy would
be to use 0xA6 for long messages and a good HD=4 polynomial for short messages.)
Another common CRC-8 application is for the
XMODEM protocol, developed by Ward Christansen in
1977. This protocol transmits packets in 128-byte (1024bit) chunks protected by CRC-8. While polynomial evaluations were not generally available then, any of the alternate CRCs discussed here (except DARC-8) would havebeen a more effective choice.

5. Polynomial selection
The difference between good HD=4 polynomials and agood HD=3/HD=2 polynomial for 8-bit CRCs illustrates
that a one-size-fits-all approach to CRC selection can costa significant amount of error detection performance, including losing a bit (or more) of possible error detection
capability for some message lengths. Therefore, selectionof a good CRC polynomial must involve not only the sizeof the CRC, but also the size of the data word. Moreover,many commonly used polynomials are poorly suited tolikely applications. Therefore, we propose “good” polynomial candidates and prescribe a method for selecting anappropriate candidate for each application.

5.1.

Candidate polynomial selection

The selection of a “good” polynomial for generic use isof course a matter of engineering judgement. The following selection process was chosen to result in polynomials
that primarily maintained high HD values to the longest
data word lengths possible, secondarily achieved good
performance at shorter lengths, and thirdly achieved good5

performance at longer lengths than the stated maximum usage length. The prioritization of these goals keeps in mind
that embedded network applications typically have a maximum message length that needs a certain HD; that shortmessages can benefit from improved HD protection solong as protection of long message is not materially sacrificed; and that sometimes a protocol revision adds messages longer than originally envisioned, so good
performance at longer message lengths is desirable as asafety net.
The steps followed were performed for all distinct CRC
polynomials of size 3 bits to 16 bits.
(1) Compute weights for all polynomials at data word
lengths 8 bits through 2048 bits.
(2) Find the bounding weights by selecting the polynomial with the lowest weight at each length (i.e., generating
a list of point-wise optimal polynomials). In general thismeans a different polynomial is selected as the bound foreach length from 8 bits through 2048 bits, although inmany cases a single high-performing polynomial happens
to account for multiple bound values. This data was thesource of our “bound” curves.
(3) Identify “break points” in the bound, in which thebest achievable HD value changes. For example, the 8-bit
CRC bound in Figure 2 has break points as follows: HD=5
is possible to length 9, so the HD=5 break point is at 9. The
HD=4 break point is at length 119 (HD=4 is the best possible HD from length 10 to 119). The HD=3 breakpoint is at
length 247. And of course HD=2 is possible at all lengths
with any CRC polynomial. Follow the subsequent steps
for each breakpoint in turn.

(4) Identify all polynomials that achieve the HD boundat the breakpoint. This guarantees that the polynomial selected gets all the way into the “corner” of the bound curveat the break point. If there are multiple polynomials, selectthe one with the lowest weights. If there is a tie for lowest
weights or several low weights are within 1% of each other(a near-tie), invoke Steps (5) and (6). If there is an existing
published polynomial within 1% of the bound, use thatpolynomial. This step excludes polynomials that might bebetter at lower weights at the expense of decreasing HD before the break point (the HD=4 break point of CRC-8,
shown in Figure 2, is an example of a polynomial being
pruned from consideration for this reason).
(5) If multiple polynomials have been identified in Step4, select the polynomial having the longest-length breakpoint for the next higher HD value. For example, there are
30 distinct 10-bit polynomials that achieve the break point
HD=3 at length 1013, all of which have identical 3-bit
Hamming weights. However, among those polynomials,
the longest length for which HD=4 is possible is length 73
from polynomial 0x327, making it the choice for a “good”
polynomial. Similarly, polynomial 0xBAAD is the only
polynomial that provides both HD=4 at length 2048 and
HD=5 up to length 108 bits (other polynomials with HD=4
at 2048 bits provide HD=5 at shorter data word lengths),
and is only 0.39% worse in performance than the optimal
polynomial at length 2048, which is 0xD3E9 given by[Kazakov01]. This screening step provides polynomials
that not only provide good performance at break points,
but also have a bonus of even better HD at smaller lengths.

Table 3. “Best” polynomials for HD at given CRC size and data word length.
Underlined polynomials have been previously published as “good” polynomials.
Max length at HD
Polynomial
HD=2
HD=3
HD=4
HD=5
HD=6

CRC Size (bits)
8

9

10

11

12

13

14

15

16

2048+ 2048+ 2048+ 2048+ 2048+
0x9 0x12 0x21 0x48
0x5

3

4

2048+
0xA6

2048+
0x167

2048+
0x327

2048+
0x64D

–

–

–

–

–

26
0x12

57
0x21

120
0x48

247
0xA6

502
0x167

1013
0x327

2036
0x64D

2048
0xB75

–

–

–

–

10
0x15

25
0x2C

56
0x5B

119
0x97

246
0x14B

501
0x319

1012
0x583

2035
0xC07

2048
2048
2048
2048
0x102A 0x21E8 0x4976 0xBAAD

9
0x9C

13
0x185

21
0x2B9

26
0x5D7

53
0x8F8

none

8
0x13C

12
0x28E

22
0x532

27
0xB41

135
52
57
114
0x1909 0x372B 0x573A 0xC86C

12
0x571

none

12
13
16
19
0x12A5 0x28A9 0x5BD5 0x968B

11
0x9

5

6

7

HD=7

113
136
241
0x212D 0x6A8D 0xAC9A

11
11
11
12
15
0xA4F 0x10B7 0x2371 0x630B 0x8FDB

HD=8

6

(6) If Step 5 does not apply or results in a tie, select thepolynomial with best performance at 2048 bits (the maximum length computed). This yields a polynomial that has
good performance for long data word lengths.
(7) If Step 6 is an approximate tie (the HD weights arewithin 1%), pick the polynomial with the best weights at
smaller lengths, even if those smaller lengths are at thesame HD as the break point.
The result of applying this selection process is shown in
Table 3. Each cell in Table 3 has two numbers – a top number for the break point length at the given HD, and a bottom“good” polynomial for lengths up to the break point.
Lengths above 2048 bits were not studied in detail, but for
11 bit and smaller CRCs, the given polynomials are alsonear-optimal for arbitrarily longer lengths. The underlined
polynomials are ones that have been previously publishedas suitable for use in CRCs (see Table 4 for details). Table
3 can be used in the following ways:• Find a “good” polynomial given CRC size and length:
Select the appropriate CRC size column in Table 3.
Pick the row with the smallest length greater than orequal to the desired length. The polynomial in that box
will provide the best HD possible at that length and
CRC size. For example, for a 9-bit CRC, a length of 246
would use polynomial 0x14B and achieve HD=4, but
the best HD that can be achieved at length 247 is HD=3
using polynomial 0x167.
• Find the minimum size CRC required to achieve a given
HD at a particular length: Pick the row of Table 3 withthe desired HD. Select the furthest left column in thatrow with a length greater than or equal to the desired
length. That is the smallest CRC that can provide thedesired HD at the required length. For example, HD=6
for a data word length of 52 bits can be achieved with a
13-bit CRC using polynomial 0x1909.
Of course this selection table is not without limitations.
For applications that have only a single data word length,
and in which optimal performance is required even at theexpense of more effort in polynomial selection, an optimal
polynomial should be selected.

enough, and there is little point selecting a novel polynomial. Therefore, it is important to present an evaluation of
the performance of commonly used polynomials so designers can choose between the extra potential effort ofjustifying a “non-standard” polynomial selection vs. thepotential error detection gain.
Table 4 is a list of polynomials either in public use or
proposed as “good” polynomials in the literature that wehave encountered. (Only select polynomials from the published 8- and 16-bit surveys previously discussed havebeen included, since they are for the most part point solutions rather than generic suggested polynomials.) The best
available citation for each polynomial has been given,along with the most commonly used nickname.
Table 4 gives the performance for data word lengths
through 2048 bits. To keep the data manageable, performance is categorized into four columns. The first column
indicates that performance is optimal or near optimal(within 1% of the best possible performance bound). The
second column indicates that undetected error probabilities
are within a factor of two of the bound, which is a somewhat arbitrary distinction but overall is useful in conveying
which polynomials are close to being good for particular
data ranges. The third column indicates where polynomials have more than twice the undetected error rate of thebound, and the fourth column indicates where each polynomial’s HD is one or more bits worse than the bound. Underlined entries correspond to recommendations from
Table 3. Tables of weights for these polynomials andbounds are available from the primary author, and are on
the Web at http://www.ece.cmu.edu/~koopman/crc
Some CRC polynomials appear to be incorrect as a result of data transcription or similar errors that have occurred as polynomials are passed down over time. For
example [Ottoson01] gives a “CRC-7” value of 0x68 instead of 0x48 as given elsewhere, which might be due to a
one-bit data transcription error into a source code binary

5.2.

1e-21

1e-12

1e-15

HD=2

1e-18
0xA6

P

Despite the fact that Table 3 has many novel polynomials, that does not necessarily mean that a previously published polynomial will perform poorly in any specificapplication. In particular, the self-imposed requirement toachieve the maximum possible HD for break point values
disqualified some otherwise good standard polynomials.
For example the CAN polynomial 0x62CC is good forlengths up to 112 bits, but has a break point at 112 bits compared to the bound’s break point at 114 bits for HD=6. For
most applications, the CAN polynomial is likely to be good

HD=3

ud

Performance of published polynomials

1e-24

HD=4

1e-27

0xA6
Bound

1e-30

HD=5
1e-33
8

16

32

64

128

256

512

1024

2048

Data Word Length (bits)

Figure 3. A good 8-bit polynomial for lengths 120
and above.

7

Table 4. Performance of polynomials at BER = 10-6. Underlined ranges correspond to Table 3.
CRC
Size(Bits) Nickname Polynomial
3
4
4
5
5
6
6
7
7
7
7
7
8
8
8
8
8
8
8
9
9

SourcePerformance compared to bound at lengths given
Same HD, but
Within 1% ofWithin 2x ofWorse HD
more than 2x
bound
bound
than boundbound

0x5 = (x3 + x + 1)‡

8-2048–[RFC 3095]
8-2048–[G704]
0x9 = (x4 + x + 1)‡––[Ottoson01]
0xF = (x4 + x3 + x2 + x + 1)
8-10–
[G704]
0x15 = (x+1)(x4 + x3 + 1)‡
14-16[USB00] 11-13; 17-2048
0x12 = (x5 + x2 + 1)‡
12-25
8-11
[ETSI02]
DARC-6:
0x2C = (x+1)(x5 + x4 + x2 + x + 1)‡
29-36[G704] 26-28; 37-2048
CRC-6:
0x21 = (x6+x+1)‡
29-56
11-28
new
0x5B = (x+1)(x6 + x5 + x3 + x2 + 1)‡
57-86; 92-98[G704] 87-91; 99-2048
CRC-7:
0x48 = (x7+x4+1)‡
57-86; 92-98(CRC-7 inverse) [G832] 87-91; 99-2048
0x44 = (x7+x3+1)‡
57-86; 90-98[Funk88] 87-89; 99-2048
FT2:0x72 = (x7+x6+x5+x2+1)‡––[RFC3095]
0x67 = (x+1)(x3 + x + 1)‡(x3 + x + 1)‡–
8[Ottoson01]
0x68 = (x+1)(x2 + x + 1)‡(x4 +x3 +1)‡
8-9–
[ETSI02]
DARC-8:0x9C = (x8 + x5 + x4 + x3 + 1)
[Baicheva98] 27-50; 52; 56-119 18-26; 51; 53-55
C2:
0x97 = (x+1)(x7 + x6 + x5 + x2 + 1)‡
43-11919-42[Whitfield01]
DOWCRC: 0x98 = (x+1)(x7+x6+x5+x3+x2+x+1)‡
53-11918-52[Ottoson01]
ATM-8:
0x83 = (x+1)(x7+x6+x5+x4+x3+x2+1)‡
28-31; 43-119
20-27;32-42[Ottoson01]
WCDMA-8: 0xCD = (x+1)(x7 + x3 + 1)‡
136-140;
11-15; 120-135;
new
0xA6 = (x8 +x6 +x3 +x2 +1)‡
210-2048
141-209–
20-85[Ottoson01]
CRC-8:
0xEA = (x+1)(x2+x+1)‡(x5+x4+x3+x2+1)‡
8–
new
0x13C = (x+1)(x8 +x7 +x6 +x4 +x2+x+1)
13-16
–
new
0x185 = (x2 + x + 1)‡(x3 +x2 + 1)‡(x4 +x3 +1)‡

CCITT-4:
CRC-4:
CRC-5:

9

0x14B = (x+1)(x8 +x7 +x3 +x2 +1)‡

new

147-246

26-28; 30-146

90x167 = (x9 +x7 +x6 +x3 +x2 +x +1)‡

new45-46; 48;
412-2048

18-44; 47;
247-411100x28E = (x+1)(x2 + x + 1)‡(x3 +x2 + 1)‡(x4 +x3+1)‡ new

10

0x2B9 = (x5 +x2 +1)‡(x5 +x3 +x2 +x +1)‡

10

CRC-10:new

0x319 = (x+1)(x9 + x4 + 1)‡[Jaffer03]

10110x571 = (x11 +x9 +x7 +x6 +x5 +x +1)

new
new

11

0x532 = (x+1)(x10 +x9 +x5 +x +1)

new

11

0x5D7 = (x11 +x9 +x8 +x7 +x5 +x3 +x2 +x +1)‡

new

11

0x583 = (x+1)(x10 +x9 +x7 +x6 +x5 +x4 +x3 +x2 +1)‡ new

11

0x64D = (x11 +x10 +x7 +x4 +x3 +x +1)‡

new

12
12

0xA4F = (x+1)(x11 +x10 +x6 +x5 +x4 +x2 +1)
0xB41 = (x+1)(x3 +x2 +1)‡(x8 +x4 +x3 +x2 +1)‡

new
new

12

0x8F8 = (x12 +x8 +x7 +x6 +x5 +x4 +1)

new

12

0xC05 = (x2+x+1)‡(x2+x+1)‡(x8+x7+x6+x5+x2+x+1)‡

12

0xC06 = (x12+x11+x3+x2+1)

12
12

0x327 = (x10 +x9 +x6 +x3 +x2 +x +1)‡

CRC-12:[Press92][Whitfield01]

0xC07 = (x+1)(x11 +x2 +1)‡‡

[Ottoson01]‡

0xB75 = (x2+x+1) (x3+x2+1) (x7 +x5 +x4 +x3+1)‡

new

8

–
–
12-2048
27-2048–
58-2048–8-10; 121-2048–––
121-2048
121-2048248-2048
10-17; 248-2048
10-18; 248-2048
10-17; 248-2048
10-19; 248-2048

–
–
8-11
11-26
8-10
26-57
8-25
57-120
8-56
8-56
8-56
8-120
9-120
10-2478-9; 120-247
8-9; 120-247
8-9; 120-247
8-9; 120-247

108-9; 16-119

10-19; 248-2048
503-2048
9-12; 503-2048
14-25; 29;503-2048

8-9;86-247
9-502
8; 17-502
8-13;
247-502

14-17

8-13; 49-246

13-21;
96-1013
8-12;
17-21
13-16
1014-2048
22-10138-21;
306-501
73-30522-72; 1014-2048 502-1013
880-2048
32-73; 502-879
22-31
8-21; 74-501
8-12–
2037-2048
13-2036
8-12;
21-22
13-20
2037-2048
23-2036
23-24;
8-22;
25-28; 1775-2048–
1013-1774
29-1012625-1012
13-17; 96-624 27-95; 2037-2048 8-12;18-26;
1013-2036
111-131;8-26;
62-110; 96-624;
27-61
1775-2048
132-1012
1013-1774
8-11––
12-2048
22-27
13-21
12
8-11
8-27;
42-53
28-41
–
54-2048
8-53;–
55-16054
161-2048–––
8-20488-53;
1074-2035
221-1073
54-2202036-2048
2036-2048––
8-2035
9-12

8; 77-95

22-76; 1014-2048

Table 4 continued.
CRC
Size(Bits) Nickname Polynomial

Source13

0x10B7 = (x+1)(x+1)(x11 +x9 +x7 +x6 +x5 +x +1)

new

13

0x12A5 = (x2+x+1)‡(x11 +x10 +x6 +x5 +x4 +x2 +1)

new

13

0x1909 = (x+1)(x12 +x8 +x7 +x6 +x5 +x4 +1)

new

13
14

0x102A = (x4+x3+x2+x+1)(x9+x8+x4+x3+x2+x+1)‡

14

0x28A9 = (x14 +x12 +x8 +x6 +x4 +x +1)‡

14

0x372B = (x+1)(x+1)(x12+x11+x10+x7+x5+x4+x3+x +1)‡

14

0x212D = (x7 +x6 +x3 +x +1)‡(x7 +x6 +x5 +x4 +1)‡

14
14
15

0x21E8 = (x4 +x3 +x2 +x +1)(x10 +x9 +x4 +x +1)‡

new
0x2371 = (x+1)(x+1)(x+1)(x11+x10+x6+x5+x4+x2+1) new
new
new

DARC-14:

new

new[ETSI02]new

0x2402 = (x+1)(x13 + x12 + x11 +x +1)‡
0x630B = (x+1)(x14 +x9 +x3 +x2 +1)‡

15

0x5BD5 = (x3+x2+1)‡(x12+x11+x8+x6+x5+x3+x2+x+1) new

15

0x573A = (x+1)(x14+x13+x10+x8+x7+x6+x4+x+1)

15

0x62CC = (x+1)(x7 +x3 +1)‡(x7 +x3 +x2 +x +1)‡

CAN:

new

[Bosch91]

15

0x6A8D = (x15 +x14 +x12 +x10 +x8 +x4 +x3 +x +1)

new

0x4976=(x4+x3+x2+x+1)(x11+x10+x8+x7+x6+x4 +x2+x+1)‡
new[Gilmore02]
0x4001 = (x15 +x +1)‡
0x740A=(x3+x2+1)‡(x6+x+1)‡(x6+x4+x2+x+1) [MPT1327]
0x8FDB =(x+1)(x15+x14+x13+x12+x10+x8+x6+x5+x3+x2+1)‡ new15

Performance compared to bound at lengths given
Same HD, but
Within 1% ofWithin 2x ofWorse HD
more than 2x
bound
bound
than
bound
bound
10-11
8-9
–
12-2048
8-11;
14-52;
12-13
–
53-56
57-2048
8-12;
44-52
21-43
13, 14-20
53-2048363-2048
171-362
53-170
8-52
11
10
8-9
12-2048
8-11; 15-113;
13-14
12; 136-317
114-135318-2048
8-13;
51-57
30-50; 304-2048 14-29; 114-303
58-113;8-13; 22-57;
101-113
20-21; 58-100
14-19
114-2048
1940-2048
227-1939
114-226
8-113–
540-2048
114-539
8-113
12
10-11; 732-2048 8-9; 137-731
13-136;
8-12;
16
14-15
13
17-20488-16;
78; 98-114
49-77; 79-97
17-48
115-2048
8-16;
64-112
49-63
17-48
113-2048
8-114;
123-136
115-122–137-2048
1771-2048

441-1770

17-18; 137-440

8-16; 19-136

–
–

–
–
12-13; 42-51;
913-2048––
8-11; 20-41;
242-91219

16-18; 245-363

8; 242-244

160x968B = (x2+x+1)‡(x14 +x13 +x9 +x7 +x5 +x4 +1)

160xC86C = (x+1)(x15+x11+x10+x9+x8+x7 +x5+x4+x2+x+1)[Baicheva00]

110-111; 113-135

39-109; 112

20-38

0xAC9A = (x16+x14+x12+x11+x8+x5+x4+x2+1)[Castagnoli90]219-241

33-35; 136-218

8; 20-32

1578-2048

242-157720

8-20488-204816-19;
52-241
9-15;
20-241;364-2048
8-19;
136-2048
9-19;
36-135;242-2048
8-19; 21-241

1270-2048

256-1269

242-255

8-241

–
–

1270-2048
1270-2048
39-67;
1146-2048

242-1269242-1269
8; 20-38;
242-1145

8-241
8-241

–

39-1128-9; 20-38

10-19;
113-2048–

1015-2048

242-1014

8-241

15
15
16

16

C3

16
16
16
16

CRC-16:
ANSI-16:16
16

IEC-16:

16

CCITT-16:

Notes:

14-15

new

0xBAAD = (x3+x2+1)‡(x6+x5+x2+x+1)‡(x7+x3+1)‡ new
0xD3E9 = (x3+x2+1)‡(x6+x5+x2+x+1)‡(x7+x6+x5+x4+1)‡[Kazakov01][Press92]
0xA001 = (x+1)(x15 +x14 +1)‡
[USB00]0xC002 = (x+1)(x15 + x + 1)‡
0xD04B = (x+1)(x+1)(x14+x13+x12+x10+x8+x6 +x5+x4+x3+x+1)‡ [Ottoson01]
0xADC9=(x+1)(x+1)(x7+x6+x3+x+1)‡(x7+x6+x5+x4+x3+x2+1)‡ [Baicheva00]
0x8810 = (x+1)(x15+x14+x13+x12+x4+x3+x2+x+1)‡[ETSI02]–

All polynomials are represented as a product of irreducible factors‡

All polynomial factors marked with ( ) are primitive.

99-19; 68-241

[ETSI02] ETSI, Radio broadcasting systems; DAta Radio
Channel (DARC); System for wireless infotainment
forwarding and teledistribution, ETSI EN 300 751, V1.2.1,
October 2002.
[Funk88] Funk, G., "Performance comparison of standard frametransmission formats FT1.2 and FT2 specified by IEC
TC57", ntzArchiv Bd. 10, 1988, pp. 217-221.
[G704] International Telecommunication Union, General
Aspects of Digital Transmission Systems: Synchronous
frame structures used at 1544, 6312, 2048, 8488 and 44
736 kbit/s hierarchical levels, ITU-T Recommendation
G.704 (previously “CCITT Recommendation”), July 1995.
[G832] International Telecommunication Union, Transport ofSDH Elements on PDH Networks: Frame and Multiplexing
Structures, ITU-T Recommendation G.832 (previously“CCITT Recommendation”), November 1993.
[Jaffer03]
Jaffer, A., “Mathematical packages: cyclic
checksum,” accessed September 27, 2003 at
http://www.swiss.ai.mit.edu/~jaffer/slib_4.html#IDX522[Kazakov01] Kazakov, P., “Fast calculation of the number ofminimum-weight words of CRC codes,” IEEE Trans. Information Theory, (47) 3, March 2001, pp. 1190-1195.
[Koopman01] Koopman, P. & T. Chakravarty, “Analysis of theTrain Communication Network Protocol Error Detection
Capabilities,” Feb. 25, 2001, http://www.tsd.org/papers/[Koopman02] Koopman, P., "32-bit cyclic redundancy codesfor Internet applications," Intl. Conf. Dependable Systems
and Networks (DSN), Washington DC, July 2002, pp.
459-468.
[Lin83] Lin, Shu & D. Costello, Error Control Coding,Prentice-Hall, 1983.
[MPT1327] MX.com, Error detection and correction of
MPT1327 formatted messages using MX429A or MX809
devices, application note MPT1327, 1999.
[Ottosson01] Ottosson, T., T. Eriksson, P. Frenger, T. Ringström& J. Samuelsson, “crc.cpp,” version 1.8, May 22, 2003, at:
http://itpp.sourceforge.net/crc_8cpp-source.html[Peterson72] Peterson, W. & E. Weldon, Error-Correcting
Codes, MIT Press, Second Edition, 1972.
[Press92] Press, W., S. Teukolsky, W. Vetterling, & B. Flannery,
Numerical Recipes in C (2nd ed.), Cambridge Press, 2002.
[RFC3095] Bormann, C. (ed.), RFC 3095 - RObust Header
Compression (ROHC): Framework and four profiles: RTP,
UDP, ESP, and uncompressed, 2001, accessed at:
http://www.faqs.org/rfcs/rfc3095.html[Smbus00] SBS Implementers Forum, System Management Bus(SMBus) Specification, Version 2.0, August 3, 2000.
[Tanenbaum96] Tanenbaum, A., Computer Networks (3rd. Ed.),
Prentice Hall, 1996.
[USB00] Universal Serial Bus Specification, Rev. 2.0, 2000.
[Wells99] Wells, R., Applied coding and information theory forengineers, Prentice-Hall, 1999.
[Whitfield01] Whitfield, H., “XFCNs for Cyclic Redundancy
Check Calculations,” April 24, 2001, accessed at
http://homepages.
cs.ncl.ac.uk/harry.whitfield/home.formal/CRCs.html

data array. Unfortunately, 0x68 is dominated by six otherpolynomials and is generally inferior to 0x48.
Similarly [Jaffer03] indicates that various web-basedsources are evenly split between 0xC06 and 0xC07 as being the “standard” CRC-12 polynomial. Numerical
Recipes states that CRC-12 is 0xC05 [Press92]. One canspeculate that these are also one-bit transcription errors.

6. Conclusions
New embedded networks that use CRCs are continually
being created. Unfortunately, the usual practice of selecting a published CRC polynomial under the presumptionthat it is “good” runs into trouble because some publishedvalues perform quite poorly. Moreover, even if a good
published polynomial is available, there is generally no
published guidance on what range of data word lengths it isgood for nor, for that matter, quantitative data to help distinguish that good polynomial from any competing published or standardized “bad” polynomials.
This paper presents the first exhaustive survey of all
CRC polynomials from 3 bits to 15 bits, and discusses
16-bit polynomials as well. A methodology for selecting
generically “good” CRC polynomials is based on achieving maximum Hamming Distance for the longest possible
data word sizes and other performance considerations.
Our tables of good polynomials given should enable practitioners to use quantitative information in selecting effective polynomials for embedded computing error detection
applications for data word sizes up to 2048 bits.

7. Acknowledgments
Thanks to Kobey DeVale for her help in early explorations. This work was supported in part by grants from
Bombardier Transportation, the General Motors Collaborative Laboratory at Carnegie Mellon University, and thePennsylvania Infrastructure Technology Alliance.

8. References[Baicheva98] Baicheva, T., S. Dodunekov & P. Kazakov, “On
the cyclic redundancy-check codes with 8-bit redundancy,” Computer Communications, vol. 21, 1998, pp.
1030-1033.
[Baicheva00] Baicheva, T., S. Dodunekov & P. Kazakov, “Undetected error probability performance of cyclic redundancy-check codes of 16-bit redundancy,” IEEE Proc.
Comms., Vol. 147, No. 5, Oct. 2000, pp. 253-256.
[Bosch91] Bosch, CAN Specification, Version 2, 1991.
[Castagnoli93] Castagnoli, G., S. Braeuer & M. Herrman,"Optimization of Cyclic Redundancy-Check Codes with
24 and 32 Parity Bits", IEEE Trans. on Communications,Vol. 41, No. 6, June 1993.
[Gilmore02] Gilmore, J., “Parallel CRC Equation Generator”(source code), accessed on October 22, 2002 at:
http://www.physics.ohio-state.edu/~cms/crc_generator

10

ERRATAThe following corrections have been made to this paper:
8/3/2014: Page 6, table 3
CRC 0x5D7 provides HD=5 up to length 26 bits. The original paper indicated only up to 25 bits.
Thanks to Berthold Gick for reporting this issue.