Question about Hamming Code

[vick5821]

The message below has been coded in the Hamming code and transmitted through a noisy channel. Decode the message assuming that a single error has occured in each word code :
1001001,0111001

How to solve it ? they didnt sspecify either odd or even parity ?

 

[(*steve*)]

Well, you can tell that there is not another parity bit (and there's 2 ways to do that)

Look up hamming code. for each 4 bits there are three parity bits. You can detect and correct a 1 bit change.

 

[Harald Kapp]

Each data word has 7 bits.
Look here (http://en.wikipedia.org/wiki/Hamming_code), there is only one Hamming code which generates 7 bits.Form this information you can find out the number of data bits and of parity bits. You can then check for the error and correct the data.

Even or Odd parity doesn't matter. Since you know, that only one bit is wrong, you can find out which type of parity has been used by trial. You start by assuming one tpye of parity (even or odd). If the number of errors is >1, then change to the other type of parity.

The information you have is already sufficient to solve the problem.

Harald

 

[vick5821]

I dun understand..let me think about it

 

[(*steve*)]

Have a look at the wikipedia article. They show a 15 bit signal I think. Just consider the leftmost 7 bits because that's what you have.

You will notice that there are parity bits spread through the data. In your case it's the first, second, and fourth bits.

The first bit contains the parity of bit 1, 3, 5, and 7

The second bit contains the parity of bits 2, 3, 6, and 7

The fourth bit contains the parity of bits 4, 5, 6, and 7.

(If you write the bit numbers down in binary, you can see that each parity bit corresponds to locations where the corresponding bit is 1)

321
001 = 1 (P1)
010 = 2 (P2)
011 = 3 (D1) (covered by P1 and P2)
100 = 4 (P3)
101 = 5 (D2) (covered by P1 and P3)
110 = 6 (D3) (covered by P2 and P3)
111 = 7 (D4) (covered by P1, P2, and P3)

Notice that I have numbered the bit positions in binary and labelled the columns from LSB to MSB.

Where Column 1 is 1, that bit is covered by P1

Where Column 2 is 1, that bit is covered by P2

Where Column 3 is 1, that bit is covered by P3

P1, P2, and P3 are in the position where *ONLY* the corresponding bit is 1.

So all you need to do is write down all the bits next to this, then calculate what the parity bits should be. If they're all right, the message is assumed to be OK. If they're not OK, you need to flip a single bit to fix them.

If only 1 parity bit is wrong, it's the parity bit that needs flipping.

If 2 parity bits are wrong, you need to flip the data bit that is covered ONLY by those 2 parity bits.

Both rules can be generalised to cover any situation by saying that the bit which needs to be flipped is the one covered by ONLY the parity bits which are wrong.

If you don't know whether the parity is odd or even, there are 2 possible solutions to each problem.

Does that help?