12
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Nice solution; more insightful than mine :-) When you say "adding / removing a parity bit", I suppose you mean "adding a parity bit or removing an arbitrary bit"? At least I don't see why the $(7,9,4)_2$ code should have a parity bit. $\endgroup$ – joriki Feb 27 '13 at 0:06
  • 1
    $\begingroup$ Thank you. Yes, you are right, "removing a parity bit" is a bit misleading. I'll edit my answer. What I mean is: You puncture the code in the $i$-th coordinate (i.e. remove the $i$-th coordinate from all codewords). The only condition is that not all codewords are zero in this coordinate (if $C$ has more than 1 codeword, there is always such a coordinate; for good codes typically each single coordinate is fine). $\endgroup$ – azimut Feb 27 '13 at 12:32
  • $\begingroup$ Whence that condition? Wouldn't you also get a $(6,9,3)_2$ code by removing a coordinate with all zeros? $\endgroup$ – joriki Feb 27 '13 at 13:45
  • $\begingroup$ You get a $(6,9,4)_2$ code then. Of course, you could immediately "worsen" it to a $(6,9,3)_2$ code by flipping some bit in a minimum weight codeword (assuming that the zero-word is in the code. $\endgroup$ – azimut Feb 27 '13 at 15:01
  • $\begingroup$ Interesting -- I hadn't realized that I was slightly misusing the notation and calling anything a $(6,9,3)_2$ code that has distance at least $3$. $\endgroup$ – joriki Feb 27 '13 at 15:13
7
$\begingroup$

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.

$\endgroup$
0
6
$\begingroup$

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
$\endgroup$
0

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.