Hamming distance of a CRC

Question

How do you calculate the Hamming distance of a CRC generator ploynomial? for example if they say that the generator polynomial has a hamming distance of 3, for a given data length, how is it calculated?

Answer 1

Those bounds follow from the theory of cyclic codes.

A (binary linear) cyclic code of length $n$ (an odd natural number in all the interesting cases) has a generator polynomial $g(D)$ that is a factor of $D^n+1$ in the ring $\Bbb{F}_2[D]$ of polynomials in the unknown $D$ with binary coefficients.

The cyclic code $C$ generated by $g(D)$ then consists of the polynomials $x(D)$ that are 1) multiples of $g(D)$, and 2) have degree $<n$. This follows from the fact that the cyclic codes of length $n$ are viewed as ideals of the ring $\Bbb{F}_2[D]/\langle D^n+1\rangle$. Any book that explains the algebra of cyclic codes will explain why a cyclic code has a generator, and how it works.

The data on the minimum Hamming distance come from those of the code $C$. For example the polynomial $g(D)=D^8+D^4+D^3+D^2+1$ can be used. It is known to be a primitive polynomial of degree eight, so its zeros (in the extension field $\Bbb{F}_{256}$ have multiplicative order $255$. This means that $255$ is the smallest exponent $n$ with the property $g(D)\mid D^n+1$ (this can be brute forced). It follows that no binomial $D^i+D^j$ with $0\le i<j<255$ can be divisible by $g(D)$ either. What this means that using $g(D)$ as a CRC-polynomial we will detect all error patterns of weight at most two, if the total length of the protected data block+ 8-bit CRC tag is at most $255$.

In practice the CRC-polynomials are often products of two irreducible polynomials (often but not always primitive) of the same degree and possibly also the extra factor $D+1$. I recall figuring out such things for a few standardized CRC-polynomials as an exercise for myself. The product of an intelligently chosen pair of polynomials will generate a cyclic code belonging to some well studied family. IIRC at least double-error-correcting BCH codes, Melas codes and Zetterberg codes are used. The extra factor $1+D$ is a nice trick making sure that the minimum Hamming distance is even (if it isn't already). If you can spare that extra bit in the CRC-tag that may give the desired level of reliability to the check.

Anyway, if the cyclic code of length $n$ with a generator polynomial of degree $r$ is used, then the maximum length of the data block that can be protected is $n-r$. If the length of the data block is lower, then the resulting codeword has a corresponding number of extra zeros (that won't show anywhere).

In the cases I checked the bound on the minimum Hamming distance comes from some known bound on the cyclic codes. In the simplest cases the BCH-bound will suffice. In the case of Melas or Zetterberg codes we need that Hartmann-Tzeng bound (search with those buzzwords for their derivation).

One last word: there are often several pairs of irreducible factors leading to, say, minimum distance five. There exists some very specific tools in selecting among those. They involve largish simulations and such, but I'm not familiar with the details.