GATE CSE 2021 Set 1 | Question: 29

Question

Assume that a $12$-bit Hamming codeword consisting of $8$-bit data and $4$ check bits is $d_8d_7d_6d_5c_8d_4d_4d_3d_2c_4d_1c_2c_1$, where the data bits and the check bits are given in the following tables: $$\overset{\textbf{Data bits}}{\begin{array}{|c|c|c|c|}  \hline  d_{8} & d_{7} & d_{6} & d_{5} & d_{4} & d_{3} & d_{2} & d_{1} \\\hline 1 & 1 & 0 & x & 0 & 1 & 0 & 1 \\\hline \end{array}}\qquad \overset{\textbf{Check bits}}{\begin{array}{|c|c|c|c|} \hline  c_{8} & c_{4} & c_{2} & c_{1} \\\hline y & 0 & 1 & 0 \\\hline \end{array}}$$ Which one of the following choices gives the correct values of $x$ and $y$?

• A. $x$ is $0$ and $y$ is $0$
• B. $x$ is $0$ and $y$ is $1$
• C. $x$ is $1$ and $y$ is $0$
• D. $x$ is $1$ and $y$ is $1$

Comments

yup, i got it right A is the answer.

---

Well explained 

https://gateoverflow.in/357422/gate-cse-2021-set-1-question-29?show=370477#a370477

---

does hamming code in syllabus for gate 2025 ?

Answer 1

First I wanna point out a mistake here, it says hamming codeword is 12-bit long, but given codeword sequence is of 13-bit due to repetition of d4 twice (I believe this is a typing error, either they should have write a 13-bit codeword, or d4 occurs only once in this codeword),  also 13-bit codeword is very unlikely as it is given in this question, reason: we put check bits at $2^i \ \forall i\ \in  N $,

But in the given codeword c8 is at 9th position taken from RHS)

---

Case 1: assume it’s a 12-bit codeword and d4 is repeated twice by mistake,

12	11	10	9	8	7	6	5	4	3	2	1
d8	d7	d6	d5	c8	d4	d3	d2	c4	d1	c2	c1
1	1	0	x	y	0	1	0	0	1	1	0

(1)  $c_1 + d_1 + d_2 + d_4 + d_5 +d_7$ should be of even parity

= 0 + 1 + 0 + 0 + x + 1 = x + 2,

x must be 0 for even parity.

(2)    $c_2 + d_1 + d_3 + d_4 + d_6 + d_7$ should be even

= 1 + 1 + 1 + 0 + 0 + 1 = 4 (yes)

(3)    $c_4 + d_2 + d_3 + d_4  + d_8$ should be even

=  0 + 0 + 1 + 0 + 1 = 2 (yes even)

(4)    $c_8 + d_5 + d_6 + d_7 + d_8$ should be even

= y + x + 0 + 1 + 1 = y + 2 (taking x=0) , for even parity, y should be 0

Hence if code work is of 12-bit, both x and y are 0.

A is correct here

---

Case 2: It’s a 13-bit codeword, (I don’t think this will be the case, because $c_8$ should be at position 8), but lets try anyway

13	12	11	10	9	8	7	6	5	4	3	2	1
d8	d7	d6	d5	c8	d4	d4	d3	d2	c4	d1	c2	c1
1	1	0	x	y	0	0	1	0	0	1	1	0

(1)     $c_1 + d_1 + d_2 + d_4 + c_8 + d_6 + d_8$ = 0 + 1 + 0 + 0 + y + 0 + 1 = y+2, y will be 0.

(2)     $c_2 + d_1 + d_3 + d_4 + d_5 + d_6$ = 1 + 1 + 1 + 0 + x + 0 = x + 3, x will be 1

We may conclude C is correct in this case. but i just wanna check it further for other parity bits whether they holds good or not

(3)   $ c_4 + d_2 + d_3 + d_4 + d_7 +d_8$ = 0 + 0 + 1 + 0 + 1 + 1 = 3 (odd parity) , $c_4$ should be 1 for this to be true, which it isn’t)

This case fails, so C is definitely not the answer.

Comments

@Lakshmi Narayana404

Here in this question, look at C2(given as 1).

C2 = d1 + d3 + d4 + d6 + d7 = 11001(has odd number of one’s)

To make it even(in case of even parity), we should add 1. Means C2 = 1.

To make it odd(in case of odd parity), we will add 0, Means c2 = 0

Since C2 is 1, we can say that they are asking even parity.

---

How are you guys doing ?

c1 = d1+d3+d4+d6+d7 

c2 = d1+d3+d4+d6+d7

​​​​​​etc ? Please explain!

---

Hey watch the 3Blue1Brown youtube video on hamming code. it has a different view point to solve the hamming code. it is easy to solve for any combination within a minute.
check with C1 first X=0; next check with C8 = 0.

Answer 2

Apart from the mistake in question, what I realize is that candidates often get confused on how to associate the redundant bits with the data words and why even we do so?

The idea is that the first redundant take and ignore alternatively i.e check if (c1 + d1 + d2 + d4 + d5 + d7) % 2 == 0.

The second redundant bit take and ignore 2 bits at a time i.e check if (c2 + d1 + d3 + d4 + d6 + d7) % 2 == 0.

The third 4-bits at a time.

The fourth 8 -bits at a time 

Following is an article with reference from the Florida International University page 

Answer 3

In this question, we need to find even parity. 

S1 => Parity/check bits will always be placed in powers of 2 positions (1,2,4,8 etc)

S2 => We now will draw a truth table for check bits, which will start in reverse order like C8 C4, C2, C1

S3 => Under C1 in the table, the places where C1 = 1, those places we need to find even parity. for C1 place 1,3,5,7,9,11 is where we need to check for even parity.

Same with all the other check bits

S4 => C8 will be tied with the positions 8,9,10,11,12, so we need to check those places for it

Note: When we are asked to put the parity bits, we need to reverse the check bits in the table and find the values again.