1
$\begingroup$

I'm trying to learn for my exam and had the following practice question:

Take a code with the following code words.

  • 101100010111
  • 110001001001
  • 101110111011

Errors of how many bits can be corrected?


The answer i received was:

The hamming distance is: 4.

Therefore only single bit errors can be corrected.


How did they conclude that only single bit errors can be corrected just by looking at the hamming distance?

$\endgroup$
  • $\begingroup$ This is explained in Wikipedia: en.wikipedia.org/wiki/…. $\endgroup$ – Yuval Filmus Apr 11 '18 at 15:42
  • $\begingroup$ @YuvalFilmus So basically, d is 4, and the max number of errors is floor((d-1)/2) which equals floor(1.5) = 1? $\endgroup$ – GSerum_ Apr 11 '18 at 15:49
  • $\begingroup$ Yes, that's the calculation. I strongly suggest that you understand what is behind this formula. $\endgroup$ – Yuval Filmus Apr 11 '18 at 15:50
2
$\begingroup$

If you need four bit changes to change from A to B, then you can make two bit changes from A to some A' followed by two more bit changes from A' to B. If you receive A' then you don't know whether it is a double bit error coming from A, or a double bit error coming from B. Therefore, you cannot fix double bit errors.

Since four bit errors are needed to go from one valid code to another, you can detect double bit errors.

You also have the choice of either fixing single bit errors and detecting double bit errors at the same time (assuming that there will be no triple bit errors), or detecting triple bit errors. You cannot both fix single bit errors and detect triple bit errors, since I can get the same result by changing a single bit in A and changing three bits in B.

$\endgroup$

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.