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.

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!

share|improve this question
    
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? –  Dilip Sarwate Oct 8 '12 at 1:54
    
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. –  josh Oct 8 '12 at 3:41

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  josh Oct 8 '12 at 13:47

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.