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

Answer 3

For a binary codeword of length $6$, there are $4$ choices for the last two coordinates: $00,01,10$ or $11$. Now assume that, there is a binary code with nine codewords. But then, at least three of the codewords must have the same the last two coordinates by pigeonhole principle. However, three codewords having the same last two coordinates cannot satisfy the given minimum distance since they must satisfy the same minimum distance for length $4$. Hence, there is no $(6,9,3)_2$ code.