Author Topic: Error-correction Hamming codes question...  (Read 3891 times)

0 Members and 1 Guest are viewing this topic.

Offline Adriweb

  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1708
  • Rating: +229/-17
    • View Profile
    • TI-Planet.org
Error-correction Hamming codes question...
« 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 :

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.
« Last Edit: November 11, 2012, 09:10:37 am by adriweb »
My calculator programs
TI-Planet.org co-admin.
TI-Nspire Lua programming : Tutorials  |  API Documentation

Offline ElementCoder

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 611
  • Rating: +42/-2
    • View Profile
Re: Error-correction Hamming codes question...
« Reply #1 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 :)

Some people need a high five in the face... with a chair.
~EC

Offline Adriweb

  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1708
  • Rating: +229/-17
    • View Profile
    • TI-Planet.org
Re: Error-correction Hamming codes question...
« Reply #2 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 :



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 ?
« Last Edit: November 10, 2012, 03:16:05 pm by adriweb »
My calculator programs
TI-Planet.org co-admin.
TI-Nspire Lua programming : Tutorials  |  API Documentation

Offline phenomist

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 132
  • Rating: +46/-3
    • View Profile
Re: Error-correction Hamming codes question...
« Reply #3 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.
Level Designer for Graviter

[Disclaimer: I can't program for my life.]

Offline Adriweb

  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1708
  • Rating: +229/-17
    • View Profile
    • TI-Planet.org
Re: Error-correction Hamming codes question...
« Reply #4 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 ;)
« Last Edit: November 10, 2012, 05:54:41 pm by adriweb »
My calculator programs
TI-Planet.org co-admin.
TI-Nspire Lua programming : Tutorials  |  API Documentation

Offline phenomist

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 132
  • Rating: +46/-3
    • View Profile
Re: Error-correction Hamming codes question...
« Reply #5 on: November 10, 2012, 05:51:03 pm »
5 mod 2 = 1
6 mod 2 = 0
7 mod 2 = 1
5 mod 2 = 1
Level Designer for Graviter

[Disclaimer: I can't program for my life.]

Offline Adriweb

  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1708
  • Rating: +229/-17
    • View Profile
    • TI-Planet.org
Re: Error-correction Hamming codes question...
« Reply #6 on: November 10, 2012, 05:54:22 pm »
Ah, mod for each number, lol I feel bad :D
Thanks !
My calculator programs
TI-Planet.org co-admin.
TI-Nspire Lua programming : Tutorials  |  API Documentation