469,301 Members | 2,153 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,301 developers. It's quick & easy.

Hamming coding woes part 2...

72
Ok I am really confused now. Maybe its not my programming or something. Anyway just for background, the final part of my assignment is to encode a text with 8458 characters with huffman, encode it with hamming and send it through a channel simulator with 20% chance of error(1 become 0 and 0 become 1) and use hamming to correct the errors and compare with the original. and my result is always unreadable.

Since I can code and decode my huffman with out error, I narrowed it down to either my channel modeling is casuing the problem where i am give more than 1 error which hamming (7,4) can only fix or my hamming coder is the problem.

ok so my assignment says 0.2 chance of error which I do this

Expand|Select|Wrap|Line Numbers
  1. for(int i = 0; i < size; i++)
  2. {                                
  3.    double e = Math.random();
  4.  
  5.    if(e > errorPercent)
  6.    {
  7.       output += (char)text[i];
  8.    }
  9.    else
  10.    {                    
  11.       if((char)text[i] == '1')
  12.       {
  13.          output += '0';
  14.       }
  15.       else
  16.       {
  17.          output += '1';
  18.       }
  19.    }                                
  20. }
also on hamming, i found a few different version on the net and was wondering which the right one?

Where a 4 bit data = b1b2b3b4 and p1p2p3 are the parity bits
I can do it b1b2b3b4p1p2p3 or b1b2b3p1b4p2p3 and even more ways to decode and correct it.

Really confused here so hope someone can point me in the correct direction...

Thanks in advance...
Aug 8 '07 #1
21 4462
JosAH
11,448 Expert 8TB
Please note that order of the parity/data bits is important: the parity bits 'control'
themselves as well when indexed properly. Google for the correct order of those
bits when (7,4) encoding.

kind regards,

Jos
Aug 8 '07 #2
KWSW
72
Please note that order of the parity/data bits is important: the parity bits 'control'
themselves as well when indexed properly. Google for the correct order of those
bits when (7,4) encoding.

kind regards,

Jos
i did... and i found a few versions thats why i am rather confused now...

I found b1b2b3b4p1p2p3, b1b2b3p1b4p1p2, p3p2b4p1b3b2b1 so far...
and with different kinds of orders I get different kinds of ways to check for errors...

And that is making me more confused...
Aug 8 '07 #3
KWSW
72
here is my logic for encoding and decoding.

encoding:


Expand|Select|Wrap|Line Numbers
  1. Data           = b1 b2 b3 b4
  2. Parity         = p1 p2 p3
  3. Hamming        = b1 b2 b3 p1 b4 p2 p3
  4.                = h7 h6 h5 h4 h3 h2 h1
  5.  
  6. p1 = b1 XOR b3 XOR b4;
  7. p2 = b1 XOR b2 XOR b4;
  8. p3 = b1 XOR b2 XOR b3;
  9.  
  10.  
decoding:

Expand|Select|Wrap|Line Numbers
  1. using   h7 h6 h5 h4 h3 h2 h1
  2. or      b1 b2 b3 p1 b4 p2 p3
Expand|Select|Wrap|Line Numbers
  1. correct code table = {"0000000","0000111","0011001","0011110","0101010",
  2. "0101101","0110011","0110100","1001011","1001100","1010010","1010101",
  3. "1100001","1100110","1111000","1111111"};  
Check if its in the correct code table. If it is return h7 h6 h5 h3

if not add Correct Codes with a difference in Hamming Weight of 1 to a vector v.

Check for Correct Codes with a difference in Hamming Distance of 1 from vector v.

if there is a match(input code and code from vector v has a distance of 1),
return h7 h6 h5 h3 as corrected code.

if not return h7 h6 h5 h3 from input as code that cannot be corrected.
Aug 9 '07 #4
JosAH
11,448 Expert 8TB
[quote=KWSW]
Expand|Select|Wrap|Line Numbers
  1. Data           = b1 b2 b3 b4
  2. Parity         = p1 p2 p3
  3. Hamming        = b1 b2 b3 p1 b4 p2 p3
  4.                = h7 h6 h5 h4 h3 h2 h1
  5.  
  6. p1 = b1 XOR b3 XOR b4;
  7. p2 = b1 XOR b2 XOR b4;
  8. p3 = b1 XOR b2 XOR b3;
  9.  
  10.  
