Cyclic Redundancy Check (CRC): 25-Comp-B5 Computer Communications, December 2014, Q4

Question 4: Cyclic Redundancy Check (CRC) (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Generator (divisor) bit pattern $P = 110011$ (6 bits, degree 5); message $M = 11100011$ (8 bits).

Given data
Quantity	Value
Generator $P$	110011
Message $M$	11100011

Find. The CRC — the $r$-bit remainder appended to $M$ to form the transmitted frame.

Approach. Determine the redundancy length $r = \deg(P)$; append $r$ zero bits to $M$; perform binary mod-2 (XOR-only, no-borrow) polynomial division of the augmented message by $P$; the final $r$-bit remainder is the CRC.

Redundancy length. $$r = \text{len}(P) - 1 = 6 - 1 = 5\ \text{bits}.$$
Augmented dividend. Append $r=5$ zero bits to $M$ (equivalent to $M \cdot 2^{r}$): $$M \cdot 2^{r} = 11100011\underbrace{00000}_{5\ \text{zeros}} = 1110001100000\ (13\ \text{bits}).$$

Mod-2 division by $P=110011$. Working left to right across the 8 possible alignments ($13-6+1=8$), XOR with $P$ whenever the current leading bit is 1, otherwise bring the next bit down unchanged:

Mod-2 (XOR) division trace
Position	Leading bit	Action	Working register after this step
0	1	XOR with $P$	0010111100000
1	0	bring down	0010111100000
2	1	XOR with $P$	0001110000000
3	1	XOR with $P$	0000010110000
4	0	bring down	0000010110000
5	1	XOR with $P$	0000001111100
6	1	XOR with $P$	0000000011010
7	0	bring down	0000000011010

Two independent implementations (a bitwise sliding-window XOR pass, and an integer shift-and-XOR pass) agree on every intermediate row.

Remainder = CRC. The final 5 bits of the working register are the remainder: $$\text{CRC} = \boxed{11010}.$$
Self-check. The transmitted frame is $T = M \Vert \text{CRC} = 1110001111010$. Dividing $T$ by $P$ (mod-2) gives a remainder of $00000$, confirming $T$ is exactly divisible by $P$ as required for a valid CRC codeword.

Final results — Question 4
Quantity	Result
Redundancy length $r$	5 bits
Augmented message $M\cdot2^{r}$	1110001100000
CRC (remainder)	11010
Transmitted frame $T = M\Vert\text{CRC}$	1110001111010

Topic: Cyclic Redundancy Check via mod-2 polynomial division.

Key relations: $r = \deg(G(x))$; $T(x) = M(x)\cdot x^{r} \oplus R(x)$, where $R(x)$ is the remainder of $M(x)\cdot x^{r}$ divided (mod 2) by the generator $G(x)$; the receiver accepts iff $T(x) \bmod G(x) = 0$.

Why this works: appending $r$ zero bits shifts the message up by exactly the generator's degree, matching the transmitted codeword's degree to the check field; dividing with XOR (addition/subtraction without carry — arithmetic over $GF(2)$) rather than ordinary binary subtraction is what makes CRC a linear, easily hardware-implementable code. The receiver runs the identical division on the received bits, and a non-zero remainder flags a detected transmission error.

Common pitfall: performing an ordinary borrow-based long division instead of XOR (no-borrow) division, or forgetting to zero-extend the message by $r$ bits before dividing — both silently produce the wrong remainder.

Source: Kurose & Ross, Computer Networking: A Top-Down Approach, 7th ed., Ch.5 §5.2 (Error-Detection and -Correction Techniques — Cyclic Redundancy Check).

Question 4 of 7: Cyclic Redundancy Check (CRC)

Question 4: Cyclic Redundancy Check (CRC) (20 marks)