How can errors be detected and corrected using the Hamming distance?

Question

Give an example of the detection of one single-bit error.

Give an example of the correction of one single-bit error.

Answer 1

Well I can see you're doing homework but I'll try to help without actually giving answers for free... First of all the hamming distance is the number of bits in which 2 bit patterns differ. For example the hamming distance between 000000 and 001111 is 4. And the difference between 001111 and 010011 is 3. Also consider the bit patterns 011100 and 110101.

So there's a total of 5 bit patterns:
000000
001111
010011
011100
111010

And notice that the MINIMUM hamming distance between any 2 of these patterns is 3. Go ahead and test a few out.

Now, suppose you receive the pattern 010100. Compare it with the other known patterns and look at the hamming distance for each pairing.

000000 = 2
001111 = 4
010011 = 3
011100 = 1
111010= 4

So we conclude that the pattern we SHOULD HAVE received was 011100, because this pattern is the smallest (distance of only 1) hamming distance away from what we received.

So there's a basic example of correcting a single bit error... That's the idea, you can go from here. Hint: you will need a minimum hamming distance of 5 between all your bit patterns to be able to correct 2 errors.

To understand the complex math behind this technique, do some research on algebraic coding theory.

Answer 2

Hamming Distance Example