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$

2 Answers 2

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
  • 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, 2019 at 11:26
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$
2
  • 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, 2019 at 6:22
  • 1
    $\begingroup$ The subscript signifies the field $\mathbb{F}_2$. $\endgroup$ Feb 20, 2019 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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