Computer Networks · TEE · papers

Q4(a) · CRC and corrupted frame

2024-12-06 · Final 2024-25 / Re-exam 2023-24

Actual paper; 100 marks attempted. Current-syllabus alignment is stated per question.

Q4(a). Given the data bit sequence 1001100 and the CRC polynomial x^3+x^2+1, calculate the transmission sequence. Suppose the 2nd bit from the left is inverted during transmission. Illustrate how the receiver will detect the error. [10 marks]

Answer

Given

Data = 1001100; generator bits = 1101; degree r = 3.

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

1001100 → 1001100000

Step 2. Perform XOR division

Leading position	Before XOR	Aligned generator	After XOR
1	1001100000	1101000000	0100100000
2	0100100000	0110100000	0010000000
3	0010000000	0011010000	0001010000
4	0001010000	0001101000	0000111000
5	0000111000	0000110100	0000001100
7	0000001100	0000001101	0000000001

Step 3. Build the frame

Remainder = 001. Transmit 1001100001.

Step 4. Divide the received frame

Position	Before	Generator	After
1	1001100001	1101000000	0100100001
2	0100100001	0110100000	0010000001
3	0010000001	0011010000	0001010001
4	0001010001	0001101000	0000111001
5	0000111001	0000110100	0000001101
7	0000001101	0000001101	0000000000

Receiver remainder = 000. No error is detected; this is not a guarantee that every possible corruption is detectable.

Step 5. Invert bit 2 from the left

1001100001 becomes 1101100001.

Position	Before	Generator	After
1	1101100001	1101000000	0000100001
5	0000100001	0000110100	0000010101
6	0000010101	0000011010	0000001111
7	0000001111	0000001101	0000000010

Remainder = 010, which is nonzero: reject the frame and request recovery according to the error-control protocol.