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!
Best Answer
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.