CRC Polynomial Zoo

Philip Koopman, Carnegie Mellon University

Best CRCs | CRC Selection | CRC Zoo | Checksum and CRC Blog

Select # Bits in CRC below (see also NOTES PAGE):
3,  4,  5,  6,  7,  8,  9,  10,  11,  12,  13,  14,  15,
16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,
32,  33-36,  37-40,  41-44,  45-48,  49-52,  53-56,  57-60,  61-63,  64

• Good /6sub8 Polynomials
• Good HD=3 Polynomials
• Good HD=4 Polynomials
• Good HD=5 Polynomials
• Good HD=6 Polynomials
• Notation and copyright statement

NOTES SECTION:

Interpret the table entries as follows:

• (0xea; 0x1d5) <=> (0xab; 0x157) {85,85,2,2} [@177:proper,4.2x] | gold | (*o) CRC-8
  • "0xea" is an implicit +1 value of the polynomial, followed by the long version (explicit +1). The notation is admittedly slightly quirky, but has the advantage that machine words don't overflow on the polynomial value, and matches with my publications, so I decided not to change it. The link points to Hamming Weights for a variety of lengths, usually starting from length of 1 bit through 64KBytes. At longer lengths weights are given for every 8 bits or every 32 bits. If you have an intermediate length you can always just use the next higher table entry as a conservative approximation. See notes below on how to interpret the file format.
  • 0x1d5 is the explicit +1 notation of the same polynomial. In this representation of the same polynomial value, each "1" bit corresponds to a term in the polynomial, including the +1 at the end.
  • 0xab is the bit-reversed polynomial in implicit +1 notation. (Wikipedia calls this "reversed reciprocal" notation; and "Koopman notation" and I guess it is my fault for creating a divergent notation, but I did the original work before there was even a Wikipedia article on this, so that's just how things go. I appreciate that folks have accommodated this notation.) Bit-reversed polynomials have the same error detection characteristics in terms of having the same Hamming Weights. Thus, the data and corresponding bit flip error detection capability for 0xea is identical to the data for 0xab. So I only list one of the two alternative values in my tables. Usually it is the lexicographically smaller one, but there are a few exceptions to match widely published reversed values.
  • 0x157 is the explicit +1 notation 0xab of the bit-reversed polynomial.
  • "{85,85,2,2}" gives the dataword lengths for Hamming Distance (HD) values starting with HD=3. Polynomial 0xEA has HD=6 at dataword length 1-2, no lengths for HD=5, HD=4 at dataword lengths 3-85, and HD=2 at 86 bits and above. The repeating numbers in the list mean that this polynomial skips directly from HD=2 to HD=4 to HD=6. Clicking on the link gives machine-generated output to confirm the lengths.
    • A notation of "{}" with no numbers within the braces means HD=2 at all lengths. HD=2 lengths are always infinite, and so are always left out of this list.
    • A boldfaced number means this has been confirmed to be the longest length dataword at that HD for the given CRC size for all possible polynomials, not just the ones listed. Sometimes the bolding does not show up when rendered, but that is an html/browser issue.
    • The notation "?" means that this HW is still scheduled for computation and not yet available for posting.
    • Note that while computations were automated, web page construction was semi-automated, and in particular annotating the name of the polynomial was cut and paste, so please always check underlying data files for accuracy.
  • [@177:proper,4.2x] gives the proper polynomial characteristics for both low (up to 50% BER) and high (above 50% BER) bit fault rates.
    • @177 indicates that these characteristics apply up to and including 177 bit data word lengths. Unless otherwise noted, at one greater this length (in this case at data word length 178 data bits) there is a vulnerability to high BER corruptions, including specifically an all "1" bit data word yields and all "1" bit check value, meaning that 100% BER faults are undetectable (0% fault detection effectiveness). Other high BERs similarly have an elevated rate of undetected faults, in large part because they will by chance create an all "1" bit code word due to chance far more often than a 50% BER would.
    • "proper" in the first position after the length indicates that all BERs examined showed an undetected fault fraction no worse than 1/2^k, for BERs up to and including 50%.
    • "4.2x" in the second position after the length indicates that BERs above 50% had a worse case of 4.2/2^k (i.e., 4.2x worse than a proper polynomial) maximum for all data word lengths between 1 and the indicated data word length (in this case 177).
    • NOTE: alternate notation [256:proper,4.2x][@1020] would mean: proper up to 50% up to 256 bit data word; 4.2x worse than the proper limit above 50% up to a 256 bit data word; and 100% BER faults undetectable at 1021 bit data word, with the "properness" of data word lengths between 257 and 1020 not evaluated other than to check that there are no 100% BER vulnerabilities up to length 1020 and that there is definitely one such vulnerability at length 1021 bits.
  • The "gold" entry is an abbreviated set of computations performed by brute force computation without optimization as an integrity check. The main tables are created by very highly optimized code (if we didn't we'd never get done). The gold tables are the data used for regression testing the optimized computation and are provided for reference.
  • The final field, if present, is one or more "nicknames" for the polynomial from various sources. See Wikipediafor more formal references. It also includes salient factorization information:
    • *p - primitive polynomial. This has optimal length for HD=3, and good HD=2 performance above that length.
    • *o - odd bit errors detected. This has a factor of (x+1) and detects all odd bit errors (implying that even number of bit errors have an elevated undetected error rate)
    • *op - odd bit errors detected plus primitive. This is a primitive polynomial times (x+1). It has optimal length for HD=4, and detects all odd bit errors.
    • Other factorizations are sometimes of interest, but are less directly coupled to CRC performance. If you want to know the factorization of a polynomial you are interested in, we recommend using Wolfram Alpha, for example enter the following to see the factorization over 0xea (with the polynomial found on the first line of the Hamming Weight file 0xea):
      factor x^8 +x^7 +x^6 +x^4 +x^2 +1 over GF(2)
      or alternately in open code:
      Factor[x^8 + x^7 + x^6 + x^4 + x^2 + 1, Modulus -> 2]
      which gives a result of:
      (x+1)(x^2+x+1)(x^5+x^4+x^3+x^2+1) (mod 2)
      (Note that Wolfram could change their interface at any time, so I have not attempted to build these factorization links for the data tables.)

Interpret the Hamming weight data files as follows:

• # 0xea=x^8 +x^7 +x^6 +x^4 +x^2 +1 (0x1d5) <=> (0xab; 0x157)
  • "#" is a comment indicator so that you can grep to remove comments
  • "0xea" is an implicit +1 value of the polynomial (see above).
  • "x^8 +x^7 +x^6 +x^4 +x^2 +1" is the explicit polynomial representation.
  • 0x1d5 is the explicit +1 notation of the same polynomial (see above).
  • 0xab is the bit-reversed polynomial in implicit +1 notation (see above).
  • 0x157 is the explicit +1 notation 0xab of the bit-reversed polynomial (see above).
• #Length Poly HW(2) HW(3) HW(4) HW(5) HW(6) HW(7) HW(8) ...
  • The "#Length" line is a comment indicating that the data format is length of the data word (in bits), the polynomial (implicit +1 notation), followed by a list of Hamming Weights starting with HW(2). HW(1) is always zero for a CRC, and is omitted. HW(5), for example, is the number of undetected 5-bit errors out of all possible 5-bit errors affecting the codeword (both corruptions to dataword and the check sequence are considered). The number of HWs varies, but always includes at least the first non-zero HW, and often additional HWs. When the Hamming Distance changes as the dataword size increases, additional HW values are carried for a while to avoid protential problems with so called "improper" polynomial situations.
• 88 0xea 3 0 26313
  • This is an actual data entry. Each data file has HW values for many different dataword lengths.
  • 88=> the dataword length in bits, corresponding to an 11-byte dataword. To be sure, CRC check sequence bits are NOT included in this number. For smaller CRCs and dataword lengths values are given for every length, but in larger data files entries may only be given for every 8 or 32 bits of dataword length for longer lengths
  • 0xea=> each line has the polynomial value to facilitate processing the data with scripts
  • 3=> this is the HW(2) value. This means that out of all possible 2-bit errors, only 3 are undetected by this CRC for this dataword length.
  • 0=> this is the HW(3) value. All 3-bit errors are detected (zero undetected errors).
  • 26313=> this is the HW(4) value. There are 26,313 undetected 4-bit errors.
  • Note that no HW(5) and higher HW values are given. How many HWs are given depends on the HD at that dataword length. Be careful with integer size if you are processing this data -- many of the HW values exceed 32 bit integer capacity. I strongly recommend you use unsigned 64-bit integers when handling HW values (which is how it is done in my tools) or you'll get some weird results and potentially waste a lot of time tracking down the problem.

Interpret the Hamming distance data files as follows:

• # 0xea HD=3 len=85 Example: Len=86 {0} (0x80) (Bits=2)
  • This polynomial has HD=3 up to and including dataword length 85.
  • An example of a codeword that violates HD=3 is as follows:
    • Length of dataword is 86 (codeword is therefore 86+8=94 bits long). The example length is always one bit longer than the maximum HD dataword length shown (i.e., 85+1=86). The last line of the per-HD data has a length of NONE, providing an example showing that the indicated HD cannot be supported by the polynomial at any length.
    • Bit 0 is set (note that dataword bits are numbered 0..85). This is the first bit in the dataword, making it the bit furthest away from the FCS field. In other words, this bit has been cycled through a CRC shift register 86 times. The examples always have bit 0 set.
    • The FCS from computing the CRC for this dataword is 0x80. In other words, this is the residual CRC computation value after computing the CRC over an 86 bit data word with all zeros except the first bit (bit 0)
    • There are two bits set in this codeword (one bit from {0} plus one bit in the FCS value of 0x80=two bits), confirming HD=2 for this codeword
• 0xea {85,85,2,2}
  • 0xea is the polynomial
  • {85,85,2,2} is the list of all lengths, and is a summary of the preceding lines.

Nomenclature:

See Wikipedia for citations and sources of most names.

• "CRC-nK/m.v" notation is for polynomials that as far as I know I am the first to report as being "good" for a particular purpose. Some I have previously published, and some are working results that haven't been in a scholarly paper yet. The "n" means "n-bit CRC." The "m" is the smallest "interesting" Hamming Distance for that polynomial. Sometimes there is a ".v" if I've published two polynomials for that HD with different properties that are still useful.Thus, CRC-32K/6.1 is a 32-bit CRC that has good HD=6 performance and is version 1 (as opposed another HD=6 polynomial CRC-32K/6.2 that is also good for HD=6 but either published separately or has different but desirable secondary HD properties).
• Similarly, CRC-nF/m.v refers to polynomials from: G. Funk, "Determination of best shortened linear codes," Transactions Letters, IEEE Trans. on Comms., 44(1), Jan 1996, pp. 1-6. (Note that in some cases the "/m" part of the notation refers to HD performance at shorter than 4 bits of dataword length, so the data reported above might not appear to match the notation.)
• "FP-n" is the "First Primitive" polynomial for an n-bit CRC, meaning it is the smallest value polynomial that is primitive for that size CRC. This polynomial always has the longest possible HD=3 length, and also has all its "1" bits down near the bottom, which can make it more efficient to compute that polynomials with more randomly distributed 1 bits in the polynomial. It is often a poor choice if you care about anything better than HD=3, but is a reasonable baseline for comparison with other polynomials. The HD=3 length of any primitive polynomial of size n bits is ((2**n)-(n+1))
• "FOP-n" is the "First Odd+Primitive" polynomial for an n-bit CRC, meaning it is the lexicographically smallest polynomial that is (x+1) times a primitive (n-1)-bit CRC. This corresponds to the smallest n-bit CRC that has "(*op)" annotation for factorization. This polynomial always has the longest possible HD=4 length, and also has all its "1" bits down near the bottom, which can make it more efficient to compute that polynomials with more randomly distributed 1 bits in the polynomial. It is also divisible by (x+1) and therefore detects all odd number of bit errors (at the cost of even numbers of bit errors being undetected at an elevated rate). It is often a poor choice if you care about anything better than HD=4, but is a reasonable baseline for comparison with other polynomials. The HD=3 and HD=4 lengths of any primitive polynomial of size n bits is ((2**(n-1))-(n+1))
• "CRC-nK/DsubS" is for polynomials that have the property of only the bottom S bits set. Most are previously unpublished, but to make it easier to find I've added that notation in a few cases to previously discovered polynomials. As an example: CRC-32K/6sub8 is a 32-bit polynomial with the best HD=6 length for all polynomials that have bits set in only the lowest 8 bit positions. Polynomials with only low bits set and no bits in the middle (except for the highest bit) can be computed more quickly and with smaller lookup tables than polynomials with bits set throughout the polynomial, albeit often at the tradeoff of a shorter length than the best possible polynomial of that size.

I'll try to update Wikipedia with citations as they become formalized if nobody beats me to it. I have checked pretty thoroughly, but a lot of work in this area is pretty obscure. If I find out one of them was published before me I will of course be happy to update the attribution.

I welcome correspondence and especially notification of any errors that might have crept into the work. However, I cannot provide free individual advice on CRCs via e-mail. From time to time I'll augment the data, but research funding for this topic is scarce, so it mostly gets done more or less as a hobby.

If you know of a standard polynomial (e.g., one in an ISO, IEC, or IEEE standard) not in the "zoo" above, please let me know and I'll add it as I have time. (Ideally, you should add it to Wikipedia and then let me know it is there so I can do a data run for it.) While I have spent significant effort on getting things right, this data is provided as-is and provide with out any warranty whatsoever, no matter what might occur on an e-mail or other communication exchange. USE AT YOUR OWN RISK!

Thanks to:

• Prof. B. Gick for many enlightening discussions and data for Jones CRC-64.
• Bernhard Lindner for pointing out some manual transcription errors. I have since reworked everything with automated scripts so that all the entries on the pages oranized by CRC size are automatically generated.

Last update 5/2018.

This work is copyright 2015-2018 by Philip Koopman. Licensed under a Creative Commons Attribution 4.0 International License.