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!

  • 0
    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.2012-10-08

1 Answers 1

3

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.

  • 0
    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.2012-10-08