473,320 Members | 1,926 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

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 4862
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

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

Similar topics

45
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 : , , , ,
144
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...
2
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...
4
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...
9
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...
1
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?
1
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...
3
by: mcoyle128 | last post by:
Where can I find the Hamming Code in Java in this site please?
8
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...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.