How does hamming distance help correcting codes?

[elecs_gene]

error correcting codes

hi,
could u guys explain me what hamming distance is all about?that is i read that if the minimum hamming distance is satisfied,then it is possible to correct your codes.how is this achieved?please help....

 

[Resistance]

Re: error correcting codes

Hi,

So Hamming distance by def is between two code worfds what r the bits that differ.

So basically it is a comparision technique as far as i know.. know u have detected an error how do we correct it ?

So hamming distance not only tells u by how they differ but also how far they are.
take a plot and using many criterions u can land up estimating which would be closet to the codeword u have transmitted.Thats the mechanism by which best estimation is done.

U would have read abt LMS and Steetest Decent alg.. they are all egs how the best estimation is done..

regards

 

[ee_expert2000]

Re: error correcting codes

hamming distance by definition is the maximum seperation of two code words.
the more this value, the more tye system can tolerate noise.
the point is that if you increase your code word length, the more noise your system can stand. butt this leads to a reduction of you system data transfer rate.

 

[albert22]

Re: error correcting codes

Hamming distance is a measure of how ‘close’ two code word are
For error correction it is important to know the minimun hamming distance between any two words of the code (dmin).
Having a code means that some words of the space are valid and others are not. You transmit only the valid words. If they are corrupted by transmission errors. Some bits would have changed.
If your dmin is 1 you have no means of detecting an error because any bit changed results on a valid word.
If your dmin is 2 you can detect an error of one bit changed but not correct it. Because changing 1 bit gives an invalid word which is equally distant of two or more valid words.
If your dmin is 3 then you can detect 2 bit errors and correct 1 bit errors. Because when 1 bit changes the invalid word which results falls near to only one valid word.
In general you can correct dmin - 2 error bits and you can detect dmin-1.
As resistance said correcting an error is just a matter of picking the nearest valid word (of the code)

Of course there are other methods of error correction.

Happy New year

 

[Resistance]

Re: error correcting codes

hi albert22,

If your dmin is 1 you have no means of detecting an error because any bit changed results on a valid word.
If your dmin is 2 you can detect an error of one bit changed but not correct it. Because changing 1 bit gives an invalid word which is equally distant of two or more valid words.
If your dmin is 3 then you can detect 2 bit errors and correct 1 bit errors. Because when 1 bit changes the invalid word which results falls near to only one valid word.
In general you can correct dmin - 2 error bits and you can detect dmin-1.


the reason i think dmin =1 is difficult to correct is wat u told plus the syndrome for one bit error is the same as the property of LBC goes right?

Then can u explain also which dmin is preferred and which ec codes is widely used as i have only studied as in m courses but have no hands on experience.

 

[albert22]

Re: error correcting codes

Hi Resistance

>the reason i think dmin =1 is difficult to correct is wat u told plus the syndrome >for one bit error is the same as the property of LBC goes right?

I dont know what LBC is.
But when dmin = 1 there is no detection or correction. If just one bit changes the new word will be valid and the error goes undetected.

dmin is selected by first defining how many bit errors you want to be able to detect and correct. Obviuosly the larger is better. But to increase dmin you should increase the space of possible words or decrease the number of valid words of the code.
In other words you have to add redundancy to the data. All systems of error correction add redundancy to the data by adding more bits than those needed to just send the desired message.
In a convolutional code (ratio 1/2) you are sending 2 bits for each bit of the message. That is you are doubling the req. bandwidth.
In a memory ECC 7 bits can protect 32 bits or 8 bits can protect 64 bits
So there is always a tradeoff between the error correcting capability and the redundancy you add.


The choice of an ECC depends on the application.
There are Block and convolutional (sequential) ECCs. And in each category you have many choices. Sometimes more than one is used at the same time. It is said that they are "concatenated". As an example in a modem you may find a block ECC as Reed Solomon, followed by a convolutional encoder. Which are widely used.
Check this page:
http://www.eccpage.com/
There are some books that you can upload from edaboard.
Including "Introduction to error correcting codes " by Michael Purser

 

[moorthi]

Re: error correcting codes

i'e for ex if A=01110011
and B=11101111;
wt(A)= 5 and wt(b)=7;

Hamming distance
H(A,B)= weight(A^B)

A^B is the bitwise xoring of the two vectors= 10011100
wt(A^B) is the number of ones in the A^B = 4;

So the hamming distance is the difference in the number of bits in the two input bit patterns in the bit positions is =4;