434,793 Members | 1,252 Online + 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
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 int b1 = 1; int b2 = 0; int b3 = 0; int b4 = 1;   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 int b1 = 1; int b2 = 0; int b3 = 0; int b4 = 1;   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 public int nofBitsSet(int x) {      int total= 0;    for (; x != 0; x&= x-1)       total++;    return total; }   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 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 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 