Numerically validate CRC performance
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 $&lt; 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 $&lt;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.