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$

3 Answers 3

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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 15:13
7
$\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
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

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.