9
$\begingroup$

The problem is to prove or disprove the existence of $C$, s.t., $|c| = 6,\forall c\in C$; $|C| = 32$; $d(c_i,c_j)\geq2,1\leq i<j\leq32$. ($d$ stands for hamming distance)

I tried to construct a satisfying code. The best I can get is to let $C = C'\times C'$, a concatenation of $C' = \{000,011,110,101\}$, which is of size 16. 32 happens to be the theoretical upper bound of the size, now I don't know what to do next so as to solve the problem.

$\endgroup$
9
$\begingroup$

Yes, there is such a set. You are actually on the right track to find the following example.

Let $C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$. You can check the following.

  • $|C|=32$.
  • $d(u,v)\geq2$ for all $u,v\in C$, $u\not=v$. (In fact, $d(u,v)=2$ or 4 or 6.)

Here are four related exercise, listed in the order of increasing difficulty. As in the question, only binary code is concerned.

Exercise 1. Give another example of a set of 32 words of length 6 and pairwise distance at least 2.

Exercise 2. Show that there are only two such sets, as given in the answer and in the exercise 1.

Exercise 3. Generalize the above to words of any given length and pairwise distance at least 2. (Hint, $32=2^{6-1}$.)

Exercise 4. (further generalization stated in Yuval's answer) If $A(n,d)$ is the maximum size of a code of length $n$ and minimum pairwise distance $d$, then $A(d,2d)=A(n-1,2d-1)$.

$\endgroup$
  • 1
    $\begingroup$ I think $d(u,v)$ may also be 6, specifically for $u=000000$ and $v=111111$, as both $u\in C$ and $v\in C$ because both have even number of 1's. Or am I missing something? $\endgroup$ – siegi Feb 20 at 11:26
  • $\begingroup$ @siegi, thanks. Updated. $\endgroup$ – Apass.Jack Feb 20 at 14:06
7
$\begingroup$

All words of even parity from a linear code with $2^{n-1}$ codewords and minimum distance $2$.

More generally, if $A_2(n,d)$ is the maximum size of a code of length $n$ and minimum distance $d$, then $A_2(n,2d) = A_2(n-1,2d-1)$.

$\endgroup$
  • 1
    $\begingroup$ Nice fact, upvoted. By the way, why not just $A(n,d)$ instead of $A_2(n,d)$? Oh, two letters. $\endgroup$ – Apass.Jack Feb 20 at 6:22
  • 1
    $\begingroup$ The subscript signifies the field $\mathbb{F}_2$. $\endgroup$ – Yuval Filmus Feb 20 at 6:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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