0
$\begingroup$

Show by arithmetical arguments that there cannot be a perfect binary code of length $n$ which corrects $e$ errors when:

(i) $n=5,e=1;$

(ii) $n=10,e=2;$

I'm not sure I understand what a perfect code is. My book says that for some code $C$ that corrects at most one error, $|C| \times (1 + n) \leq 2^n$. And for Hamming codes, this is an equality so $|C|$ attains its maximum value.

For Hamming codes $|C|=2^k$ where $k=2^r-1-r$ ($r$ is the number of rows in the check matrix), and $n+1=2^r$ so $|C| \times (1+n) = 2^k \times 2^r = 2^{2^r-1-r} \times 2^r = 2^{n+1 -1 -r + r}=2^{n}$.

So I see the equality they speak of. Every possible word is in $|C|$. But what does this have to do with error?

Attempt:

(i) If $e=1$ and we assume $2e+1= \delta$, the minimum distance in $C$, then $\delta=3$. So $C$ is a Hamming code. However, for a Hamming code, $n=2^r-1 \implies 6 = 2^r$, which is impossible since there are no nonnegative integer solutions for $r$.

(ii) $e = 2 \implies \delta = 5$. A perfect code must be a Hamming code, and for a Hamming code, $\delta = 3$. So this can't be a perfect code.

$\endgroup$
  • $\begingroup$ If an $e$-error-correcting code exists, then the Hamming spheres of radius $e$ centered at each codeword (i) are disjoint and (ii) together exhaust the space: every vector belongs to one (and only one) such Hamming sphere. Also, each such Hamming sphere has exactly $\sum_{i=0}^e \binom{n}{i}$ vectors in it. Now apply this idea to the question. $\endgroup$ – Dilip Sarwate Apr 30 '14 at 3:39
  • $\begingroup$ So in the first question, $n=5$ implies each Hamming sphere contains $n+1=6\neq 1$ vectors in it. But each word can only belong to one Hamming sphere, so there is a contradiction? $\endgroup$ – Bobby Lee Apr 30 '14 at 4:05
  • 1
    $\begingroup$ Yes. Figure out what the contradiction is, and then write up your solutions neatly and post them as an answer to your question. Yes, that is encouraged on this site. Some time later, you can even accept your own answer as the best answer to the question. $\endgroup$ – Dilip Sarwate Apr 30 '14 at 11:27
  • 1
    $\begingroup$ Carfeul there. A perfect code is not necessarily a Hamming code, so you cannot conclude that the length of a perfect code would be one less than a power of two. $\endgroup$ – Jyrki Lahtonen Apr 30 '14 at 12:55
  • 2
    $\begingroup$ @BobbyLee Read about the $[23,11]$ Golay code which is a perfect code with $e=3$. A Hamming code is perfect but with $e=1$. $\endgroup$ – Dilip Sarwate Apr 30 '14 at 13:21
1
$\begingroup$

Let $C$ be a linear code. For some $\textbf c \in C$, let $S_e(\textbf c)$ denote the set of vectors attained by altering up to $e$ bits in $\textbf c$.

A perfect code $C$ with vectors of length $n$ that corrects $e$ errors possesses the property $$\forall \textbf x \in V^n, \;\; \textbf x \in S_e(\textbf c) \text{ where } \textbf c \in C$$

In other words, every possible vector of length $n$ is some alteration (of up to $e$ bits) of a vector in $C$. If $C$ corrects $e$ errors, these $S_e(\textbf c)$ sets are disjoint such that

$$|C| \times |S_e(\textbf c)|=2^n$$

(i) $n=5,e=1$

In this case we have $|C| \times \sum_{i=0}^{1} {5 \choose i} = 2^5 \implies |C| \times 6=32$. So the cardinality of $C$ is not an integer, which is impossible.

(ii) $n=10,e=2$

Now we have $|C| \times \sum_{i=0}^{2} {10 \choose i} = 2^{10} \implies |C| \times 56=1024$. So the cardinality of $C$ is not an integer, which is impossible.

$\endgroup$

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.