search
Log In
23 votes
3.4k views
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.
in Computer Networks
edited by
3.4k views

6 Answers

19 votes
 
Best answer

Here, answer is yes. There is error in This message. Error is in bit $6$.

How to calculate it? First of all reverse given input to get it in correct position from $1$ to $7$.

$0110001$

$\text{Bit-1, Bit-2 & Bit-4}$ are partity bits.

Calculating position of error $\Rightarrow$

$\text{$\large c_4 c_2 c_1$}$

$\text{1   1   0}$

Here, $c4 = bit4\oplus bit5 \oplus bit6 \oplus bit7=0\oplus 0\oplus 0\oplus 1=1$
                   $\text{ (Taking Even parity )}$

          $c2  = bit2\oplus bit3\oplus bit6\oplus bit7=1\oplus 1\oplus 0\oplus 1=1$

          $c1= bit1\oplus bit3\oplus bit5\oplus bit7=0\oplus 1\oplus 0\oplus 1=0$

Reference: $\Rightarrow$ https://en.wikipedia.org/wiki/Hamming%287,4%29

When you correct bit $6$.

You get message as $0110011$.

If you calculate $\large c_4,c_2,c_1$ all will be $0$ now!


edited by
2

http://codegolf.stackexchange.com/questions/45684/correct-errors-using-hamming7-4

See example here..

good read if u want to grasp it completely.

1
@Rajesh This link is so "Big" to read :P
1
if assume odd parity then bit 1 has error ,it should be zero
1
by default which one to choose odd or given ?
6

The bits at which correct bits depend, I think is given wrong!!

$C_1: 1\oplus3\oplus5\oplus7 $

$C_2:2\oplus3\oplus6\oplus7$

$C_4:4 \oplus5\oplus6\oplus7$

C1 is like begin from data bit 1, take 1 bit, leave 1 bit, then take 1 bit and so on.

C2 is like from bit position 2 take 2 bits, then leave next two bits, then take next two bits and so on....

Easy and nice to read with a good Example

 

http://logos.cs.uic.edu/366/notes/ErrorCorrectionAndDetectionSupplement.pdf

 

1
if we take the odd parity then bit 1 should be corrected

not the bit 6
0
Yes you are correct. But if nothing is mentioned in the question, then we take Even parity by default.
11 votes

Error bit is 6 ... Msg is 1100110


edited by
4 votes

Yes there is an error in this message at 6-bit position so the correct message is 1100110

2 votes
6th bit is having error both parity bit 2 and 4 support this so 6 bit need to be 1 and data must be 1100110
0 votes
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.
–1 vote
Answer: Bit 5 has the error. It should be 1.

Here, parity bits are 1,2,4 (power of 2).

Hamming code based on data bits received = 110
Bit 1 = Bit 3 $\oplus$ Bit 5 = 1 $\oplus$ 0 = 1. (XOR of all bits having the least significant digit as 1)
Bit 2 = Bit 3 $\oplus$ Bit 6 = 1 $\oplus$ 0 = 1. (XOR of all bits having the second least significant digit as 1)
Bit 7 = Bit 4 $\oplus$ Bit 5 $\oplus$ Bit 6 = 0 $\oplus$ 0 $\oplus$ 0 = 0. (XOR of all bits having the third least significant digit as 1)

But the received message has Bit 1 = 0, Bit 2 = 1, Bit 7 = 1 (Actual hamming code)

Bit error = Hamming code based on data bits received $\oplus$ Actual hamming code = 110 $\oplus$ 011 = 101 (i.e. Bit 5 has the error)
6

the answer is wrong.it should be bit 6.if you consider forouzan's book of data networking, the answer should be bit 6.then the correct message will be 1100110.

her the parity bits are bit 1,bit 2, bit 4.

now to calculate bit 1=bit1⊕bit3⊕bit5⊕bit7=0⊕1⊕0⊕1=0

again,to calculate bit 2=bit2⊕bit3⊕bit6⊕bit7=1⊕1⊕0⊕1=1

again,to calculate bit 3=bit4⊕bit5⊕bit6⊕bit7=0⊕0⊕0⊕1=1

therefore ,the error is at the position 110 = 6 

please ,think of it mr @jon_snow.

1

Sudipta Paul

Your answer is correct !

0
is it correct?
0
yes it is
0

Superb way to solve! @Sudipta Paul By this we can get the answer in just one go.

Thank u !

Related questions

1 vote
0 answers
1
1 vote
0 answers
2
315 views
To provide more reliability than a single parity bit can give, an error-detecting coding scheme uses one parity bit for checking all the odd-numbered bits and a second parity bit for all the even-numbered bits. What is the Hamming distance of this code?
asked Mar 16, 2019 in Computer Networks ajaysoni1924 315 views
2 votes
2 answers
3
690 views
If the Hamming distance between a dataword and the corresponding codeword is three, there are _____ bits in error. A) 5 B) 4 C) 3 D) none of the above
asked Nov 19, 2018 in Computer Networks iarnav 690 views
1 vote
1 answer
4
735 views
Let C be a binary linear code with minimum distance 2t + 1 then it can correct upto _____ bits of error. A t + 1 B t C t - 2 D t / 2
asked Jun 15, 2018 in Computer Networks bts 735 views
...