4
$\begingroup$

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$.

$\endgroup$
4
  • 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$ Commented Mar 13, 2013 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
    Commented Mar 13, 2013 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$ Commented Mar 13, 2013 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$
    – 2'5 9'2
    Commented Mar 14, 2013 at 17:47

1 Answer 1

2
$\begingroup$

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.)

$\endgroup$
7
  • $\begingroup$ Oops, $32-24=8$, not $6$. So I just edited to account for that. $\endgroup$
    – 2'5 9'2
    Commented Mar 13, 2013 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
    Commented Mar 13, 2013 at 23:06
  • 1
    $\begingroup$ What does "$4$ codes without errors" mean? $\endgroup$ Commented Mar 13, 2013 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$
    – 2'5 9'2
    Commented Mar 14, 2013 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$ Commented Mar 14, 2013 at 2:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .