Is there a $(6,9,3)_2$ code?

Question

Does there exist a $1$-error-correcting binary code with block length $6$ and $9$ codewords?

• The Hamming bound says that for any code $C$ with those parameters, $|C| \le \frac{2^6}{1+6} \approx 9.14$. So, we can't rule out the existence of such a code using the Hamming bound.

• The Singleton bound says that for any code $C$ with those parameters, $|C| \le 2^{6-3+1} = 16$, so we can't rule out the existence of such a code using the Singleton bound.

• Also, this can't be a linear code, since $\log_2 9$ isn't an integer. That rules out the possibility of just enumerating the possible generator matrices.

I feel a bit silly asking this, but the direct approach (assume $000\ 000$ is in the code, then all others must have Hamming weight $\ge 3$, ...) becomes unmanageable quickly. How else can I go about this?

Answer 1

By adding a parity bit / puncturing in any non-constant coordinate (i.e. in this coordinate, both symbols $0$ and $1$ appear in some codeword), a $(6,9,3)_2$ code exists if and only if a $(7,9,4)_2$ code exists. For a $(7,9,4)_2$-code, the Plotkin bound yields the contradiction $$4 = d \leq \frac{n\cdot \left|C\right| \cdot (q-1)}{(\left|C\right|-1)\cdot q} = \frac{7 \cdot 9\cdot 1}{8\cdot 2} \approx 3.94.$$ So there is no $(7,9,4)_2$ code and no $(6,9,3)_2$ code.

A convenient tool on questions like this is the internet table for small binary block codes. According to it, the maximum size for a binary code of length $7$ and distance $4$ is $8$, so again, there is no $(7,9,4)_2$ code.

In fact there is only a single isomorphism class of a $(6,8,3)_2$ code, and moreover it is linear (if translated such that the zero word is in the code). The code of joriki has the generator matrix $$\begin{pmatrix}1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1\end{pmatrix}.$$

Answer 2

Here's code that performs an exhaustive search for such a code and doesn't find one. It does find a $(6,8,3)_2$ code:

000000
111000
100110
011110
010101
101101
110011
001011