Numerically validate CRC performance

In this paper authors compare performance of different CRC polynomials in terms of minimum Hamming distance of two codes with the same checksum.

The naive method of doing this would require enumerating all codes that have the same checksum. This is computationally intractable for 2048 bit long data words that authors consider - so they must have used some more more efficient technique.

I did not find a mention in the paper on how the authors computed it. But it would be interesting to know the method as it would allow to numerically verify optimality of used CRC polynomials on given data word size.

What algorithm authors used to compute minimum HD for given CRC polynomial on long data words?

There are multiple techniques to compute the minimum Hamming distance for a given CRC polynomial. I don't know what technique they used, but here are three techniques that seem suitable.

I will assume the problem is as follows:

Given a CRC polynomial $p(x)$, determine whether there exists a $d$-bit error pattern of length $n$ that isn't detected.

This is equivalent to asking whether there exists a word of length $n$ with Hamming weight $d$ whose CRC is zero; or whether there exists a polynomial $q(x)$ of degree $n$ and weight $d$ such that $p(x)$ divides $q(x)$.

Method #1: Exhaustive enumeration

One can enumerate all words of length $n$ and Hamming weight $d$, and check each one to see if that error pattern would be detected. This involves checking ${n \choose d}$ possibilities, which is feasible if $d$ is small and $n$ is not too large, but rapidly becomes infeasible for larger parameters.

For instance, their Table 1 lists results for $n=48$ and $d=1,2,3,4,5,6$. These are feasible to compute by exhaustive enumeration. For instance, for $n=48$ and $d=6$, we have ${48 \choose 6} \approx 2^{37.3}$, and it's feasible to do $2^{37.3}$ computations on a computer in a reasonable amount of time.

As another example, for $n=2048$, it's feasible to compute results for $d=1,2,3$. We have ${2048 \choose 3} \approx 2^{32.4}$, which isn't too large. However, ${2048 \choose 4} \approx 2^{44.6}$ which is feasible but uncomfortably large.

Method #2: Meet-in-the-middle

We can speed up method #1 using a trick. The trick reduces the amount of computation time to something like $\sqrt{{n \choose d}}$, at the cost of requiring much more space (memory).

Note that the CRC is linear. Suppose there exists a data word $x$ of weight $d$ whose CRC is zero. We can express $x$ as $x=y \oplus z$ (where $\oplus$ denotes the xor), where $y,z$ each have weight $d/2$. Then by the linearity of the CRC, the CRC of $x$ is the xor of the CRC of $y$ and the CRC of $z$. So, if we want to search for an $x$ whose CRC is zero, it suffices to search for $y,z$ whose CRC xors to zero -- i.e., to search for $y,z$ that have the same CRC.

Now the method becomes this. We enumerate all data words $y$ of length $n$ and weight $d/2$, compute their CRC, and store them in a hashtable (or sorted list) keyed on the CRC. Next, we enumerate all data words $z$ of length $n$ and weight $d/2$, compute each one's CRC, and look up that CRC in the hashtable to look for matches. This will require $2 {n \choose d/2}$ CRC computations and ${n \choose d/2}$ space. Note that ${n \choose d/2}$ is roughly $\sqrt{{n \choose d}}$, so this is a big reduction in the running time.

If $d$ is not even, then we split into $y$ of weight $(d-1)/2$ and $z$ of weight $(d+1)/2$, so the running time is ${n \choose (d+1)/2}$ and ${n \choose (d-1)/2}$ space.

Of course, we can trade off memory for space, so we can find an algorithm with running time ${n \choose d_1}$ and space ${n \choose d_2}$ for any $d_1,d_2$ such that $d_1+d_2=d$.

As an example, for $n=48$ and $d=6$, there is an algorithm with ${48 \choose 3} \approx 2^{16.1}$ running time and ${48 \choose 3} \approx 2^{16.1}$ space -- easily computable on a computer. As another example, for $n=2048$ and $d=4$, the running time is $2^{21}$ and the space is $2^{21}$ -- again, easily feasible. For $n=2048$ and $d=5$, the running time is $2^{32.4}$ and $2^{21}$ space, which is again easily feasible. So this readily explains how one could compute the results in Figures 1-2.

(In fact, it turns out you can speed up this method by a small additional factor, at the price of an exponentially small probability of error. There are many ways to split $x=y \oplus z$, so in some sense the above method is doing more work than necessary. An optimization is to require that $y$ be zero in the last $n/2$ bits and $z$ be zero in the first $n/2$ bits, and search for such a split. This reduces the running time and space to ${n/2 \choose d/2}$ time and space. However, there is no guarantee that $x$ can be split in this way. So, instead, we pick a random subset $S \subseteq \{1,2,\dots,n\}$ of $n/2$ positions, and we require $y$ to be zero in all bit positions of $S$ and $z$ to be zero in all bit positions of $\overline{S}$, and we search for any solution. Then, we repeat this again multiple times with multiple different random choices of $S$. If there is a solution, then we have about a $1/\sqrt{\pi d/2}$ chance of finding it, so after $O(\sqrt{d})$ repetitions, there is an overwhelming chance that we find it. This provides a speedup by about a factor of $\Theta(2^{d/2}/\sqrt{d})$, at the cost of some implementation complexity.)

Method #3: Discrete logs in finite fields

Finally, there is one more method, which involves a lot more implementation complexity and requires knowledge of finite fields. Given $p(x)$, we'll try to determine whether there exists a polynomial $q(x)$ of degree $n$ and weight $d$ such that

$$q(x) \equiv 0 \pmod{p(x)}.$$

We can think of this as working in the finite field $\mathbb{F}_{2^m}$ where $m$ is the degree of $p(x)$. Note that there are fairly efficient algorithms for computing the discrete log in $\mathbb{F}_{2^m}$ when $m$ is not too large (as is the case for CRC polynomials, where typically $m \le 32$). We can think of any polynomial as an element in this finite field. For example, we can think of the degree-1 polynomial $x$ as an element in the finite field.

We'll use a subroutine for computing the discrete log of an arbitrary polynomial $s(x)$, to the base $x$. In other words, given $s(x),p(x)$, this subroutine returns us a number $k$ such that

$$s(x) \equiv x^k \pmod{p(x)}.$$

Now we'll split $q(x)=r(x)+s(x)$ where $r(x)$ has weight $d-1$ and $s(x)$ has weight $1$. If $q(x) \equiv 0 \pmod{p(x)}$, it follows that

$$r(x) \equiv s(x) \pmod{p(x)}.$$

Thus we'll enumerate all possible polynomials $r(x)$ of degree $< n$ and weight $d-1$, and for each, we will compute the discrete logarithm of $r(x)$ to the base $x$. If the resulting discrete log, call it $k$, is less than $n$, we have found a valid $s(x)$ of weight $1$ and thus $q(x) = r(x) + x^k$ is a multiple of $p(x)$ with degree $<n$ and weight $d$, so we have found a valid solution. If the resulting discrete log is $\ge n$, we discard this possibility $r(x)$ and continue enumerating other values of $r(x)$.

The running time is ${n \choose d-1}$ computations of a discrete log and $O(1)$ space. This is unlikely to be better than Method #2 except for very large values of $n$ and small values of $d$, but there are some parameter settings where it might be probably faster than Method #2.