GATE CSE 1994 | Question: 9

Question

Following $7$ bit single error correcting hamming coded message is received.
$$\overset{7\qquad 6\qquad 5 \qquad 4\qquad 3 \qquad 2 \qquad 1}{\boxed{1 \qquad 0\qquad 0 \qquad 0 \qquad 1  \qquad 1 \qquad 0}} \qquad \overset{\textbf{bit No.}}{\boxed{X}}$$
Determine if the message is correct (assuming that at most $1$ bit could be corrupted). If the message contains an error find the bit which is erroneous and gives correct message.

Answer 1

Number the bits as given in the question :

Now take only those number in which bit is 1 ( in this case 7, 3, 2). Write them in binary and apply XOR. If we get 0 there is no error. If we get a number that is the bit where error is present.

7 – 111

3 – 011

2 – 010

Result : 110( which is 6).

So error is present in bit 6.

Answer 2

 

d7	d6	d5	p4	d3	p2	p1
1	0	0	0	1	1	0

 

from the above table,

p1=0

p2=1

p4=0

now use parity bits to check whether there is any error

p1=d3 d5 d7 =1 0 1 =  0  (correct),

  means d3 d5 d7 are correct

p2= d3 d6 d7 = 1 0 1 = 0  (wrong), which is actually 1

 means any of d3 d6 d7 is wrong, but we know from p1 that d3 & d7 are correct. i,e d6 is wrong

so, error found at 6th position

 

Answer 3

To know if there is an error in the message or not what we can do is 

first of all write down the message and then check for partiy bits value i.e 

1 0 0 0 1 1 0

there are 3 parity bits. How ? by using 2 to the power n 

2 to the power 0 = 1 

2 to the power 1 = 2

2 to the power 2 = 4

2 to the power 3 = 8

and so on.

so here parity bits are at position 1, 2 and 4.

now calculate the parity bits value of P1, P2 and P4

for P1 = value of bit at position 1 from right, value of bit at position 3 from right, value of bit at position 5 from right, value of bit at position 7 from right 

i.e  0,1,0,1 

since there is no mentioning of parity case i.e even or odd parity we have to consider we take by default the parity case to be even [If you don’t understand it please check for Hamming code]

so 0, 1, 0, 1 have even number of 1’s therefore the value of P1 = 0

 

Similarly, for P2 = value of bit at position 2 from right, value of bit at position 3 from right, value of bit at position 6 from right, value of bit at position 7 from right

i.e 1, 1,0,1

it has odd number of ones therefore P2 should be 1 to make it a even parity.

for P3 = value of bit at position 4 from right, value of bit at position 5 from right, value of bit at position 6 from right, value of bit at position 7 from right

i.e 0,0,0,1 

it has odd number of ones therefore P3 should be 1

now if all the parity bits would have been come out as 0 then there would be no error but in this case P2 and P3 are 1. That means there is an error in the message.

 

Now how to know if which bit contains the error.

simply write P3, P2, P1 in sequence i.e 110 and calculate the decimal value of it

110 in decimal is 6

 

 

and therefore the 6^th bit contains an error. and accordingly then you can give the correct message by replacing the erroneous bit and correct message is 1 1 0 0 1 1 0

 

 

Answer 4

To know if there is an error in the message or not what we can do is

first of all write down the message and then check for partiy bits value i.e

1 0 0 0 1 1 0

there are 3 parity bits. How ? by using 2 to the power n

2 to the power 0 = 1

2 to the power 1 = 2

2 to the power 2 = 4

2 to the power 3 = 8

and so on.

so here parity bits are at position 1, 2 and 4.

now calculate the parity bits value of P1, P2 and P4

for P1 = value of bit at position 1 from right, value of bit at position 3 from right, value of bit at position 5 from right, value of bit at position 7 from right

i.e  0,1,0,1

since there is no mentioning of parity case i.e even or odd parity we have to consider we take by default the parity case to be even [If you don’t understand it please check for Hamming code]

so 0, 1, 0, 1 have even number of 1’s therefore the value of P1 = 0

 

Similarly, for P2 = value of bit at position 2 from right, value of bit at position 3 from right, value of bit at position 6 from right, value of bit at position 7 from right

i.e 1, 1,0,1

it has odd number of ones therefore P2 should be 1 to make it a even parity.

for P3 = value of bit at position 4 from right, value of bit at position 5 from right, value of bit at position 6 from right, value of bit at position 7 from right

i.e 0,0,0,1

it has odd number of ones therefore P3 should be 1

now if all the parity bits would have been come out as 0 then there would be no error but in this case P2 and P3 are 1. That means there is an error in the message.

 

Now how to know if which bit contains the error.

simply write P3, P2, P1 in sequence i.e 110 and calculate the decimal value of it

110 in decimal is 6

 

 

and therefore the 6th bit contains an error. and accordingly then you can give the correct message by replacing the erroneous bit and correct message is 1 1 0 0 1 1 0