Computer Networks · TEE · papers
Q5(b) · CRC and damaged message
2024-02-06 · AI-only Sem V variant
Exact historical variant. Current-syllabus questions solved; excluded topics and source limitations stated.
Q5(b). For M=11010110101 and G(x)=x⁴+x²+1, calculate CRC and transmitted message. If one bit changes (the paper illustrates 11010110101→11010111101), can the receiver detect it? Show the receiver check using the original appended CRC. [5 marks]
Answer
Given
Data = 11010110101; generator bits = 10101; degree r = 4.
To find
CRC remainder, complete transmitted frame and receiver check; then detect the specified bit inversion.
Formula and why
Append r zeros, divide using XOR (modulo 2), and replace those zeros with the r-bit remainder. XOR has no borrowing or carrying. A valid received codeword has remainder zero; the receiver does not append new zeros.
Step 1. Append zeros
11010110101 → 110101101010000
Step 2. Perform XOR division
| Leading position | Before XOR | Aligned generator | After XOR |
|---|---|---|---|
| 1 | 110101101010000 | 101010000000000 | 011111101010000 |
| 2 | 011111101010000 | 010101000000000 | 001010101010000 |
| 3 | 001010101010000 | 001010100000000 | 000000001010000 |
| 9 | 000000001010000 | 000000001010100 | 000000000000100 |
Step 3. Build the frame
Remainder = 0100. Transmit 110101101010100.
Step 4. Divide the received frame
| Position | Before | Generator | After |
|---|---|---|---|
| 1 | 110101101010100 | 101010000000000 | 011111101010100 |
| 2 | 011111101010100 | 010101000000000 | 001010101010100 |
| 3 | 001010101010100 | 001010100000000 | 000000001010100 |
| 9 | 000000001010100 | 000000001010100 | 000000000000000 |
Receiver remainder = 0000. No error is detected; this is not a guarantee that every possible corruption is detectable.
Step 5. Invert bit 8 from the left
110101101010100 becomes 110101111010100.
| Position | Before | Generator | After |
|---|---|---|---|
| 1 | 110101111010100 | 101010000000000 | 011111111010100 |
| 2 | 011111111010100 | 010101000000000 | 001010111010100 |
| 3 | 001010111010100 | 001010100000000 | 000000011010100 |
| 8 | 000000011010100 | 000000010101000 | 000000001111100 |
| 9 | 000000001111100 | 000000001010100 | 000000000101000 |
| 10 | 000000000101000 | 000000000101010 | 000000000000010 |
Remainder = 0010, which is nonzero: reject the frame and request recovery according to the error-control protocol.