GATE CS 1992 Q01 — Data Link Layer: Framing, Error Detection, MAC, Ethernet Bridging

To find the required values, we break the problem into two parts:

1. Number of extra parity bits ($r$):
   For a Hamming code to correct $1$-bit errors, the number of parity bits $r$ for $m$ data bits must satisfy the Hamming rule:$$2^r \ge m + r + 1$$Given $m = 4$ data bits:$$2^r \ge 4 + r + 1 \implies 2^r \ge r + 5$$Testing values of $r$:
   • For $r = 2$: $2^2 = 4 \not\ge 7$
   • For $r = 3$: $2^3 = 8 \ge 8$ (Satisfied)
   Thus, the number of extra parity bits required is 3.
2. Minimum Hamming distance ($d_{\text{min}}$) for error detection:
   To detect up to $t$ errors, the minimum Hamming distance of the code must satisfy:$$d_{\text{min}} \ge t + 1$$For $3$-bit error detection ($t = 3$):$$d_{\text{min}} \ge 3 + 1 = 4$$Thus, the minimum distance required is 4.

Therefore, the blanks are filled with 3 and 4 respectively (represented as 3 : 4).