GATE CS 2017 Set 2 Q.34 (CS Q.34): Data Link Layer: Framing, Error Detection and Sliding Window

Consider a binary code that consists of only four valid codewords as given below:
00000, 01011, 10101, 11110

Let the minimum Hamming distance of the code be $p$ and the maximum number of erroneous bits that can be corrected by the code be $q$ . Then the values of $p$ and $q$ are

$p = 3$ and $q = 1$

$p = 3$ and $q = 2$

$p = 4$ and $q = 1$

$p = 4$ and $q = 2$

Official answer and solution

Official answer: A
From: Official GATE 2017 answer key

Solution

Compute pairwise Hamming distances between all four codewords to find the minimum distance $p$ , then use the error-correction bound $q = \lfloor (p-1)/2 \rfloor$ .

Compute the pairwise Hamming distance (number of bit positions where codewords differ) for all pairs from $\{00000, 01011, 10101, 11110\}$ :

$d(00000, 01011) = 3$
$d(00000, 10101) = 3$
$d(00000, 11110) = 4$
$d(01011, 10101) = 4$
$d(01011, 11110) = 3$
$d(10101, 11110) = 3$

The minimum Hamming distance of the code is $p = \min(3, 3, 4, 4, 3, 3) = 3$ .

A code with minimum Hamming distance $p$ can correct up to $q$ errors, where:

q = \left\lfloor \frac{p - 1}{2} \right\rfloor = \left\lfloor \frac{3 - 1}{2} \right\rfloor = \left\lfloor \frac{2}{2} \right\rfloor = 1

Therefore, $p = 3$ and $q = 1$ , which matches option A.

Final answer

Common trap

Confusing error detection capability ( $p - 1 = 2$ ) with error correction capability ( $\lfloor (p - 1)/2 \rfloor = 1$ ).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 2
Question: 34 of 65, printed as CS Q.34
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source