Computer Networks · TEE · papers
Q2A · CRC polynomial division
Re-exam · 4 February 2026
TEE · Actual TEE paper · all questions · current syllabus 702AI0C023
Actual PYQ · Q2A. Consider a message represented by the polynomial M(x)=x5+x4+x. Consider a generating polynomial G(x)=x3+x2+1. Generate a 3-bit CRC and show the transmitted frame. How is error detected by CRC? [10 marks]
Answer
Given
Message=110010; generator=1101; generator degree r=3. This is textbook systematic CRC with zero initial remainder and no reflection/final XOR.
To find
Exactly r CRC bits, the transmitted frame and receiver syndromes.
Formula and why
LaTeX: R=(M\,2^r)\bmod_2 G,\qquad T=(M\,2^r)\oplus RModulo-2 division uses aligned XOR, not ordinary decimal division.
Step-by-step solution
Step 1. Preserve all polynomial coefficients
Message bits=110010; generator bits=1101. Leading exponent is 3, so CRC length is 3.
Step 2. Append zeros
110010 followed by 3 zeros = 110010000.
Step 3. Perform each nonzero XOR subtraction
| Before | Aligned generator | After XOR |
|---|---|---|
| 110010000 | 110100000 | 000110000 |
| 000110000 | 000110100 | 000000100 |
Remainder padded to 3 bits = 100. Leading zero columns need no subtraction.
Step 4. Construct the transmitted frame
Message + CRC = 110010 + 100 = 110010100.
Step 5. Check the full frame
| Before | Aligned generator | After XOR |
|---|---|---|
| 110010100 | 110100000 | 000110100 |
| 000110100 | 000110100 | 000000000 |
Receiver remainder = 000; the uncorrupted frame passes.
Step 6. Demonstrate detection
Flip the last bit: 110010101. Dividing by 1101 leaves 001, which is nonzero, so this error is detected. A zero syndrome would mean no detected error, not proof of no corruption.
Final answer: CRC=100; transmitted frame=110010100; uncorrupted receiver remainder=000.
Scheme correction: the remainder 100 is correct, but one scheme line prints 110010111. The correctly appended frame is 110010100; the receiver division shown above verifies it.
Source: Re-exam · 4 February 2026, original question paper page 1. Original marks retained; solution independently authored.