Why double error correction and quadruple error detection cannot occur at the same time?

Question

What does [ we cannot both correct double errors and detect quadruple errors because this would require us to interpret a received codeword in two different ways] means? I understand how double error correction works but I cannot imagine quadruple error detection. Can anybody show me example why double error correction and quadruple error detection cannot occur at the same time because it requires different interpretation?

For example, if double error correction occur,

will be something like this. How about quadruple error detection?

This is an excerpt from Computer Network Book by Andrew S. Tanenbaum

The data link layer(chapter 3), Page 208, Fifth edition.

Answer 1

Your interpretation is mistaken. Both properties are satisfied at the same time, since they are properties of the code itself.

In more detail, using the notation $d(x,y)$ for the Hamming distance between $x,y$:

• If $x$ is the sent codeword, $y$ is the received codeword, and $0 \leq d(x,y) \leq 4$, then we would be able to detect that $y \neq x$. This is quadruple error detection.

• If $x$ is the send codeword, $y$ is the received codeword, and we are promised that $0 \leq d(x,y) \leq 2$, then we can recover $x$ from $y$. This is double error correction.

Rephrasing:

• If there were errors in the channel but at most 4, we will be able to detect that errors occurred.
• If there were errors in the channel but at most 2, we can not only detect that errors occurred, but also determine their locations.

In the second case, we both detect that errors occurred, and are able to undo them. In that sense, we can both detect and correct errors at the same time.

Your quote is trying to make a different point. Given a codeword $y$, what can you do with it?

• You can try to detect whether errors occurred. This detection is guaranteed to be successful if up to 4 errors have occurred.
• You can try to determine the sent codeword $x$. This will be successful if up to 2 errors have occurred.

In practice, this is used in the following way:

• It is highly unlikely that more than 4 errors occur (or this is taken care of in some other way). Your error-handling strategy is to detect whether any errors occurred, and if so, ask the sender to resend the message.
• It is highly unlikely that more than 2 errors occur (or this is taken care of in some other way). Your error-handling strategy is to silently correct the errors, without communicating with the sender.

The two strategies are mutually exclusive, since the error detection mechanism doesn't differentiate between the case in which the number of errors is 0,1,2 and the case in which the number of errors is 3,4. So if you assume that there are at most 4 errors, you have no way of knowing whether the input can be corrected (there were up to 2 errors) or not.

The author doesn't mention a third approach, list decoding, which allows you to handle more errors as part of a longer communication protocol. In list decoding, you get a small "list" of possible sent messages, which you winnow down in some other way. I don't know whether this is actually used in practice, but it has been very influential in coding theory and theoretical computer science.

Answer 2

With a hamming distance of five, you can make one of two assumptions:

A. No word has more than four errors. Since you need five changes to get from one valid word to another valid word, and five errors don’t happen, every invalid word has 1 to 4 errors.

B. No word has more than two errors. If you find an invalid word, then it has at most two changes from a valid word. To reach any different valid word would take at least 3 more changes, so there is only one valid word within two changes, so you can fix the errors.

But you can’t assume both at the same time. If you find an invalid word, it could have two or four errors, and trying error correction would give you a totally wrong result.

If you have a hamming-distance of 7, you can indeed detect up to four errors and fix up to two errors at the same time. A word with four or three errors cannot be made valid with 1 or 2 changes, so you can detect 3 or 4 errors without being able to fix them, and you can fix 1 or 2 errors.