Does a binary code with length 6, size 32 and distance 2 exist?

Question

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.

Answer 1

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

Answer 2

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