Hamming distance necessary for detecting d-bit error and for correcting a d-bit error I am trying to understand what hamming distance of a code is needed to detect a d-bit error, or to correct a d-bit error.

This is what I have found around the web:


  If two codewords are Hamming distance $d$ apart, it will take $d$ one-bit
  errors to convert one into the other.
  
  
  To detect (but not correct) up to $d$ errors per length n of a codeword,
  you need a coding scheme where codewords are at least $(d + 1)$ apart in
  Hamming distance. Then d errors can't change into another legal code,
  so we know there's been an error.
  To correct $d$ errors, need codewords $(2d + 1)$ apart. Then even with $d$
  errors, bit string will be $d$ away from original and $(d + 1)$ away from
  nearest legal code. Still closest to original. Original can be
  reconstructed
  


I have seen in my other post that, in the image, the calculation of the bits that can be detected and correct is done using the reversed formula of the above statements 1. and 2:

If we have a hamming distance of $d$, we can detect $d - 1$ errors (inverse of the formula 1.), so to detect a $d - 1$ error, we need a hamming distance of d (same thing said in another way). So for example, if we want to know what is the hamming distance required to detect a 4 errors, we just have to apply the formula 1.

$4 = d - 1$

$4 + 1 = d$

We need a hamming distance of 5. 

So to find the hamming distance required to correct $d$-bit errors, we have to apply the formula 1. $2d + 1$, where $d$ are the bit errors.

Am I correct?

If yes, could you explain me what the second part of the point 2. is saying:


  Then even with $d$ errors, bit string will be $d$ away from original
  and $(d + 1)$ away from nearest legal code. Still closest to original.
  Original can be reconstructed


By d-bit errors, we mean d number of errors, right?
The first step towards clarifying your confusion is forgetting about the formulas. You should be able to understand this material without looking at the formulas. You should even be able to develop the formulas on your own.

Now to the actual question at hand. Suppose we have a bunch of codewords, and every two are different in at least 10 positions. Suppose I send one codeword on the air, and an adversary corrupts (flips) $x$ bits. I claim that if he flips a small enough number of bits, then the receiver can detect that the adversary modified my codeword. The way she is going to do that is by noticing that what she got wasn't a codeword at all. If $x &lt; 10$ then flipping $x$ bits, the adversary cannot reach another codeword, since by assumption any two codewords differ in at least 10 positions. So if the adversary flips $x &lt; 10$ bits, the receiver will notice that the communication was corrupted on air. That's the meaning of "$d$-bit errors can be detected", where here $d = 9$.

Continuing the same scenario, the receiver isn't really interested in knowing whether some bits were flipped. Rather, she wants to know what the original codeword was. Suppose we can promise her that at most $y$ bits were flipped. When can she recover the original codeword? How is she going to recover the original codeword? Suppose that what she gets is the word $w$. She is going to look for the closest codeword $c$, and guess that the original codeword that was sent was $c$. When can we be sure that she is right?
Suppose that the original codeword was actually $o$. So the distance (number of different positions) from $o$ to $w$ is at most $y$ (since we allowed the adversary to flip at most $y$ bits). As $c$ is the codeword closest to $w$, the distance from $c$ to $w$ is also at most $y$. So the distance from $o$ to $c$ is at most $2y$. Since both $o$ and $c$ are codewords, either they are the same (and we win – the receiver found the original codeword), or $2y \geq 10$, since any two codewords differ by at least 10 positions. As long as $2y &lt; 10$, this cannot happen. Reiterating, if $2y &lt; 10$, then even if the adversary flips up to $y$ bits on air, the receiver can know what the original codeword was by looking for the codeword closest to the word she received. That's the meaning of "$d$-bit errors can be corrected", where here $d = 4$.

More generally, if the minimum distance of the code – the minimum distance between two codewords – is $D$, then the first argument will work as long as $d &lt; D$, and the second as long as $2d &lt; D$. Given $d$, the minimum value of $D$ satisfying $d &lt; D$ is $D = d+1$, and the minimum value of $D$ satisfying $2d &lt; D$ is $D = 2d+1$. That's where the formulas come from. But don't memorize the formulas. Understand where they come from instead.