Editing Cyclic redundancy check (section)

=== Designing polynomials ===
The selection of the generator polynomial is the most important part of implementing the CRC algorithm. The polynomial must be chosen to maximize the error-detecting capabilities while minimizing overall collision probabilities.

The most important attribute of the polynomial is its length (largest degree(exponent) +1 of any one term in the polynomial), because of its direct influence on the length of the computed check value.

The most commonly used polynomial lengths are 9 bits (CRC-8), 17 bits (CRC-16), 33 bits (CRC-32), and 65 bits (CRC-64).<ref name=Ergen-2008/>

A CRC is called an ''n''-bit CRC when its check value is ''n''-bits. For a given ''n'', multiple CRCs are possible, each with a different polynomial. Such a polynomial has highest degree ''n'', and hence {{nowrap|''n'' + 1}} terms (the polynomial has a length of {{nowrap|''n'' + 1}}). The remainder has length ''n''. The CRC has a name of the form CRC-''n''-XXX.

The design of the CRC polynomial depends on the maximum total length of the block to be protected (data + CRC bits), the desired error protection features, and the type of resources for implementing the CRC, as well as the desired performance. A common misconception is that the "best" CRC polynomials are derived from either [[irreducible polynomial]]s or irreducible polynomials times the factor&nbsp;{{nowrap|1 + ''x''}}, which adds to the code the ability to detect all errors affecting an odd number of bits.<ref name="williams93" /> In reality, all the factors described above should enter into the selection of the polynomial and may lead to a reducible polynomial. However, choosing a reducible polynomial will result in a certain proportion of missed errors, due to the quotient ring having [[zero divisor]]s.

The advantage of choosing a [[Primitive polynomial (field theory)|primitive polynomial]] as the generator for a CRC code is that the resulting code has maximal total block length in the sense that all 1-bit errors within that block length have different remainders (also called [[Syndrome decoding|syndromes]]) and therefore, since the remainder is a linear function of the block, the code can detect all 2-bit errors within that block length. If <math>r</math> is the degree of the primitive generator polynomial, then the maximal total block length is <math>2 ^ {r} - 1 </math>, and the associated code is able to detect any single-bit or double-bit errors.<ref>{{Cite book | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | isbn=978-0-521-88068-8 | chapter=Section 22.4 Cyclic Redundancy and Other Checksums | chapter-url=http://numerical.recipes/book.html | access-date=20 August 2024 | archive-date=13 July 2024 | archive-url=https://web.archive.org/web/20240713014419/http://numerical.recipes/book.html | url-status=live }}</ref> However, if we use the generator polynomial <math>g(x) = p(x)(1 + x)</math>, where <math>p</math> is a primitive polynomial of degree <math>r - 1</math>, then the maximal total block length is <math>2^{r - 1} - 1</math>, and the code is able to detect single, double, triple and any odd number of errors.

A polynomial <math>g(x)</math> that admits other factorizations may be chosen then so as to balance the maximal total blocklength with a desired error detection power. The [[BCH code]]s are a powerful class of such polynomials. They subsume the two examples above. Regardless of the reducibility properties of a generator polynomial of degree&nbsp;''r'', if it includes the "+1" term, the code will be able to detect error patterns that are confined to a window of ''r'' contiguous bits. These patterns are called "error bursts".