CRC is a polynomial remainder

I was learning CRC today. I started from the division I could already do on paper: given $D(x)$ and $G(x)$ over $\mathbb{F}_2[x]$, compute the remainder of $D(x)$ on division by $G(x)$. The CRC is one further shift.

A message may be corrupted on the way out. I append a short check, and the receiver divides the whole word by a generator chosen in advance. That check is the remainder. The place it lives is the end of the message.

Arithmetic in F_2

$\mathbb{F}_2$, also called $\mathrm{GF}(2)$, is the field with two elements. Addition and subtraction are both XOR:

Multiplication is AND:

A word is a polynomial

The bit string $101101$ is

The left bit is the highest power, so a uint32_t is a polynomial in $\mathbb{F}_2[x]$. Likewise $10011$ is $x^{4}+x+1$, and its degree is $4$: the index of the highest $1$. The loop starts at $-1$ and adds one on each right shift until the word is zero.

[[nodiscard]] int polynomial_degree(uint32_t polynomial) {
  int degree = -1;
  while (polynomial > 0) {
    polynomial >>= 1;
    ++degree;
  }
  return degree;
}

Long division

While the dividend still has degree at least $\deg G$, cancel its leading term. If $\deg D=n$ and $\deg G=r$, the multiple that lines up is $x^{n-r}G(x)$, and divisor << shift is that multiple. XOR is the addition.

[[nodiscard]] uint32_t polynomial_remainder(uint32_t dividend,
                                            uint32_t divisor) {
  const int divisor_degree = polynomial_degree(divisor);
  while (polynomial_degree(dividend) >= divisor_degree) {
    const int shift = polynomial_degree(dividend) - divisor_degree;
    dividend = dividend ^ (divisor << shift);
  }
  return dividend;
}

Take $D=1011010000$ and $G=10011$, so $\deg D=9$ and $\deg G=4$. The first shift is $9-4=5$:

  1011010000
^ 1001100000
------------
  0010110000

The degree is now $7$, so the shift is $3$:

  0010110000
^ 0010011000
------------
  0000101000

The degree is $5$, so the shift is $1$:

  0000101000
^ 0000100110
------------
  0000001110

The degree is $3$, below $4$, and the loop stops. The remainder is $1110$.

Each step replaces $D$ by $D+x^{k}G$ with $k=\deg D-\deg G$. That sum is congruent to $D$ modulo $G$, and the two leading terms are the same power, so they cancel and the degree falls. The loop begins with the original dividend, which is congruent to itself, and it ends at a polynomial of degree less than $\deg G$ in the same residue class. That remainder is unique. Write $\operatorname{rem}_{G}(D)$ for it: the polynomial of degree less than $r=\deg G$ congruent to $D$ modulo $G$. The value left in dividend is $\operatorname{rem}_{G}(D)$.

One shift makes it a CRC

The check appended to a message $M$ is

Multiplying by $x^{r}$ shifts the message left by $r$ and leaves $r$ zeros at the end. Those zeros are the room for the CRC. For $G=10011$, the degree is $4$, and the message $101101$ shifts to $1011010000$. That is the dividend above, so

[[nodiscard]] uint32_t crc(uint32_t message, uint32_t generator) {
  const int width = polynomial_degree(generator);
  return polynomial_remainder(message << width, generator);
}

message << width is $x^{r}M(x)$. Appending the remainder gives the word $x^{r}M(x)+R(x)$. The low $r$ bits were zero, so writing $R$ there is (message << width) | R. Here that word is $1011011110$. Division gives $x^{r}M=QG+R$, and $R+R=0$, so the word equals $QG$. The generator divides the message with the CRC appended.

The next step is to divide without building $x^{r}M$ as one integer.