That most definitely is not correct, i.e. the parity bits should also check the
parity bits themselves (that's the clue of the trick). Google for the correct (7,4)
Hamming en/decoding.

kind regards,

Jos
Aug 9 '07 #5
KWSW
72
[quote=JosAH]
Expand|Select|Wrap|Line Numbers
  1. Data           = b1 b2 b3 b4
  2. Parity         = p1 p2 p3
  3. Hamming        = b1 b2 b3 p1 b4 p2 p3
  4.                = h7 h6 h5 h4 h3 h2 h1
  5.  
  6. p1 = b1 XOR b3 XOR b4;
  7. p2 = b1 XOR b2 XOR b4;
  8. p3 = b1 XOR b2 XOR b3;
  9.  
  10.  
That most definitely is not correct, i.e. the parity bits should also check the
parity bits themselves (that's the clue of the trick). Google for the correct (7,4)
Hamming en/decoding.

kind regards,

Jos
the problem is that I have no idea which is the correct one. so many floating around the internet.
Aug 9 '07 #6
JosAH
11,448 Expert 8TB
[quote=KWSW]

the problem is that I have no idea which is the correct one. so many floating around the internet.
Have a look at this one, it's definitely correct.

kind regards,

Jos
Aug 9 '07 #7
KWSW
72
[quote=JosAH]

Have a look at this one, it's definitely correct.

kind regards,

Jos
taking a look at this one and am wondering if java can do matrix of do i need to build a matrix class myself...
Aug 9 '07 #8
JosAH
11,448 Expert 8TB
[quote=KWSW]

taking a look at this one and am wondering if java can do matrix of do i need to build a matrix class myself...
Nah, that's just a convenient linear algebra notation for just bit fiddling; you don't
want to take that direction, i.e. simple bit manipulation is much more efficient here.

kind regards,

Jos
Aug 9 '07 #9
KWSW
72
[quote=JosAH]

Nah, that's just a convenient linear algebra notation for just bit fiddling; you don't
want to take that direction, i.e. simple bit manipulation is much more efficient here.

kind regards,

Jos
which means my previous checking will not work?
Aug 9 '07 #10
JosAH
11,448 Expert 8TB
[quote=KWSW]

which means my previous checking will not work?
As I wrote above: nope, the way you construct your parity bits is not correct
(you calculate the parity value over the wrong bits).

kind regards,

Jos
Aug 9 '07 #11
KWSW
72
[quote=JosAH]

As I wrote above: nope, the way you construct your parity bits is not correct
(you calculate the parity value over the wrong bits).

kind regards,

Jos
ok starting from scratch again

Hamming (7,4)

h1 h2 h3 h4 h5 h6 h7 = p1 p2 b1 p3 b2 b3 b4

p1 = b1 XOR b2 XOR b4
p2 = b1 XOR b3 XOR b4
p3 = b2 XOR b3 XOR b4

edited:

just this idea from the wikipedia page

c1 = p1 XOR b1 XOR b2 XOR b4
c2 = p2 XOR b1 XOR b3 XOR b4
c3 = p3 XOR b2 XOR b3 XOR b4

than i convert (c1c2c3) into dec and that will be the bit with the error...
Aug 9 '07 #12
JosAH
11,448 Expert 8TB
[quote=KWSW]

ok starting from scratch again

Hamming (7,4)

h1 h2 h3 h4 h5 h6 h7 = p1 p2 b1 p3 b2 b3 b4

p1 = b1 XOR b2 XOR b4
p2 = b1 XOR b3 XOR b4
p3 = b2 XOR b3 XOR b4
That is not correct, use this instead:

p1 uses p1 b1 b2 b4 (use 1, skip 1 etc)
p2 uses p2 b1 b3 b4 (use 2, skip 2 etc)
p3 uses p3 b2 b3 b4 (use 4, skip 4 etc)

kind regards,

Jos
Aug 9 '07 #13
KWSW
72
[quote=JosAH]

That is not correct, use this instead:

p1 uses p1 b1 b2 b4 (use 1, skip 1 etc)
p2 uses p2 b1 b3 b4 (use 2, skip 2 etc)
p3 uses p3 b2 b3 b4 (use 4, skip 4 etc)

kind regards,

Jos
sorry i dun understand you...

what i understand from the website is:

//Checking Bits
c1 = p1 XOR b1 XOR b2 XOR b4;
c2 = p2 XOR b1 XOR b3 XOR b4;
c3 = p3 XOR b2 XOR b3 XOR b4;

form there i can tell which bit is wrong.

example I get:

c1 = 1
c2 = 0
c3 = 1

than it means that the error bit is in c1 and c3 but not in c2 which means that its b2 since it cannot be b1, b3, b4 and yet b2 appears in c1 and c3 but not c2...
Aug 9 '07 #14
JosAH
11,448 Expert 8TB
[quote=KWSW]

sorry i dun understand you...

what i understand from the website is:

//Checking Bits
c1 = p1 XOR b1 XOR b2 XOR b4;
c2 = p2 XOR b1 XOR b3 XOR b4;
c3 = p3 XOR b2 XOR b3 XOR b4;

form there i can tell which bit is wrong.

example I get:

c1 = 1
c2 = 0
c3 = 1

than it means that the error bit is in c1 and c3 but not in c2 which means that its b2 since it cannot be b1, b3, b4 and yet b2 appears in c1 and c3 but not c2...
Yep, that's the beauty of Hamming codes. Bit b2 must be incorrect. Have
another look at that Venn diagram in that link page; c1 and c3 (p1 and p3 in
the figure) are incorrrect but c2 (p2) isn't. That leaves b2 (d2 in the figure) as
the only incorrect bit.

kind regards,

Jos
Aug 9 '07 #15
KWSW
72
[quote=JosAH]

Yep, that's the beauty of Hamming codes. Bit b2 must be incorrect. Have
another look at that Venn diagram in that link page; c1 and c3 (p1 and p3 in
the figure) are incorrrect but c2 (p2) isn't. That leaves b2 (d2 in the figure) as
the only incorrect bit.

kind regards,

Jos
based on that i redid my checking:
Expand|Select|Wrap|Line Numbers
  1.         //Checking Bits
  2.         int c1 = p1 ^ b1 ^ b2 ^ b4;
  3.         int c2 = p2 ^ b1 ^ b3 ^ b4;
  4.         int c3 = p3 ^ b2 ^ b3 ^ b4;
  5.  
  6.         if(c1 == 1 && c2 == 0 && c3 == 0)
  7.         {
  8.             //Error with p1
  9.         }
  10.         else if(c1 == 0 && c2 == 1 && c3 == 0)
  11.         {
  12.             //Error with p2
  13.         }
  14.         else if(c1 == 0 && c2 == 0 && c3 == 1)
  15.         {
  16.             //Error with p3
  17.         }
  18.         else if(c1 == 1 && c2 == 1 && c3 == 0)
  19.         {
  20.             // Error with b1
  21.         }
  22.         else if(c1 == 0 && c2 == 1 && c3 == 1)
  23.         {
  24.             // Error with b3
  25.         }
  26.         else if(c1 == 1 && c2 == 0 && c3 == 1)
  27.         {
  28.            // Error with b2
  29.         }
  30.         else if(c1 == 1 && c2 == 1 && c3 == 1)
  31.         {
  32.            // Error with b4
  33.         }
Aug 10 '07 #16
KWSW
72
[quote=JosAH]

Yep, that's the beauty of Hamming codes. Bit b2 must be incorrect. Have
another look at that Venn diagram in that link page; c1 and c3 (p1 and p3 in
the figure) are incorrrect but c2 (p2) isn't. That leaves b2 (d2 in the figure) as
the only incorrect bit.

kind regards,

Jos
based on that i redid my checking:

c1 = p1 XOR b1 XOR b2 XOR b4;
c2 = p2 XOR b1 XOR b3 XOR b4;
c3 = p3 XOR b2 XOR b3 XOR b4;

c1 == 1 && c2 == 0 && c3 == 0
Error with p1

c1 == 0 && c2 == 1 && c3 == 0
Error with p2

c1 == 0 && c2 == 0 && c3 == 1
Error with p3

c1 == 1 && c2 == 1 && c3 == 0
Error with b1

c1 == 0 && c2 == 1 && c3 == 1
Error with b3

c1 == 1 && c2 == 0 && c3 == 1
Error with b2

c1 == 1 && c2 == 1 && c3 == 1
Error with b4
Aug 10 '07 #17
JosAH
11,448 Expert 8TB
[quote=KWSW]

based on that i redid my checking:

c1 = p1 XOR b1 XOR b2 XOR b4;
c2 = p2 XOR b1 XOR b3 XOR b4;
c3 = p3 XOR b2 XOR b3 XOR b4;

c1 == 1 && c2 == 0 && c3 == 0
Error with p1

c1 == 0 && c2 == 1 && c3 == 0
Error with p2

c1 == 0 && c2 == 0 && c3 == 1
Error with p3

c1 == 1 && c2 == 1 && c3 == 0
Error with b1

c1 == 0 && c2 == 1 && c3 == 1
Error with b3

c1 == 1 && c2 == 0 && c3 == 1
Error with b2

c1 == 1 && c2 == 1 && c3 == 1
Error with b4
Yup, the c1, c2, c3 values, when interpreted as a binary three bit number, are
supposed to be the index number of the incorrect bit.1, 2, 3 ... 7. I'm sure I made
a mistake somewhere in one of my replies but this is the crux of Hamming code.

kind regards,

Jos

ps. I think b2 and b3 need to be swapped ... not sure though: I didn't have my
espresso yet ;-)
Aug 10 '07 #18
KWSW
72
[quote=JosAH]

Yup, the c1, c2, c3 values, when interpreted as a binary three bit number, are
supposed to be the index number of the incorrect bit.1, 2, 3 ... 7. I'm sure I made
a mistake somewhere in one of my replies but this is the crux of Hamming code.

kind regards,

Jos

ps. I think b2 and b3 need to be swapped ... not sure though: I didn't have my
espresso yet ;-)
no prob at least I finally got this nailed down...

