Computer Networks · TEE · papers

Q4(c) · Hamming generation and correction

2024-12-06 · AI-only Sem V variant

Exact historical variant. Current-syllabus questions solved; excluded topics and source limitations stated.

Q4(c). Generate even-parity Hamming code for data 10101111. If the 7th bit is corrupted, give the received pattern and show how to detect and correct the error. [10 marks]

Answer

Source note: The paper does not state bit-position direction. The solution numbers positions from the right, matching current faculty slides; position 7 means the seventh from the right throughout.

Given

Data 10101111; even parity; one error at position 7 from the right.

To find

Codeword, received word, syndrome, corrected data.

Formula and why

2^r\ge m+r+1,\qquad m=8

Use the smallest r satisfying the inequality. Four checks label positions up to 12; parity positions are powers of two.

Solution

Step 1. Choose parity positions

r=3 gives 8 < 8+3+1=12, so it is insufficient. r=4 gives16 ≥8+4+1=13. Total length =12; reserve positions1,2,4,8.

Step 2. Insert data in the remaining positions

Position (right-to-left index)	12	11	10	9	8	7	6	5	4	3	2	1
Role	data	data	data	data	p8	data	data	data	p4	data	p2	p1
Data/parity	1	0	1	0	?	1	1	1	?	1	?	?

Step 3. Set each parity bit for an even total

Parity	Other covered positions	Other bits	Parity bit
1	3, 5, 7, 9, 11	1 + 1 + 1 + 0 + 0	1
2	3, 6, 7, 10, 11	1 + 1 + 1 + 1 + 0	0
4	5, 6, 7, 12	1 + 1 + 1 + 1	0
8	9, 10, 11, 12	0 + 1 + 0 + 1	0

Transmitted codeword = 101001110101.

Step 4. Flip position 7

Position7 changes 1→0. Received word = 101000110101.

Step 5. Compute the received syndrome

Parity check	Positions	XOR
1	1,3,5,7,9,11	1
2	2,3,6,7,10,11	1
4	4,5,6,7,12	1
8	8,9,10,11,12	0

s8s4s2s1 = 0111 = 7. Flip position7 back; all four checks become0. Remove positions1,2,4,8 to recover 10101111.