Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
    
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. –  joriki Feb 27 '13 at 0:06
    
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). –  azimut Feb 27 '13 at 12:32
    
Whence that condition? Wouldn't you also get a $(6,9,3)_2$ code by removing a coordinate with all zeros? –  joriki Feb 27 '13 at 13:45
    
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. –  azimut Feb 27 '13 at 15:01
    
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$. –  joriki Feb 27 '13 at 15:13
show 2 more comments

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
share|improve this answer
add comment

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.

share|improve this answer
    
+1 for this very nice argument! –  azimut May 12 '13 at 10:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.