What requirements should a CRC polynomial satisfy?

Question

What requirements should a CRC polynomial of a given degree satisfy to make the CRC catch a maximum of errors?

edit
I'm talking about GF(2) polynomials.
As an example of the kind of requirements I'm looking for: I can imagine (but don't know for sure) that a prime polynomial catches more errors than a composite polynomial.

I'm not a mathematician, so please type slowly :-)

Answer 1

Typically one considers the Hamming distance for the possible lengths of the messages, the larger the better.

See Koopman & Chakravarty, Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks.

Answer 2

Probably the link given by starblue gives you more than enough information. A few general remarks may help giving a new reader an overview, so here comes:

1) An irreducible check polynomial $p(D)\in F_2[D]$ (Edit: of degree $m$) catches all error patterns of weight $\le 2$ provided that the length of the data block+CRC-check is at most the order $k$ of $D$ modulo the polynomial $p(D)$. IOW $k$ is the smallest positive integer such that $D^k\equiv 1\pmod{p(D)}$. Here the game is to maximize $k$ (maximize the range of usability of this CRC). The maximum $2^m-1$ is reached exactly, when $p(D)$ is a so called primitive polynomial (or its root generates the multiplicative group of the field $GF(2^m)$).

2) If you want a guarantee for the CRC to catch more than 3 bit errors for certainty, then you have to use a product of irreducible polynomials. Typically (but not necessarily) they would have the same degree. If you are familiar with the theory of BCH-codes, then you see that a cyclic code generated by a product of minimal polynomials $p_1(D)$ of a primitive elemen $\alpha$ and the minimal polynomial $p_3(D)$ of $\alpha^3$, gives rise to a CRC-polynomial guaranteed to catch all the error patterns of weights $\le4$. BUT the price you pay for this is that the usable length of the CRC-polynomial $p_1(D)p_3(D)$ is only $2^{\deg p_1(D)}-1$, not $2^{\deg p_1(D)p_3(D)}-1$ as you might have hoped. This is because the polynomial $D^{2^m-1}+1, m=\deg p_1(D)$ is divisible by both $p_1(D)$ and $p_3(D)$ and creates "uncatchable" weight 2-patterns, if you make the block too long.

3) Generator polynomials of cyclic codes other than BCH-codes are often used. There are several pairs of irreducible polynomials that give rise to the same guaranteed error-detection probability as the generator polynomial of a BCH-code. Secondary design criteria often tip the scale in favor of these, also other choices give rise to check polynomials with slightly differing length limits. I have seen generator polynomials of Melas codes and Zetterberg codes used as CRC-polynomials.

4) You can always make sure that you CRC catches all the odd weight error patterns by multiplying the polynomial with $1+D$, if you can spare that single extra check bit.