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 4869
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
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Joh |
last post by:
hello,
i'm trying to understand how i could build following consecutive sets
from a root one using generator :
l =
would like to produce :
, , , ,
|
by: Natt Serrasalmus |
last post by:
After years of operating without any coding standards whatsoever, the
company that I recently started working for has decided that it might be a
good idea to have some. I'm involved in this...
|
by: LabWINC |
last post by:
Hi all,
i have a question for all :-D
I would like to design and apply a FIR low pass filter with Hamming
window.
I'm using scipy module.
First I create the windows with the signal.firwin...
|
by: AzizMandar |
last post by:
C++ Event Coding Questions
I have done some simple programs in C++ and read a lot of good C++
books (Including The C++ Programing Language, and C++ Primer) I am
trying to understand and...
|
by: KWSW |
last post by:
Having settled the huffman encoding/decoding and channel modeling(thanks to the previous part on bitwise operation), the last part would be hamming encoding/decoding.
Did some research as usual on...
|
by: babydollbijal |
last post by:
how i can develope the hamming code(7,4) using java..any interface or class is available for that in java?
|
by: bigidybong |
last post by:
I've been set this task below. Unlike my colleagues I am new to java. If anyone has the code for this then please let me know or send me an email if they can do it.
Develop a program which...
|
by: mcoyle128 |
last post by:
Where can I find the Hamming Code in Java in this site please?
|
by: godavemon |
last post by:
I need to calculate the Hamming Distance of two integers. The hamming
distance is the number of bits in two integers that don't match. I
thought there'd be a function in math or scipy but i...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
| |