Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
CRC as in CRC checksums? –  J. M. Oct 30 '10 at 13:19
    
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? –  Jason S Oct 30 '10 at 14:57
    
@J.M.: yes, as in CRC checksums –  stevenvh Oct 30 '10 at 15:02
    
@Jason: yes, I'm talking about GF2 polynomials. I'll add it to my question –  stevenvh Oct 30 '10 at 15:07
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.