By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
434,793 Members | 1,252 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 434,793 IT Pros & Developers. It's quick & easy.

Hamming Encoding / Decoding

P: 72
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 hamming codes and how they work(well sort of) I got a general idea how to start constucting a (7,4) hamming code.

Unfortunately I have no idea how to start on the decoding/error correcting part and some direction would be nice.

---

for encoding I figured out I woul have to take the first 4 bits and add 3 more behind as the parity check bit.

but for decoding/error correcting, I would have to construct sort of a list of possible codes and pick the one with the least "distance"?
Aug 6 '07 #1
Share this Question
Share on Google+
9 Replies


Expert 10K+
P: 11,448
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 hamming codes and how they work(well sort of) I got a general idea how to start constucting a (7,4) hamming code.

Unfortunately I have no idea how to start on the decoding/error correcting part and some direction would be nice.

---

for encoding I figured out I woul have to take the first 4 bits and add 3 more behind as the parity check bit.

but for decoding/error correcting, I would have to construct sort of a list of possible codes and pick the one with the least "distance"?
This is how I know (7,4) Hamming code: positions 1, 2 and 4 are the parity
bit positions; the other four are the data bits:

p1 p2 d1 p4 d2 d3 d4

p1 is computed using the bits at positions 1, 3, 5, 7 (check 1, skip 1)
p2 is computed using the bits at positions 2, 3, 6, 7 (check 2, skip 2)
p4 is computed using the bits at positions 4, 5, 6, 7 (check 4, skip 4)

p1 p2 p4 form a three bit word itself and if one of them is incorrect the position
of the incorrect bit can be found by forming the three bit word from p1 p2 p4
(1 means incorrect, 0 means correct). The value of this word is the position
of the incorrect bit.

kind regards,

Jos

ps. Google is your friend here
Aug 6 '07 #2

P: 72
ah ok i got an rough idea... just wanna check if this can work...

p1 = parity addition of (b1+b2+b3)
p2 = parity addition of (b1+b3+b4)
p3 = parity addition of (b2+b3+b4)

that would mean p1 = b1 XOR b2 XOR b3?

Also just wondering if i can do this in terms of java

Expand|Select|Wrap|Line Numbers
  1. int b1 = 1;
  2. int b2 = 0;
  3. int b3 = 0;
  4. int b4 = 1;
  5.  
  6. int p1 = b1 ^ b2 ^ b3;
Aug 6 '07 #3

Expert 10K+
P: 11,448
ah ok i got an rough idea... just wanna check if this can work...

p1 = parity addition of (b1+b2+b3)
p2 = parity addition of (b1+b3+b4)
p3 = parity addition of (b2+b3+b4)

that would mean p1 = b1 XOR b2 XOR b3?

Also just wondering if i can do this in terms of java

Expand|Select|Wrap|Line Numbers
  1. int b1 = 1;
  2. int b2 = 0;
  3. int b3 = 0;
  4. int b4 = 1;
  5.  
  6. int p1 = b1 ^ b2 ^ b3;
I don't know which index scheme you're using but it can be very well done using
Java's bit fiddling operators. Here's a little tip: if you want to find out how many
bits in a word are set to one, use this:

Expand|Select|Wrap|Line Numbers
  1. public int nofBitsSet(int x) {
  2.  
  3.    int total= 0;
  4.    for (; x != 0; x&= x-1)
  5.       total++;
  6.    return total;
  7. }
  8.  
kind regards,

Jos
Aug 6 '07 #4

P: 72
Thanks for the added info, and i learn something new again :)

Was reading up on the error correcting if needed and this is the logic I came out with.

1.Compute a collection/table of the possible combinations/outcomes I can expect.
from 0000 - 1111 and their hamming codes.

2. Receive the hamming code and compare to the collection/table to find a match.

2a.If there is a match, no error has occurred and I will just decode it as the first 4 bits.

2b.If there is no match, I will calculate the hamming weight of the received error code and look through the collection/table to find the code with the nearest hamming weight. Take that code as the corrected code and decode it as the first 4 bits.

Was thinking of using a map<Integer(hamming weight),String(hamming code)> to hold the calculated possible combinations/outcome. Would this be ok or would there be another better way?

Also hamming weight in my case would be the number of "1"s found in my strin of code make up of "0"s and "1"s?

Thanks again in advance :)
Aug 6 '07 #5

Expert 10K+
P: 11,448
Thanks for the added info, and i learn something new again :)

Was reading up on the error correcting if needed and this is the logic I came out with.

1.Compute a collection/table of the possible combinations/outcomes I can expect.
from 0000 - 1111 and their hamming codes.

2. Receive the hamming code and compare to the collection/table to find a match.

2a.If there is a match, no error has occurred and I will just decode it as the first 4 bits.

2b.If there is no match, I will calculate the hamming weight of the received error code and look through the collection/table to find the code with the nearest hamming weight. Take that code as the corrected code and decode it as the first 4 bits.

Was thinking of using a map<Integer(hamming weight),String(hamming code)> to hold the calculated possible combinations/outcome. Would this be ok or would there be another better way?

Also hamming weight in my case would be the number of "1"s found in my strin of code make up of "0"s and "1"s?

Thanks again in advance :)
You can even keep track of three tables:

1) the correct codes;
2) the correctable codes (1 error)
3) the wrong codes (can not be corrected)

... and calculate the values for these tables in advance.

kind regards,

Jos
Aug 6 '07 #6

P: 72
hmm, codes that cannot be corrected....

that would mean that my checking logic for error codes would be:


1. get form correct table codes with a difference in hamming weight of 1.
2. corrected to the code with a difference in hamming distance of 1.

if a code fails either, it belongs to the cannot be corrected table.
Aug 6 '07 #7

Expert 10K+
P: 11,448
hmm, codes that cannot be corrected....

that would mean that my checking logic for error codes would be:


1. get form correct table codes with a difference in hamming weight of 1.
2. corrected to the code with a difference in hamming distance of 1.

if a code fails either, it belongs to the cannot be corrected table.
Yup, that's it. You can calculate all those codes in advance and fill your tables
with them.

kind regards,

Jos
Aug 6 '07 #8

P: 72
Ok got everything up and running... but got another question, do I pad a input for my hamming (7,4) encoding?

example:
I get encode with hammings my file and the last part I get is only 2 bits but I would need 4 bits to do the encoding. Do I just add 2 "0"s to make 4 bits?
Aug 7 '07 #9

Expert 10K+
P: 11,448
Ok got everything up and running... but got another question, do I pad a input for my hamming (7,4) encoding?

example:
I get encode with hammings my file and the last part I get is only 2 bits but I would need 4 bits to do the encoding. Do I just add 2 "0"s to make 4 bits?
It's all up to you: you have to have something there to complete the last byte
and since you're not going to use those last two bits it's your convention what
those last two bit values are supposed to be; 00 would be fine.

kind regards,

Jos
Aug 7 '07 #10

Post your reply

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