GATE CS 2021 Set 1 Q.39 (CS Q.29): Data Link Layer: Framing, Error Detection and Sliding Window

Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is $d_8 d_7 d_6 d_5 c_8 d_4 d_3 d_2 c_4 d_1 c_2 c_1$ , where the data bits and the check bits are given in the following tables:

Data bits
d8	d7	d6	d5	d4	d3	d2	d1
1	1	0	x	0	1	0	1

Check bits
c8	c4	c2	c1
y	0	1	0

Which one of the following choices gives the correct values of $x$ and $y$ ?

$x$ is 0 and $y$ is 0.

$x$ is 0 and $y$ is 1.

$x$ is 1 and $y$ is 0.

$x$ is 1 and $y$ is 1.

Official answer and solution

Official answer: A
From: Official GATE 2021 answer key

Solution

Set up parity check equations using 1-based bit indexing for standard Hamming code positions.

The 12-bit Hamming codeword structure places check bits at powers of 2 (positions 1, 2, 4, 8) and data bits at all other positions:

Position 1: $c_1$
Position 2: $c_2$
Position 3: $d_1$
Position 4: $c_4$
Position 5: $d_2$
Position 6: $d_3$
Position 7: $d_4$
Position 8: $c_8$
Position 9: $d_5$
Position 10: $d_6$
Position 11: $d_7$
Position 12: $d_8$

We are given the values:
$d_1 = 1, d_2 = 0, d_3 = 1, d_4 = 0, d_5 = x, d_6 = 0, d_7 = 1, d_8 = 1$
$c_1 = 0, c_2 = 1, c_4 = 0, c_8 = y$

Parity bit $c_1$ covers all positions whose binary representation has bit 0 set (1, 3, 5, 7, 9, 11):

c_1 = d_1 \oplus d_2 \oplus d_4 \oplus d_5 \oplus d_7

Substituting known values:

0 = 1 \oplus 0 \oplus 0 \oplus x \oplus 1 = x \oplus (1 \oplus 1) = x \oplus 0 = x \implies x = 0

Parity bit $c_8 = y$ covers positions whose binary representation has bit 3 set (8, 9, 10, 11, 12):

c_8 = d_5 \oplus d_6 \oplus d_7 \oplus d_8

With $x = 0$ , $d_5 = 0$ :

y = 0 \oplus 0 \oplus 1 \oplus 1 = 0

Thus, $x = 0$ and $y = 0$ , which matches option A.

Final answer

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

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 39 of 65, printed as CS Q.29
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