GATE 2021 CS (CS1) – Question 39
Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is $d_8d_7d_6d_5c_8d_4d_3d_2c_4d_1c_2c_1$, where the data bits and the check bits are given in the following tables:
Data bits: $d_8=1, d_7=1, d_6=0, d_5=x, d_4=0, d_3=1, d_2=0, d_1=1$
Check bits: $c_8=y, c_4=0, c_2=1, c_1=0$
Which one of the following choices gives the correct values of $x$ and $y$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $x$ is 0 and $y$ is 0.
Explanation
The codeword is laid out from position 12 down to position 1:
| pos | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| bit | $d_8$ | $d_7$ | $d_6$ | $d_5$ | $c_8$ | $d_4$ | $d_3$ | $d_2$ | $c_4$ | $d_1$ | $c_2$ | $c_1$ |
| val | 1 | 1 | 0 | $x$ | $y$ | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
Each check bit $c_k$ makes the parity (even) of all positions whose index has bit $k$ set equal to 0.
- **$c_1$** covers positions 1, 3, 5, 7, 9, 11: $c_1+d_1+d_2+d_4+d_5+d_7=0+1+0+0+x+1=x$ must be even, so $x=0$.
- **Check $c_2$** (positions 2, 3, 6, 7, 10, 11): $1+1+1+0+0+1=4$, even. Consistent.
- **Check $c_4$** (positions 4, 5, 6, 7, 12): $0+0+1+0+1=2$, even. Consistent.
- **$c_8$** covers positions 8, 9, 10, 11, 12: $y+x+d_6+d_7+d_8=y+0+0+1+1=y$ must be even, so $y=0$.
So $x=0,\ y=0$: option (A).
More Data Link Layer: Error Detection, Medium Access Control, Flow Control questions
- GATE 2019 CS Q39
- GATE 2018 CS Q65
- GATE 2015 CS (CS1) Q36
- GATE 2015 CS (CS1) Q39
- GATE 2016 CS (CS1) Q65
- GATE 2017 CS (CS1) Q42
All Data Link Layer: Error Detection, Medium Access Control, Flow Control questions →