CRC error detection with example

CRC (Cyclic Redundancy Check) is an error-detecting code that appends a few redundant check bits (the remainder of a binary polynomial division) to the data. The receiver divides the received frame by the same divisor, and a non-zero remainder means an error.

CRC-4 uses a 4-bit remainder with a 5-bit generator, here G(x) = x⁴ + x + 1, i.e. 10011.

Sender

Data = 1101011011 (10 bits). Append n = 4 zeros: 11010110110000. Divide by 10011 using modulo-2 (XOR) division, no carries:

 start      1101011011 0000
 step at 0  11010 xor 10011 -> 01001110110000
 step at 1  10011 xor 10011 -> 00000010110000
 step at 6  10110 xor 10011 -> 00000000101000
 step at 8  10100 xor 10011 -> 00000000001110
 remainder  = 1110

Remainder (CRC) = 1110. Transmitted codeword = data + CRC = 11010110111110.

Receiver, no error

Dividing 11010110111110 by 10011 gives remainder 0000, so the frame is accepted.

Receiver, with error

Suppose bit 4 flips: received 11000110111110. Dividing by 10011 gives remainder 0111 ≠ 0, so the error is detected and the frame is discarded (retransmission requested).

Why it works

Transmitted polynomial T(x) is exactly divisible by G(x). An error E(x) is undetected only if G(x) divides E(x). CRC with a degree-4 generator that has a constant term detects all single-bit errors, all burst errors of length ≤ 4, and most longer bursts (miss probability about 1/2⁴).

Answer: CRC = 1110, codeword = 11010110111110; the corrupted word gives non-zero remainder 0111.