473,380 Members | 1,374 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,380 software developers and data experts.

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

ps. Google is your friend here
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?

Thanks again in advance :)
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?

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

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

Similar topics

3
by: dot | last post by:
Hi all, I have written a Python huffman Encoding Module, for my own amusement. I thought it might be educational/entertaining for other people, so I've put it on my website and wrote about it a...
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 : , , , ,
1
by: Slade | last post by:
Hi, I'm trying to use POST an image to a web page with WebRequest/WebResponse. Only problem is that I must be making an error somewhere in the encoding/decoding process. I've pasted below a bit...
9
by: Mark | last post by:
I've run a few simple tests looking at how query string encoding/decoding gets handled in asp.net, and it seems like the situation is even messier than it was in asp... Can't say I think much of the...
37
by: Zhiv Kurilka | last post by:
Hi, I have a text file with following content: "((^)|(.* +))" if I read it with: k=System.IO.StreamReader( "file.txt",System.Text.Encoding.ASCII); k.readtotheend()
14
by: Zoro | last post by:
My task is to read html files from disk and save them onto SQL Server database field. I have created an nvarchar(max) field to hold them. The problem is that some characters, particularly html...
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: Michele | last post by:
Hi there, I'm using a python script in conjunction with a JPype, to run java classes. So, here's the code: from jpype import * import os import random import math import sys
3
by: mviuk | last post by:
Hi, I'm looking for a system which detaches the decoding process from the encoding process. That is, I would like a system for encoding data, but even if both the encoded data and the encoding...
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 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 former...
0
by: ryjfgjl | last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
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
0
BarryA
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...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
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 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.