# Bounds on decoding a codeword

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.

• If the distance to a legitimate codeword is non-zero, we know for sure there has been a transmission error. So case (ii) does happen. – André Nicolas Nov 10 '15 at 18:15
• @AndréNicolas Then what is the difference between case (2) and (3)? – Jan Leo Nov 10 '15 at 19:01
• Whoever wrote this painted a simplified picture. Many details depend on what kind of decoding can be performed by the receiver. In case 1) the receiver is guaranteed to succeed (assuming its algorithm is good enough). In case 2) we can, indeed, always detect that errors have occured. It is possible that the original word is still the closest codeword, but then we need luck with the actual error pattern. But the decoder may also decode to an incorrect codeword and be unaware that we are in case 2 as opposed to case 1. In case 3) we are no longer guaranteed to detect that errors occurred. – Jyrki Lahtonen Nov 11 '15 at 7:54
• Anyway, it is definitely wrong to say that whenever more than $(d-1)/2$ errors occur, we move to the scope of another codeword. We may equally well (this actually happens often in practive) move to a region of the Hamming space, where there are no codewords within distance $(d-1)/2$. The so called perfect codes form an exception to this, but, while mathematically fascinating, they are so few in number to be considered useless for practical error-correction. – Jyrki Lahtonen Nov 11 '15 at 7:58
• As a toy example consider the following code (a very bad one - just making a point here). It has the words $$\{0000000000,1110000000,0001111111,1111111111\}.$$ The minimum distance is three. But if the word $x=0001111111$ was received as $0001111000$, i.e. 3 errors ($>d-1$) the decoder can actually claim that $x$ was transmitted, because it is at Hamming distance three, and the other codewords are further away Making 3 errors did not move this to the scope of some other word. But we are not guaranteed to detect all patterns of three errors as the first codeword may be received as the second. – Jyrki Lahtonen Nov 11 '15 at 8:06

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.

• Thanks! What do you mean by TL, DR, Alert? – Jan Leo Nov 12 '15 at 4:33
• – Jyrki Lahtonen Nov 12 '15 at 4:59