Error Detection Using Cyclic Redundancy Check (CRC): Principle, Modulo-2 Division, and Worked Example

Cyclic Redundancy Check CRC is an error-detecting code constructed from a generator polynomial $G(x)$. The core principle is polynomial long division over modulo-2 arithmetic (so subtraction is XOR, with no carries/borrows). Modulo-2 division is used to compute a remainder that is appended to the data, forming a transmitted codeword. At the receiver, the same division is performed; if the remainder is nonzero, an error is detected. This “nonzero remainder” property is central to CRC’s detection capability.

A generator of degree $r$ implies CRC appends exactly $r$ redundant bits (the remainder length) to the dataword. Generator polynomial defines the code structure; Remainder determines the appended checksum bits.

Polynomial model for CRC

Map a binary string to a polynomial over $GF(2)$:

• bit string $b_k b_{k-1}\dots b_0$ $\Rightarrow$ $b_k x^k + b_{k-1} x^{k-1} + \cdots + b_0$
• addition/subtraction uses XOR (coefficients reduced mod 2)

Then:

1. Data polynomial: $M(x)$ from the dataword.
2. Multiply by $x^r$ (append $r$ zeros): $M(x)\,x^r$.
3. Compute remainder $R(x)$ when dividing $M(x)x^r$ by $G(x)$: $M(x)x^r = Q(x)G(x) + R(x), \quad \deg(R) < r$
4. Transmitted codeword polynomial: $C(x)=M(x)x^r + R(x)$

At the receiver, the receiver divides the received bits interpreted as $C'(x)$ by $G(x)$. If the received codeword was correct (i.e., no errors), then: $C(x) \bmod G(x) = 0$ So any error pattern $E(x)$ that yields a nonzero remainder will be detected because: $(C(x)+E(x)) \bmod G(x) = E(x) \bmod G(x) \neq 0$

Key terms to anchor the idea

• Dataword $M$
• Generator polynomial $G(x)$
• Remainder $R(x)$
• Transmitted codeword $C(x)$

Visualizing the CRC division flow

Worked example (CRC codeword)

1) Inputs

• Dataword: 1101011011
• Generator polynomial: $G(x)=x^4+x+1$
• Degree: $r=4$
• Generator bit pattern (divisor): 10101 (since $x^4$ and $x^1$ and $x^0$ have coefficient 1)

So we append 4 zeros to the dataword:

• $M(x)x^4$ bits: 11010110110000

2) Modulo-2 long division to find remainder

We divide 11010110110000 by 10101 using XOR “subtraction” at each step when the leading bit is 1.

Carrying out the long division yields the final remainder:

• $R$ = 0100

Therefore the transmitted CRC codeword is:

• Transmitted codeword = dataword + remainder
• $C = \texttt{1101011011} \;||\; \texttt{0100} = \texttt{11010110110100}$

So the transmitted codeword is:

• 11010110110100

(Here || means concatenation.)

3) Verify at the receiver: division should give remainder 0

The receiver takes the received bits (assume no alteration) interpreted as $C(x)$ and divides by $G(x)=10101` again.

Because CRC construction guarantees $C(x)$ is exactly divisible by $G(x)$, we have: $C(x) \bmod G(x) = 0$

In binary remainder terms:

• Divide 11010110110100 by 10101
• Receiver remainder = 0000

Hence:

• The receiver concludes no error detected.