Computer Networks · TEE · papers

Q2A · Block coding and all pairwise distances

Final · 5 December 2025

TEE · Actual TEE paper · all questions · current syllabus 702AI0C023

Actual PYQ · Q2A. (i) Explain the block coding method for error detection and correction. (2 marks) (ii) Two binary codewords are used: C1=1001101 and C2=1110001. Compute their Hamming distance. (2 marks) (iii) C3=1010101 is added. Compute its pairwise distances from the other codewords. (2 marks) (iv) Based on the minimum Hamming distance, determine how many errors the code can detect and correct; justify your answer. (4 marks) [10 marks]

Answer

(i) Block coding. Map each k-bit dataword to a distinct n-bit codeword by adding n−k redundant bits. Only the valid codeword subset represents data. A received invalid pattern detects an error; sufficiently separated codewords permit unique correction within the guaranteed radius. For a chosen code, the minimum Hamming distance measures that separation.

Given

Codeword	Bits
C1	1001101
C2	1110001
C3	1010101

To find

All pair distances, dmin and the maximum guaranteed numbers of errors.

Formula and why

d(a,b)=\mathrm{weight}(a\oplus b)

s=d_{\min}-1,\quad t=\lfloor(d_{\min}-1)/2\rfloor

XOR exposes differing positions. Use the closest codeword pair, because it is the weakest separation in the code.

Step-by-step solution

Step 1. XOR every distinct pair

Pair	First	Second	XOR	Distance
C1 vs C2	1001101	1110001	0111100	4
C1 vs C3	1001101	1010101	0011000	2
C2 vs C3	1110001	1010101	0100100	2

Step 2. Take the minimum

dmin = min(4, 2, 2) = 2.

Step 3. Calculate the guarantees

Detect = 2−1 = 1; correct = floor((2−1)/2) = 0.

Step 4. Justify geometrically

2 bit changes can reach another valid codeword, so only 1 are guaranteed detectable. Correction regions require 2t < 2.

Final answer: dmin=2; detect up to 1 errors; correct up to 0 errors.

Source: Final · 5 December 2025, original question paper page 1. Original marks retained; solution independently authored.