Hamming distance necessary for detecting d-bit error and for correcting a d-bit error [duplicate]

Question

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.

1. 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.

2. 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?

Answer 1

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 < 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 < 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 < 10$, this cannot happen. Reiterating, if $2y < 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 < D$, and the second as long as $2d < D$. Given $d$, the minimum value of $D$ satisfying $d < D$ is $D = d+1$, and the minimum value of $D$ satisfying $2d < D$ is $D = 2d+1$. That's where the formulas come from. But don't memorize the formulas. Understand where they come from instead.

Answer 2

Yuval Filmus is absolutely right. You should not remeber the formula, but reinvent it when needed. It is really so simple.

Let me try explaining a different way.

The Hamming distance between two binary strings of the same length is the number of bit positions where the string differ. But the important point to remember is that it is a distance, pretty much like distances you measure on a road or on a map.

Changing a bit, either from 0 to 1, or from 1 to 0 is just like taking a step (using the step as unit of distance). Consider a code, composed of a collection of code words. Each codeword is just like a house. If your codewords are at a hamming distance $h$ from each other, it is like houses being at a $h$ steps distance from each other.

Now you are in house $u$, and you use your GPS to get the coordinates of your house, which you want to send to a friend who is to join you. But your GPS is not quite exact an gives you coordinates that may be off by $d$ step at most, which you send your friend, who goes to the coordinates he receives.

Then your two questions are:

1. what should be the minimal distance $h$ between houses so that your friend is sure to realise you transmitted incorrect coordinates.

2. what should be the minimal distance $h$ between houses so that your friend can furthermore be sure to find the right house by simply going to the house closest to the given incorrect coordinates.

It is quite clear that if the error is at most $d$ steps, and houses are at a greater distance $h$ steps, i.e. $d<h$, then the coordinates you send cannot be the cordinates of another house as they are further apart than the maximum error. Hence, your friend will see no house at the given coordinates and will know there is an error. Since we consider only integer number of steps (or bits), $d<h$ implies $d+1\leq h$, hence $h$ must be at least equal to $d+1$. If $d=4$, you indeed need $h=5$.

Now, if the error $d$ is always less than half the distance $h$ between two houses, the coordinates will always give a place that is closer to your house than to any other. Hence, if your friend knows that $2d<h$, he know that the house closest to the coordinates he has is actually your house. Since we consider only integer number of steps, then $2d<h$ implies $2d+1\leq h$, hence $h$ must be at least equal to $2d+1$. If $d=4$, you need $h=9$.

Now a codeword with an error of $d$ bits is exactly like the error of $d$ steps on the position of your house. And sending successive codewords is like moving from house to house, sending each time your coordinate with some error not exceeding a distance $d$ ($d$ steps off, or $d$ wrong bits), and asking your friend to retrace your route.

In "Hamming distance", the name Hamming just says that you are considering distances in number of different bits, rathen than distance in steps, or meters. But in both case it is a distance, with a unit of measure, and the possibility of comparing distances.