Computer Networks · TEE · mocks

Q2A · Error detection and correction

TEE mock C · full paper

TEE · 100 attempted marks · solutions for every choice · current syllabus 702AI0C023

TEE practice mock · Q2A. Explain block coding and redundancy. For the binary codewords C1=0000000, C2=1110000, C3=0011100, find every pairwise Hamming distance, the minimum distance, and the guaranteed error detection/correction limits. [10 mock marks]

Answer

Block coding maps each k-bit dataword to an n-bit codeword, adding n−k redundant bits. Only selected codewords are valid; their separation determines error-detection/correction capability.

Given

CodewordBits
C10000000
C21110000
C30011100

To find

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

Formula and why

d(a,b)=\mathrm{weight}(a\oplus b)LaTeX: d(a,b)=\mathrm{weight}(a\oplus b)
s=d_{\min}-1,\quad t=\lfloor(d_{\min}-1)/2\rfloorLaTeX: 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

PairFirstSecondXORDistance
C1 vs C20000000111000011100003
C1 vs C30000000001110000111003
C2 vs C31110000001110011011004

Step 2. Take the minimum

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

Step 3. Calculate the guarantees

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

Step 4. Justify geometrically

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

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