473,380 Members | 1,374 Online

# Hamming Encoding / Decoding

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
9 8767
JosAH
11,448 Expert 8TB
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

Aug 6 '07 #2
KWSW
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
JosAH
11,448 Expert 8TB
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
KWSW
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?

Aug 6 '07 #5
JosAH
11,448 Expert 8TB
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?

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
KWSW
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
JosAH
11,448 Expert 8TB
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
KWSW
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
JosAH
11,448 Expert 8TB
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