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

| cite | improve this answer | |
$\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 '19 at 11:26
  • $\begingroup$ @siegi, thanks. Updated. $\endgroup$ – John L. Feb 20 '19 at 14:06
  • $\begingroup$ @Miangu Was my answer helpful? Have you considered accepting it? (This comment will be deleted upon feedback.) $\endgroup$ – John L. May 15 at 23:46
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)$.

| cite | improve this answer | |
$\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$ – John L. Feb 20 '19 at 6:22
  • 1
    $\begingroup$ The subscript signifies the field $\mathbb{F}_2$. $\endgroup$ – Yuval Filmus Feb 20 '19 at 6:22

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.