Why is Hamming Weight (in the CRC context) independent from the data?

Question

I'm designing a communication protocol for 24 to 52 bits (typically 32 bits) data including the CRC-8 for error detection. I'm trying to select the best polynomial for this kind of application.

In the paper Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks Koopman, et. al. gives a very nice method to select a CRC polynomial depending on the needs of the application. The paper proposes that if Hamming Distance of two or more polynomials are equal, select the minimum Hamming Weight for a given bit length and error bits. Also Koopman kindly makes all these calculations and information publicly available in his site: http://users.ece.cmu.edu/~koopman/crc/index.html

As he also suggests "Don’t blindly trust what you hear on this topic", I've also verified his results for some of the 8-bit CRC polynomials using my own software. But here is what I failed to understand:

In the paper 32-Bit Cyclic Redundancy Codes for Internet Applications he defines the Hamming Weight as

A weight $W_i$ is the number of occurrences of a combination of $i$ error bits, including bit errors perturbing the CRC value, that would be undetected by a given polynomial for a given data word length.

Also, he explains why the Hamming Weight is independent from the data as follows:

Consider the fact that a data corruption is undetectable if and only if it transforms one codeword (some payload with its valid FCS value) into a different valid codeword. But because CRCs are linear, this means that the faulty bits that have been flipped from the original codeword have to themselves form a valid codeword. (In other words, the bits flipped in the message payload have to be compensated for by bits flipped in the FCS field, and the only way this can happen is if the entire set of bits flipped is itself a valid codeword.) This means that the actual data in a message payload is irrelevant in computing error detection abilities, which simplifies things greatly.

I also tried to calculate the Hamming Weight for different data and indeed obtained the same results. But I don't understand why this is the case. A rigorous proof or any different insights are greatly appreciated.

Edit: The example for Hamming weight given in the paper:

Suppose we have a codeword of length 12144 bits. So we have

$$ \pmatrix{12144 \\ 4} = \frac{12144!}{12140! ~ 4!} = 906 \times 10^{12} $$

possible bit errors. Hamming Weight is the number of undetected 4 bits error out of all possible 4 bits errors. So it is calculated for 802.3 CRC polynomial to be $W_4 = 223059$. This means $223059$ of $906 \times 10^{12}$ errors go undetected and this number does not change with the used codeword.

Answer 1

Let us call a data vector of some fixed length together with its CRC a codeword. Since CRC is a linear code, the set of codewords is closed under XOR (this is the definition of linear code).

Let $x$ be a codeword, and suppose that $y$ is a noisy version of $x$ which is also a codeword. Since CRC is linear, $x \oplus y$ is also a codeword. If $D$ is the minimum Hamming weight of a non-zero vector in the code, then the Hamming weight of $x \oplus y$ is at least $D$, that is, $y$ differs from $x$ in at least $D$ positions. This shows that at least $D$ errors need to occur in order for the errors to go undetected.

Conversely, let $w$ be a codeword of Hamming weight $D$. Then $y = x \oplus w$ is another codeword which differs from $x$ in $D$ positions. That is, $D$ errors (in appropriate locations) are enough for an error to go undetected starting from $x$. Note that $x$ here is completely arbitrary. This is why the minimum number of errors is independent of the data.

Answer 2

Define the sets

$$\begin{align*} P(d) &:= \{ p ~|~ \deg(p) \leq d \}\\ A_i(d) &:= \{ p \in P(d) ~|~ s(p) = i \} \end{align*}$$

where $s(p)$ is the number of $1$ coefficients of the polynomial $p$. For a given CRC generator polynomial $g$, define

$$ U_i(d) := \{ p \in A_i(d) ~|~ \exists q, p = q g \} $$

So $U_i(d)$ is the set of all undetected errors of length $i$ for data length $d$ using $g$. Now select an $x \in P(d)$ such that $x = q g$ for some $q$ and define the set

$$ U(x) := x \oplus U_i(d) := \{x \oplus p ~|~ p \in U_i(d) \} $$

Because of the linearity, all elements of $U(x)$ is dividable by $g$. We need to show that $U_i(d)$ and $U(x)$ has the same number of elements. This is obvious since $x \oplus p_1 = x \oplus p_2 \iff p_1 = p_2$.