Principle of CRC

CRC is a polynomial-based error detection technique. The sender appends $r$ redundant bits (the CRC) to the dataword so that the resulting codeword is exactly divisible by a predetermined generator (divisor) using modulo-2 arithmetic (XOR, no carries). The receiver divides the received codeword by the same generator: remainder 0 means no error detected; nonzero means error.

Steps (sender):

1. Append $r$ zeros to the dataword ($r$ = degree of generator).
2. Divide by the generator using modulo-2 division.
3. Replace the appended zeros with the remainder; this is the codeword.

Given

• Dataword: 1101011011
• $G(x) = x^4 + x + 1 \Rightarrow$ divisor 10011 (degree 4, so append 4 zeros)
• Dividend: 1101011011 + 0000 = 11010110110000

Modulo-2 division

Step	Current bits	XOR with	Result (remainder)
1	11010	10011	01001 -> 1001
2	1001+1 = 10011	10011	00000 -> 0000
3	0000+1 = 00001	00000	0001
4	0001+0 = 00010	00000	0010
5	0010+1 = 00101	00000	0101
6	0101+1 = 01011	00000	1011
7	1011+0 = 10110	10011	00101 -> 0101
8	0101+0 = 01010	00000	1010
9	1010+0 = 10100	10011	00111 -> 0111
10	0111+0 = 01110	00000	1110

CRC (remainder) = 1110

Transmitted codeword

Dataword + CRC = 1101011011 | 1110  ->  11010110111110

Receiver verification (no bit altered)

The receiver divides 11010110111110 by 10011. Since the codeword equals dataword-with-zeros XOR remainder, the division leaves remainder 0000. A zero remainder means no error is detected and the dataword 1101011011 is accepted. If any bit flipped, the remainder would be nonzero (unless the error pattern is itself a multiple of $G(x)$), and the frame would be discarded.