anyone know hamming codes ...errors.?

x in the city

Hi lads,

Im trying to figure this stuff out..

basically have a hamming code word with a bit pattern of say 10101000 and need to find the original 4 bit word that was written.

can anyone do this, i need to mutliply out matrices but totally lost.!

Fremen

I reckon you haven't given us enough information to help you.
I'm familiar with the very basics of this stuff. The idea is that you have some binary sequence, like 10101000 as you said. You also have a map which translates the length 8 binary sequences into length 4 binary sequences. The map translates 10101000 and other sequences "near" it (in the sense of hamming distance) into the same 4 bit sequence. That way, if a bit of your message 10101000 is flipped by an error (into, say, 10101001) the sequence is still translated back into the original message, because 10101000 is close in hamming distance to 10101001.

Maybe there's a univerally agreed upon way to do this, I don't know, but you'll have to tell us what method you're using to do it before we can help.

LenaClaire

Okay, you can technically do hamming code with out a matrix I think.

1. Mark all bit positions that are powers of two as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.)
2. All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.)
3. Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips.
   Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,...)
   Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,...)
   Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,15,20,21,22,23,...)
   Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,...)
   Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,...)
   Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-191,...)
   etc.
4. Set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit to 0 if the total number of ones in the positions it checks is even.

I put a p above each parity bit and a d above each data bit
ppdpdddp
10101000

so your first bit claims to have odd parity but if you count the 1's in spots 3,5,7 but if you look at the code there is an even number there so bit 1 has a parity issue

so you keep checking each parity bit to see if it is correct and then you add up all the ones that are incorrect, find that bit and flip it to give you the original code that was sent.


This is how I remember it but it has been a few years so please verify with another source but I hope this helps some.

x in the city

hi lads

here is the question,, thanks

(wasnt expecting many or no replys...hehe)

I am lost regarding the matric stuff...but I know that its easy once you have it mastered.

x in the city

Can anyone go over Q1 on that sheet by any chance? I have been looking over this on the web but its too confusing, even thou I know its easy once i figure it out.

its not a homework question btw... its something which might come up for my exam.;)

LenaClaire

What you need to do is check each of the parity bits.

if the bit is a 1 it means that when you count the bits it is covering there is an odd number of 1 bits.

if the bit is a 0 it means that when you count the bits it is covering there is an even number of 1 bits.

As you check the parity bits keep track of the parity bits that have the wrong flag.

Once all of the parity bits are verified you add them up to find out which of the data bits was transmitted incorrectly.

For example if parity bits 1 and 4 are not correct it means that data bit 5 is the bit with an error.

You can then correct that bit which would give you the correct word that was initially sent.

If you only have 1 parity bit that does not compute it means that the parity bit is the error.

If you refer to my earlier post it details which bits each parity bit is covering.

I hope this helps clear it up a little.

x in the city

Is this correct....

LenaClaire

I put a p above each parity bit and a d above each data bit

ppdpdddp
10101000

so your first bit claims to have odd parity so you count the 1's in spots 3,5,7 but if you look at the code there is an even number there so bit 1 has a parity issue

the second parity bit covers 3,6,7 which when you count the 1's is odd but the bit is even so another parity issue

The next parity bit is bit 4 and it covers 5,6,7 and they only have one 1 amonst them but the parity bit says even. So you know this one is also a parity issue

and the last parity bit is bit 8 but there are no bits after it so it is 0.

So now you count all the bits that have a parity issue 1+2+4 which gives you 7. This means that bit 7 is the bit with the error. So what should have been received was
10101010


which would give you an inital word of 1110

I am not sure if I am explaining this well, please let me know if it is confusing.

x in the city

jujibee wrote: »

I put a p above each parity bit and a d above each data bit

ppdpdddp
10101000

so your first bit claims to have odd parity so you count the 1's in spots 3,5,7 but if you look at the code there is an even number there so bit 1 has a parity issue

