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 
for(int i = 0; i < size; i++)

{

double e = Math.random();


if(e > errorPercent)

{

output += (char)text[i];

}

else

{

if((char)text[i] == '1')

{

output += '0';

}

else

{

output += '1';

}

}

}
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...
21 4462
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
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...
here is my logic for encoding and decoding.
encoding: 
Data = b1 b2 b3 b4

Parity = p1 p2 p3

Hamming = b1 b2 b3 p1 b4 p2 p3

= h7 h6 h5 h4 h3 h2 h1


p1 = b1 XOR b3 XOR b4;

p2 = b1 XOR b2 XOR b4;

p3 = b1 XOR b2 XOR b3;


decoding:  using h7 h6 h5 h4 h3 h2 h1

or b1 b2 b3 p1 b4 p2 p3

correct code table = {"0000000","0000111","0011001","0011110","0101010",

"0101101","0110011","0110100","1001011","1001100","1010010","1010101",

"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.
[quote=KWSW] 
Data = b1 b2 b3 b4

Parity = p1 p2 p3

Hamming = b1 b2 b3 p1 b4 p2 p3

= h7 h6 h5 h4 h3 h2 h1


p1 = b1 XOR b3 XOR b4;

p2 = b1 XOR b2 XOR b4;

p3 = b1 XOR b2 XOR b3;


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
[quote=JosAH]

Data = b1 b2 b3 b4

Parity = p1 p2 p3

Hamming = b1 b2 b3 p1 b4 p2 p3

= h7 h6 h5 h4 h3 h2 h1


p1 = b1 XOR b3 XOR b4;

p2 = b1 XOR b2 XOR b4;

p3 = b1 XOR b2 XOR b3;


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.
[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
[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...
[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
[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?
[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
[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...
[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
[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...
[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
[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: 
//Checking Bits

int c1 = p1 ^ b1 ^ b2 ^ b4;

int c2 = p2 ^ b1 ^ b3 ^ b4;

int c3 = p3 ^ b2 ^ b3 ^ b4;


if(c1 == 1 && c2 == 0 && c3 == 0)

{

//Error with p1

}

else if(c1 == 0 && c2 == 1 && c3 == 0)

{

//Error with p2

}

else if(c1 == 0 && c2 == 0 && c3 == 1)

{

//Error with p3

}

else if(c1 == 1 && c2 == 1 && c3 == 0)

{

// Error with b1

}

else if(c1 == 0 && c2 == 1 && c3 == 1)

{

// Error with b3

}

else if(c1 == 1 && c2 == 0 && c3 == 1)

{

// Error with b2

}

else if(c1 == 1 && c2 == 1 && c3 == 1)

{

// Error with b4

}
[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
[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 ;)
[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?
[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
[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...
[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
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
    
8 posts
views
Thread by godavemon 
last post: by
          