Computer Networks · TEE · mocks

Q2A · Error detection and correction

TEE mock A · 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=1111000, C3=0011110, 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
C21111000
C30011110

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 C20000000111100011110004
C1 vs C30000000001111000111104
C2 vs C31111000001111011001104

Step 2. Take the minimum

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

Step 3. Calculate the guarantees

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

Step 4. Justify geometrically

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

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