the second parity bit covers 3,6,7 which when you count the 1's is odd but the bit is even so another parity issue

The next parity bit is bit 4 and it covers 5,6,7 and they only have one 1 amonst them but the parity bit says even. So you know this one is also a parity issue

and the last parity bit is bit 8 but there are no bits after it so it is 0.

So now you count all the bits that have a parity issue 1+2+4 which gives you 7. This means that bit 7 is the bit with the error. So what should have been received was
10101010


which would give you an inital word of 1110

I am not sure if I am explaining this well, please let me know if it is confusing.

totally confused....?!!

but I think I am getting there

how do you know the first parity bit is odd??

and when you have like the bits blanked off

like

_ _ 1 _ 010_1010

and you proceed to check the bits for odd/even

do you start with the first data bit, or a blank, check bit..?!


the question said whats the original 4 bit word.. is never said what was the error bit..? (or am i way off...)

LenaClaire

The way the parity bits work is that each parity bit looks at a series of other bits and then counts the 1's. If there is an even number then the parity bit is a 0 and if there is an odd number the parity bit is a 1.

The first parity bit is created by starting with the first data bit and then alternating every other bit after that.

_ _ 1 _ 010_1010

for the word here the first parity bit would be a 1 since there is an odd number of 1's in the data bits the parity bit covers.

To find the original word you first have to determine if there were any errors in the transmission. Once you have found and corrected any errors then you can pull out the data bits which were the original word that was sent.

If you neglect to correct any errors before pulling out the data bits you have no way of knowing if the word that you received is the word that was originally sent.

x in the city

sorry for being such a n0b here :rolleyes::rolleyes:

I have this much done, I think this is right, how do I proceed to the next step , namely finding an error bit.

again, apologies if i am a bit slow...lol

LenaClaire

Sorry, I see where we a having a miscommunciation. The 8 digit word that you had initially from your teacher is the word that was received.

That means that the original word was 4 digits and the code has already been applied.

What you need to do now is look at the 8 digits you have and using what you know about the code determine if what you recieved is what was originally sent.

You are not supposed to re-encode it. Just look at the 8 digits you currently have and see if it fits the logic of the code.

This is a difficult thing so don't worry, it was giving me fits when I was first studying it as well.

So this is the packet that was recieved (4 data bits and 4 parity bits)

ppdpdddp
10101000


This means that according to the recieved transmission the data bits or the original word was 1100.

However, looking at the parity bits that were received you can calculate that one of the data bits got flipped during the transmission.

If you look at the word that was recieved - 1100 and then encode it you will see that you get a different result to what you see here. This means that there was an error.

What you need to do it determine which of the original 4 data bits were flipped (if you refer back to my second post it covers the details).

I am not sure if I am being clear, this is hard to explain over the computer.

x in the city

I see, I think I got it now..

what do you think of this.?!

LenaClaire

You have it about 90% right.

You took the data that was received and found most of the parity bits that were incorrect.

However, instead of changing the parity bits what you do is add them.

This will tell you which of the original data bits was corrupted during transmission. You can then change that one bit to find out what was sent in the beginning.

In the attached document I have highlighted the Parity Bit and the bits it checks. The word that was originally sent was 1101.

Usually for a test situation more than one of the parity bits will be incorrect so that you have something to solve.

If you ever do find a situation where only 1 parity bit is wrong it means that that parity bit was the error rather than a data bit.

x in the city

hmm,

I have looked at that question I am attempting and I have got the same solution

ie: bit 1 with an error, the rest are ok?

so the bit pattern 11100110

now is

01100110

with the code word in it > 1011

is this not right?

(i followed your example alright btw , thanks!...)

LenaClaire

"so the bit pattern 11100110"

I thought the original bit pattern was 10101000?

x in the city

bit pattern is 11100110

I got an error with the first bit just....

I was wondering were you giving me an example of yours..:p