I have the following error correcting code: $$\begin{array}{c|c} 00&00000\\ 01&01101\\ 10&10110\\ 11&11011 \end{array}$$

I should show, that every error at 2 positions cannot be (unique) corrected.

So the code 00111 can correlate with 01 or with 10.

The obvious proof, is to check every possible error, but I guess, there have to be something nicer.

I know, that every $a\in \{0,1\}^5$ has a hamming-distance $<=1$ to one of the code words, except 10001 and 01010. Can I somehow use this fact?

EDIT: Today our tutor showed us a really short and simple solution.

If you look at the matrix of the error-free codes, $$\begin{array}{ccccc} 0&0&0&0&0\\ 0&1&1&0&1\\ 1&0&1&1&0\\ 1&1&0&1&1 \end{array}$$ you can notice that there are exactly two 1s and two 0s in each column. If we take one of the 4 codes and add one error, the hamming-distance to two of the other tree codes will be decrease by 1, and the hamming-distance to the third word will be increase by 1. If we repeat this procedure, the same thing will happen. Because there are only three other code-words, the hamming-distance to one of the three will be decrease by 2 (pigeonhole principle). The max. hamming-distance beweet two of the code-words is $\le 4$, so there exists a code-word with hamming-distance $\le 4-2 = 2$.

  • 1
    $\begingroup$ I would just go with $00111$. $11000$ also works, but go with the one you found yourself! I think that is nice enough. $\endgroup$ – Jyrki Lahtonen Mar 13 '13 at 21:09
  • $\begingroup$ I have to show, that there doesn't exists any code, which cannot be unique corrected (!), not that is not possible for a single one. $\endgroup$ – Jakube Mar 13 '13 at 21:22
  • $\begingroup$ If the problem is to prove that there can't be a length 5 double-error-correcting code, then that's what you should say in the body of thequestion, not in the comments. But maybe I have misunderstood --- I'm sorry, but what you are writing is not very clear. $\endgroup$ – Gerry Myerson Mar 13 '13 at 22:48
  • $\begingroup$ It seems like this solution demonstrates a way to make a code word that cannot be uniquely corrected, rather than showing that every error-2 code word cannot be uniquely corrected. $\endgroup$ – alex.jordan Mar 14 '13 at 17:47

In $\{0,1\}^5$, there are $4$ code words without error. Each error-free code word is adjacent to $5$ code words with exactly one error. By observation of the $\binom{4}{2}=6$ pairs of error-free code words, no code word with one error is adjacent to two error-free code words, since the pairwise differences of the error-free code words have at least three 1's. At this point we have counted that the error-free code words and the error-1 code words account for $24$ codes, leaving $8$ code words which have error $\ge2$.

If we could identify these $8$ code words and demonstrate that each is distance 2 from two error-free code words, I believe we have established what you are trying to establish. Comments have identified two of the offending code words; can you find four more?

Again by observation, 00000 and 11011 are 4 units apart. So there are $\binom{4}{2}$ code words that are halfway between them: 11000, 10010, 10001, 01010, 01001, and 00011. By observation of comparison with the other two error-free code words, some of these are in fact error-2 code words: 11000, 10001, 01010, and 00011. We only have four error $\ge2$ code wordsleft to find and verify that they cannot be corrected uniquely. Now look again for a pair of error-free code wordsthat are distance 4 from each other...

01101 and 10110 are four units apart. Midway between them are 10101, 11111, 11100, 00111, 00100, and 01110. Of these, comparison with the error-free code wordsconfirms that 10101, 11100, 00111, and 01110 are in fact error-2.

In summary, we have identified all of the error-2 code wordsas lying halfway between two error-free code words, 2 units away from them making all of these 8 code wordsnot have unique corrections:

11000, 10001, 01010, and 00011 are between 00000 and 11011,

10101, 11100, 00111, and 01110 are between 01101 and 10110.

(We've also ruled out code words with error greater than 2.)

  • $\begingroup$ Oops, $32-24=8$, not $6$. So I just edited to account for that. $\endgroup$ – alex.jordan Mar 13 '13 at 23:02
  • $\begingroup$ Thanks, this answer was very helpful. 01101 and 10110 have hamming-distance 4. So the other 4 error-2 codes are: 00111, 11100, 10101 and 01010. $\endgroup$ – Jakube Mar 13 '13 at 23:06
  • 1
    $\begingroup$ What does "$4$ codes without errors" mean? $\endgroup$ – Dilip Sarwate Mar 13 '13 at 23:20
  • $\begingroup$ @Dilip The four given codes 00000, 01101, 10110, 11011 are considered error-free. I am referring to every member of $\{0,1\}^5$ as a "code". The four designated codes are error-free. For other codes, the number of errors is taxicab distance from that code to the nearest error-free code. $\endgroup$ – alex.jordan Mar 14 '13 at 0:43
  • 2
    $\begingroup$ @alex.jordan The usual meaning of code in the theory of error-correcting codes is a subset of $\mathbb F^n$. If the cardinality of the subset is $M$, we have a $(n,M)$ code, and when the subset is a $k$-dimensional subspace $\mathbb F^n$, it is called a $[n,k]$ linear code over $\mathbb F$. What you call code is generally referred to as a codeword. In this instance, we have a $[5,2]$ code over $\mathbb F_2$, and it is to be proved that there is no vector in $\mathbb F_2^5$ at Hamming distance $2$ from one codeword and at Hamming distance $\geq 3$ from the other three codewords. $\endgroup$ – Dilip Sarwate Mar 14 '13 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.