Cyclic redundancy check

Cyclic redundancy check (CRC, also polynomial codes) is a powerful error detection coding used in Ethernet and WiFi. It consists of two main components:

• $D$ data bits that we want to protect.
• $G$ bit pattern (called a generator) that is agreed by both parties (usually specified in some external pre-determined specification). It consists of $r+1$ bits.
  • The IEEE standard has 32-bits.

The core goal is that we choose $r$ CRC bits $R$ such that $⟨D,R⟩$ is exactly divisible by $G$ (mod 2). On the receiver side, we divide $⟨D,R⟩$ by $G$. If there’s a non-zero remainder, then we’ve detected an error. We can detect all burst errors less than $r+1$ bits.

Specification

The sender wants to compute $R$ such that:

$$D\cdot 2^r\oplus R=nG$$

where the $2^r$ essentially functions as a bitshift. Or equivalently (by XOR $R$ both sides):

$$D\cdot 2^r=nG\oplus R$$

which says that if we want to divide $D\cdot 2^r$ by $G$, we want the remainder $R$ to satisfy:

$$R=\text{remainder}\left(\frac{D\cdot 2^r}{G}\right)$$

Procedure

We are given $D$, $G$, and $r$.

• We first compute $D\cdot 2^r$. This is a leftwards bitshift by $r$ bits.
• Then, we perform a binary long division of $D\cdot 2^r/G$.
• We discard the result. Whatever is the remainder is