3

On the Wikipedia page for Cyclic Redundancy Check, it says that:

CRC is a linear function with a property that ${\displaystyle \operatorname {crc} (x\oplus y)=\operatorname {crc} (x)\oplus \operatorname {crc} (y)}$

This linearity property is a vital part of what makes CRC implementations efficient, and so I would like to understand how this conclusion was derived.

On the related page on CRC mathematics, the CRC is defined as $R(x)$ where:

$$ \begin{eqnarray}M(x)\cdot x^{n} &=& Q(x)\cdot G(x)+R(x) \\ R(x) &=& M(x)\cdot x^{n}\,{\bmod \,}G(x)\\ \end{eqnarray} $$

How does one get from this to the linearity conclusion?

As a clarification, let's disregard the complicating issues of actual CRC standards like the non-zero initial values, bit inversions and endianness. Just the polynomial division.

rityzmon
  • 179

2 Answers2

3

With $G(x)$ fixed, if you have two messages $M_1$ and $M_2$ then

$$ \begin{eqnarray}M_1(x)\cdot x^{n} &=& Q_1(x)\cdot G(x)+R_1(x) \\ M_2(x)\cdot x^{n} &=& Q_2(x)\cdot G(x)+R_2(x)\\ \end{eqnarray} $$

where $R_1$ and $R_2$ are the respective CRC of $M_1$ and $M_2$.

If you want to compute the CRC of $M = M_1 \oplus M_2$, the XOR of $M_1$ and $M_2$, you have to

$$ \begin{eqnarray}M(x) \cdot x^n = \mbox{ (in $\mathbb{F}_2[x]) $ }&=&(M_1(x) + M_2(x))\cdot x^{n}\\ &=& Q_1(x)\cdot G(x)+Q_2(x)\cdot G(x)+R_1(x)+R_2(x) \\ \end{eqnarray} $$

Then the CRC of $M$ is $R_1(x)+R_2(x)$ that, in $\mathbb{F}_2[x]$, is $R_1(x)\oplus R_2(x)$, the XOR between both CRCs.

ilmarchese
  • 321
3

The basic tool being used here is polynomial division: if $f(x)$ and $g(x)$ are polynomials with coefficients in some field $K$, then there are unique polynomials $q(x)$ and $r(x)$ such that: $$ f(x) = q(x)\cdot g(x) + r(x) $$ where either $r = 0$ or $\deg(r) < \deg(q)$. In the CRC algorithm, $K$ is the field $\Bbb{Z}_2$ with two elements, $g = G$ is some fixed polynomial, $f$ is the polynomial whose coefficients are the bits of the message padded with $\deg(g)$ zeroes and the CRC comprises the bits given by the coefficients of $r$.

The linearity property is a property of polynomial division: if you fix the divisor $g$, then the remainder $r$ is a linear function of $f$. I am not aware that this has anything to do with the efficiency of implementing the CRC algorithm (I thought it was usually implemented by the usual polynomial long division algorithm).

Rob Arthan
  • 48,577