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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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