Help understanding why a block code can correct up to (d-1)/2 errors.

Question

THEOREM:

Let d be a block code with odd minimum distance d. Then C can correct up to (d-1)/2 errors.

Proof from wikipedia:

If no more than (d-1)/2 transmission errors occur, the receiver can uniquely decode the received word to a codeword as every received word has at most one codeword at distance (d-1)/2. On the other hand, if more than (d-1)/2 transmission errors occur, the receiver cannot uniquely decode the received word in general as there might be several possible codewords.

Sounds like a perfectly good explanation, but for some reason I am not getting it, even though I understand all the terms. Any help appreciated. (Specifically, I'm having trouble with the italized portion.)

Answer 1

You can think of it this way: suppose your received word $w$ is as close as $(d-1)/2$ to more than one codeword, and call two such codewords $c$ and $c'$. Then the distance from $c$ to $w$ is at most $(d-1)/2$, and the distance from $w$ to $c'$ is at most $(d-1)/2$, so the distance from $c$ to $c'$ is at most $(d-1)/2 + (d-1)/2 = d-1$. This contradicts your original assumption that any two codewords are at least $d$ apart.

In general, arguments that go like "the distance from $x$ to $y$ is at most $a$, and the distance from $y$ to $z$ is at most $b$, so the distance from $x$ to $z$ is at most $a+b$" are secretly using the triangle inequality: $d(x,z)\leq d(x,y)+d(y,z) \leq a+b$.

Answer 2

Decode received messages according to the following (reasonable-looking) rule: Among all the code words, choose one whose Hamming distance from the received word is as small as possible. (If several code words are tied for closest to the received word, choose one of them arbitrarily.) Of course, if there were a huge number of errors in the received word, this decoding procedure might produce an incorrect result. How many transmission errors would have to occur in order for this problem to arise? Well, suppose the received word is $r$, the transmitted code word was $c$, and the decoder incorrectly produced the code word $c'$ instead. If $e$ is the number of transmission errors, then the Hamming distance between $r$ and $c$ is $e$. Since the decoder chose $c'$ and not $c$, we know that $c'$ is at least as close to $r$ as $c$ is; that is, the Hamming distance from $r$ to $c'$ is at most $e$. By the triangle inequality, the Hamming distance between $c$ and $c'$ is at most $2e$. But $c$ and $c'$ are two different code words, so their Hamming distance it at least $d$. Therefore $2e\geq d$. Conclusion: In order for the decoder to produce an incorrect result, we must have $2e\geq d$, i.e., $e\geq d/2$. Therefore, as long as the number $e$ of errors is strictly smaller than $d/2$, the decoder won't err; any $(d-1)/2$ or fewer errors will be corrected.

Answer 3

Owen's answer appeals directly to the properties of the metric that are important, and that's the best way to do it. However, I usually motivate the explanation of how many errors can be corrected with some helper diagrams.

Keep in mind that these pictures are purely schematic, and don't accurately represent distances or how many words are near a particular codeword. (We can't expect to convincingly compress $n$ dimensions down into two anyhow.)

The idea of maximum likelihood decoding is to cover the entire space of words with nonoverlapping circles. Here is a picture of a portion of such a space:

This is meant to depict part of a code of minimum distance $7$. The dots on the intersections are possible words, the red dots are codewords, an the green dots are codewords falling on and within a circle of radius 3 around each codeword. Because the minimum distance is $7$, all of the radius $3$ circles will be nonoverlapping. If we receive a green word, then we should correct it to the red codeword in the center of the ball it lies in.

The black codewords aren't correctable in this scheme. If we increased the radii of the circles, things wouldn't work out, because circles would overlap and you would not know where to correct words landing in overlaps.

Why was $3$ the right choice? It's just the biggest integer you can pick so that these circles don't overlap. The theoretical "midpoint" of codewords spaced as close together as possible is $3.5$, and circles of radius $3.5$ would touch each other. However, in the Hamming distance, the distances are all integers, so you can bring the radius down to $3$.

Next, let's decrease the minimum distance to $6$, where I've drawn circles still with radius $3$. We will see there is a problem:

The yellow word turns out to lie on the border of two circles! It's not clear which circle it should go to, so this radius is too big for unambiguous correction. We need to now ratchet it back to a radius of $2$ instead of $3$.

So, keeping this picture in mind, one can come up with the formula for how many errors a distance $d$ code can correct. When $d$ is odd, the halfway radius between codes minimum distance apart is a half-integer, so you can afford to reduce to $\frac{d-1}{2}$ from $\frac{d}{2}$. When $d$ is even, the halfway radius is going to allow a correctable word to sit on the edge of two correction circles, so it is too large. Knocking it down to $\frac{d-1}{2}$ prevents this overlap, so that you can correct all errors unambiguously.

Answer 4

Maybe a small example will help. A simple block code with distance three is the two words $000, 111$. Since $d=3,$ it should be able to correct any $1$ bit error. In fact, changing one bit of either code word lets you still interpret the message correctly by taking the majority vote.

Answer 5

Suppose we have a distance 4 code. C1 and C2, two valid codewords, are separated by 3 invalid codewords X1 X2 X3 :

C1 X1 X2 X3 C2

1 error is easy to correct: X1 is corrected into C1, X3 into C2.

2 errors cannot always be corrected. X1 and X3 are corrected into C1 and C2, but should X2 be corrected into C1 or C2 ?

No way to know. It's at a the same distance from C1 and C2. So a distance 4 code cannot fully correct 2 errors.

Now with with a distance 5 code:

C1 X1 X2 X3 X4 C2

X2 can be corrected into the closest valid code C1. And X3 into C2.

So generally to correct k errors there should be at least 2k values between any two valid codewords. So the distance between 2 valid codewords should be at least 2k+1
Hence d >= 2k+1 and k <= (d-1)/2