9
$\begingroup$

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 :-)

$\endgroup$
4
  • $\begingroup$ CRC as in CRC checksums? $\endgroup$ Oct 30, 2010 at 13:19
  • $\begingroup$ You should restate your question more clearly. Under what constraints? (e.g. given the polynomial degree) Are you talking about GF2 polynomials? (the usual for cyclic redundancy check e.g. CRC-16-CCITT and CRC-32-IEEE 802.3) Or GF2^N as in Reed-Solomon codes which are essentially similar? $\endgroup$
    – Jason S
    Oct 30, 2010 at 14:57
  • $\begingroup$ @J.M.: yes, as in CRC checksums $\endgroup$
    – stevenvh
    Oct 30, 2010 at 15:02
  • $\begingroup$ @Jason: yes, I'm talking about GF2 polynomials. I'll add it to my question $\endgroup$
    – stevenvh
    Oct 30, 2010 at 15:07

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .