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

See example here..

good read if u want to grasp it completely.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+15 votes

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.

$$\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.

+11 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!

+1

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

See example here..

good read if u want to grasp it completely.

+3

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

+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

–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)

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)

+5

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.

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,691 questions

52,777 answers

183,437 comments

68,391 users