# Omnimaga

## General Discussion => Other Discussions => Math and Science => Topic started by: Adriweb on November 10, 2012, 02:18:30 pm

Title: Error-correction Hamming codes question...
Post by: Adriweb on November 10, 2012, 02:18:30 pm
Hi,

I have a test soon about a lot of things, including a part with error-correction Hamming codes.
I thought I had enough things to work on on my notes, but now it looks like I was wrong :/

I have this exercise (roughly translated from french) :

Quote
A transmission has been received, and the message is the following :  101111001101110

1) Determine the syndrome [word].
2) What's the 11-bit message that has been sent ?

So basically, I believe the structure of the message is :
101111001101110
_______P3__P2_P1P0
(non-bold are the actual content, with maybe an error ? ; bold are parity-check bits)

I believe the message contains an error because P3 is 0 while there are 5 "1" at its left, which would have given a "1" for P3.

How do I determine the syndrome ?
I've looked on wikipedia and such, and it looks like I have to multiply 2 vectors (one being the matrix H of the parity bits things, and the other one being the vector of the whole message), to find a syndrom vector indicating the error position ?
I'm not too sure how to do that in my case but here's what I tried :
(http://i.imgur.com/hy4KX.png)
which gave me [[5][6][7][5]].
But I rememebered that it's not really a multiplication here, since we have to replace the additions by a parity-check operation which turns out to be a xor.   -_-

Do you have an easy way (or rather, not time-consuming) to know what bit is wrong ?

I'm sure I could read a lot more lessons online and eventually find what I need but maybe you guys will know directly what to tell me :P
Thanks !

Edit : see 3rd post in this topic.
Title: Re: Error-correction Hamming codes question...
Post by: ElementCoder on November 10, 2012, 02:50:11 pm
This sounds complicated, what course is this? All I see is that the screenie is from an nspire screen :)
Title: Re: Error-correction Hamming codes question...
Post by: Adriweb on November 10, 2012, 03:00:30 pm
It's ... "Digital Electronics" (doesn't sound well in english :P)
1st year of Enginnering / 3rd year after baccalaureate.

by the way, I made myself a program to do what I said before ("But I rememebered that it's not really a multiplication here, since we have to replace the additions by a parity-check operation which turns out to be a xor.")

I got :

(http://i.imgur.com/e1WCG.png)

Which looks good, since when I change the 11th bit to 0, it says there are no more errors...

So, the final, error-corrected message would be : 101101001101110.

We dont have calculators allowed (well, they give us crappy scientifical ones), so how is that supposed to be done efficiently/quickly during an exam :o ?
Title: Re: Error-correction Hamming codes question...
Post by: phenomist on November 10, 2012, 03:46:49 pm
I think you can just check the parity of the resultant product, so [[5][6][7][5]] = [[1][0][1][1]], as desired. This is because xor on bits is basically addition mod 2.
Title: Re: Error-correction Hamming codes question...
Post by: Adriweb on November 10, 2012, 05:01:54 pm
I think you can just check the parity of the resultant product, so [[5][6][7][5]] = [[1][0][1][1]], as desired.

Thanks,

but how do you get from [[5][6][7][5]] to [[1][0][1][1]] here directly ?

(is it related to its binary representation, 1011000101011 ?)

Edit : ahem, I feel bad, it's mod for each number.

This is because xor on bits is basically addition mod 2.

Yep, I actually saw something about addition mod 2 but looking at example I only "saw" a xor being calculated ;)
Title: Re: Error-correction Hamming codes question...
Post by: phenomist on November 10, 2012, 05:51:03 pm
5 mod 2 = 1
6 mod 2 = 0
7 mod 2 = 1
5 mod 2 = 1
Title: Re: Error-correction Hamming codes question...
Post by: Adriweb on November 10, 2012, 05:54:22 pm
Ah, mod for each number, lol I feel bad :D
Thanks !