Bounds on decoding a codeword

Question

I found this somewhere on the Web: for an error-correcting code with minimum distance $d$, suppose the number of errors in a codeword is $e$:

(1) if $e < (d-1)/2$, we can recover the original codeword;

(2) if $(d-1)/2 < e < d -1$, we can detect that there are errors, but cannot recover the original codeword;

(3) if $e > d - 1$, we can decode to a wrong codeword, without knowing whether the result is wrong;

(1) and (3) are distinguishable to the receiver. Is this right?

I also found that "minimum distance" means the minimum hamming distance between two codewords. In this case, if a codeword has more than $(d-1)/2$ errors, it will move to the scope of another codeword, and thus decode to that codeword. So the case (2) and (3) are indistinguishable to the receiver.

I am sure that there are some mistakes in my understanding, but I don't know where are they.

Answer 1

What always holds:

1. If $e\le (d-1)/2$ there is unique codeword closest to the received vector, and decoding is guaranteed to succeed (but may be computationally infeasible).
2. If $0<e<d$ we will always reliably detect that errors (one or more) have occured. This is because there are no other codewords within $e$ of the transmitted codeword.
3. If $e\ge d$, then all bets are off. We are still likely to detect that errors occured, because it is unlikely (but not impossible) that the errors transformed the transmitted codeword to another codeword.
4. If $e>(d-1)/2$ then the error may or may not have the undesirable side effect that the received word is within distance $(d-1)/2$ from another codeword. If that happens, the decoder will correct, unknowingly, the received vector to the wrong codeword. From the point of view of the receiver the situation is then (but only then) indistuingishable from case 1.

Elaborating a bit on that last point. $\color{red}{\text{TL;DR; Alert.}}$

Assume that the code $C$ is linear over a field $F$, has length $n$, dimension $k$, and minimum distance $d$. Another parameter of the code known as the covering radius, $\rho(C)$, measures how far a vector of $F^n$ can be from the nearest codeword. We obviously have the inequality $$\rho(C)\ge (d-1)/2.\qquad(*)$$ But $\rho(C)$ can be much larger. We have equality in $(*)$ only, when $C$ is a so called perfect code. Those are rare.

In general calculating the covering radius of a given code is very difficult. I do want to mention the following result known as the

Supercode Lemma. Assume that the given code $C$ is a proper subcode of another linear code $C'$. Assume further that the minimum distances of these codes are different, i.e. $d=d_{min}(C)>d'=d_{min}(C')$. Then we have the inequality $$ \rho(C)\ge d_{min}(C'). $$

Proof. Let $x$ be a word of $C'$ of minimum weight $d'$. Because $d'<d$ $x$ cannot be a word of $C$. The claim follows, if we can show that there are no words of $C$ at a distance $<d'$ from $x$. But this follows immediately. For if $y$ is any word of the code $C$, then $y$ is also a word of $C'$ (this is because $C'$ is a supercode of $C$). So automatically $d(x,y)\ge d'$, because both $x$ and $y$ are words of the code $C'$ of minimum distance $d'$. QED

Example. A Reed-Solomon code $C$ of minimum distance $d=5$ can correct up to $(d-1)/2=2$ errors. But because this Reed-Solomon code is a subcode of the bigger Reed-Solomon code of minimum distance $d'=4$. Therefore the supercode lemma says that $\rho(C)\ge 4$. In other words it is possible that four errors occur in such a way that the resulting vector is at Hamming distance $\ge4$ from all the codewords. So in that case we certainly won't fall into the decoding scope of a different codeword.

Observe that in this example both $C$ and $C'$ are MDS-codes, i.e. there parameters are as good as they can possibly be. IOW both are very good codes.