Computer Networks · TEE · read

Hamming-distance working · example 1

Unit 3 · Errors, block coding and CRC

TEE · Unit 3 before ALOHA · current syllabus 702AI0C023

Practice question. For the binary codewords C1=1001101, C2=1110001, C3=1010101, find every pairwise Hamming distance, the minimum distance, and the guaranteed error detection/correction limits. [5 practice marks]

Answer

Given

CodewordBits
C11001101
C21110001
C31010101

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 C21001101111000101111004
C1 vs C31001101101010100110002
C2 vs C31110001101010101001002

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.