3
$\begingroup$

I've been reading about upper bounds for codes, and I'm currently looking at constant weight codewords.

A $(n, M, d)$ code $\mathcal{C}$ over $\mathbb{F}_q$ is a constant weight code provided every codeword was the same weight $w$. Furthermore, $A_q(n, d, w)$ denotes the maximum number of codewords in a constant weight $(n, M)$ code over $\mathbb{F}_q$ of length $n$ and minimum distance at least $d$ whose codewords have weight $w$. Then, the text introduces the Restricted Johnson Bound for $A_q(n, d, w)$ and proves it.

From here, there are several problems in the text. One problem in particular deals with $A_2(10, 6, 4)$. By using the Restricted Johnson Bound, I am able to show that $A_2(10, 6, 4) \leq 5$. To show that $A_2(10, 6, 4) = 5$, I have to construct a $(10, 5, 6)$ constant weight binary code with codewords of weight $4$.

I am having trouble with this construction and was wondering if anyone could help me out. Any help would be greatly appreciated!

$\endgroup$
2
  • $\begingroup$ Two binary codewords of weight $4$ at distance $6$ from each other must have a common $1$ in exactly one position, right? So for starters, here are three such codewords $$1111000000\\1000111000\\1000000111$$ Can you find two more? $\endgroup$ Oct 8, 2012 at 1:54
  • $\begingroup$ I've been writing down various 4-weighted codewords for quite some time, and I have yet to find another codeword such that it shares a 1 with every previous codeword and maintains a distance of 6 with every other codeword. $\endgroup$
    – josh
    Oct 8, 2012 at 3:41

1 Answer 1

3
$\begingroup$

Two binary codewords of weight $4$ at distance $6$ from each other must have a common $1$ in exactly one position, right? So for starters, here are three such codewords $$1111000000\\1000111000\\1000000111$$ Can you find two more? You cannot. So let us back up a little bit and think some more since three codewords sharing a common $1$ in the same position does not work. What if we chose the five putative codewords so that for any given codeword, the other four had a common $1$ in four different positions? So, now we have $$1111000000\\1000111000$$ as before, but now codeword #3 shares a $1$ in position $2$ with codeword #1 and a $1$ in position $5$ with codeword #2, so that the first three codewords are $$1111000000\\1000111000\\0100100110$$ The fourth codeword shares a $1$ in positions $3,6,8$ with codewords #1, #2, #3 respectively giving $$1111000000\\1000111000\\0100100110\\0010010101$$ Can you now figure out the fifth codeword? Which positions have not been used thus far for sharing?


Note that there are $\binom{5}{2} = 10$ pairs of codewords and each pair shares a $1$ in a different position.

$\endgroup$
1
  • $\begingroup$ Following your method, the last codeword would be $0001001011$. Thank you again Dilip for the answer! It's intersting that the resulting $5$ codewords have exactly two $1$'s in every column, and the pairs of $1$'s run through every unique pair in "order" from top to bottom. $\endgroup$
    – josh
    Oct 8, 2012 at 13:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .