I have already asked a pair of questions on the hamming distance, hamming code, valid and invalid codewords on this website, because I cannot understand those concepts fully, and in a few weeks or less, I am going to have an exam also on those topics, I really do not understand. I have tried to take a look to wikipedia articles, but it is, for me, quite complicated to understand.

My question this time is more concrete. I have a figure, representing how many errors can we detect and correct according to the hamming distance. The thing I am not understanding is why, for example, with an hamming distance of 3, we can just detect 2 bit flips and correct 1 bit flip. I know there are 2 formulas (that you can see in the picture), which bring us to that result, but I would like understand why those formulas are correct. Why, with an hamming distance of 3, we can just detect 2 errors and correct 1.

This is picture: enter image description here

The Hamming distance being 3 means that any two code words must differ in at least three bits. Suppose that 10111 and 10000 are codewords and you receive 10110. If you assume that only one bit has been corrupted, you conclude that the word you received must have been a corruption of 10111: hence, you can correct a one-bit error. However, if you assume that one or two bits could have been corrupted, you don't know if 10110 should be 10111 (one 1 got turned into a 0) or 10000 (two 0s got turned into 1s). You can correct one-bit errors (if you assume that those are the only kind that occur) but you can't tell the difference between a one-bit error from one codeword and a two-bit error from another, so you can't deal with two-bit errors at all. If a two-bit error occurs, you'll detect that some error occurred, but you'll assume it was a one-bit error from a different codeword and "correct" it wrongly.

In contrast, with the distance-4 code illustrated in the fourth diagram, you can detect two-bit errors. If you receive the word in the middle, you can tell that (at least) two bits got corrupted but you can't tell whether you were supposed to see the blue codeword on the left or the one on the right.

  • But the image is showing that with an hamming distance of 4, we can detect 3 errors... – nbro Oct 17 '14 at 17:52
  • 3
    @Broly In the distance-4 code, if three bits are corrupted, you can tell that some error occurred. But you'll assume that it was a one-bit error, and "correct" it wrongly. What you can't do is detect that the error was specifically a three-bit error from the left codeword, rather than a one-bit error from the right codeword. – David Richerby Oct 17 '14 at 18:03

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.