GATE CS 2017 Set 2 Q34 — Data Link Layer: Framing, Error Detection, MAC, Ethernet Bridging

To find the minimum Hamming distance $p$ and the error-correcting capability $q$ of the given binary code, we analyze the set of valid codewords:

• $C_1 = 00000$
• $C_2 = 01011$
• $C_3 = 10101$
• $C_4 = 11110$

Step 1: Find the Minimum Hamming Distance ($p$)

The Hamming distance between two codewords is the number of positions at which the corresponding bits differ. Let's compute the pairwise Hamming distances:

• $d(C_1, C_2) = \text{weight}(01011) = 3$
• $d(C_1, C_3) = \text{weight}(10101) = 3$
• $d(C_1, C_4) = \text{weight}(11110) = 4$
• $d(C_2, C_3) = \text{weight}(01011 \oplus 10101) = \text{weight}(11110) = 4$
• $d(C_2, C_4) = \text{weight}(01011 \oplus 11110) = \text{weight}(10101) = 3$
• $d(C_3, C_4) = \text{weight}(10101 \oplus 11110) = \text{weight}(01011) = 3$

The minimum Hamming distance $p$ is the minimum of all pairwise distances:

Step 2: Find the Error-Correction Capability ($q$)

To correct up to $q$ errors, the minimum Hamming distance $d_{\text{min}}$ of the code must satisfy the following relation:

Substituting $d_{\text{min}} = p = 3$ into the inequality:

Thus, the maximum number of erroneous bits that can be corrected is $q = 1$.

Therefore, $p = 3$ and $q = 1$, which corresponds to Option A.