although with this, is there anyway to check if a code has 2 errors or more since hamming (7,4) cannot correct more than 1 error?
Aug 10 '07 #19
JosAH
11,448 Expert 8TB
[quote=KWSW]

no prob at least I finally got this nailed down...

although with this, is there anyway to check if a code has 2 errors or more since hamming (7,4) cannot correct more than 1 error?
Other, longer Hamming codes can find two or more errors but there's a catch:
suppose you receive, say &00, can you tell how many bits are wrong? The
parity bits are ok, so it seems that there are no errors in that bit sequence.

Maybe 2 or more bits are wrong; who knows? Hamming codes work, *assuming*
that no more than n bits were wrong.

kind regards,

Jos
Aug 10 '07 #20
KWSW
72
[quote=JosAH]

Other, longer Hamming codes can find two or more errors but there's a catch:
suppose you receive, say &00, can you tell how many bits are wrong? The
parity bits are ok, so it seems that there are no errors in that bit sequence.

Maybe 2 or more bits are wrong; who knows? Hamming codes work, *assuming*
that no more than n bits were wrong.

kind regards,

Jos
alrights i understand this part... many thanks for all ur help... time to write the report on why even with hamming, i still get trash after decoding through a channel with 20% chance of error...
Aug 10 '07 #21
JosAH
11,448 Expert 8TB
[quote=KWSW]

alrights i understand this part... many thanks for all ur help... time to write the report on why even with hamming, i still get trash after decoding through a channel with 20% chance of error...
For every 35 bits on average 7 bits are incorrect (20%) if two or more of them
are incorrect in a single Hamming 7 bit code then decoding will fail.

kind regards,

Jos
Aug 10 '07 #22

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

45 posts views Thread by Joh | last post: by
144 posts views Thread by Natt Serrasalmus | last post: by
2 posts views Thread by LabWINC | last post: by
4 posts views Thread by AzizMandar | last post: by
9 posts views Thread by KWSW | last post: by
1 post views Thread by bigidybong | last post: by
3 posts views Thread by mcoyle128 | last post: by
8 posts views Thread by godavemon | last post: by
1 post views Thread by CARIGAR | last post: by
1 post views Thread by Geralt96 | last post: by
reply views Thread by harlem98 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.