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 the various upper bounds for different types of codes. Recently, I came across a statement that is similar to the Singleton Upper Bound that I am having trouble proving. The statement is as follows.

Let $\mathcal{C}$ be an $[n, k, d]$ linear binary code. If $k \geq 5$ and $d \geq 3$, then $k \leq n - d - 1$.

My strategy has been to assume $k > n - d - 1$ and arrive at a contradiction using the fact that $d \geq 3$ and $k \geq 5$, but I'm not having any luck.

Any suggestions would be greatly appreciated. Thank you!

EDIT

Instead of my original strategy, I've been looking at the $k \times n$ generator matrix $G$ of $\mathcal{C}$ in standard form along with the $(n-k) \times n$ parity check matrix $H$ and using the fact that $d \geq 3$ means that the columns in $H$ are nonzero and distinct. Since $H$ has $n-k$ rows, then it can have at most $2^{n-k} - 1$ columns. I haven't been able to make any progress from this point using the fact that $k \geq 5$.

share|improve this question
3  
The $[8,4,4]$ extended binary Hamming code and the $[n,n-1,2]$ single parity check code show that the bound does not hold if $k < 5$ or $d < 3$. –  Dilip Sarwate Oct 19 '12 at 2:33
1  
Thanks Dilip. I was also able to find similar counter-examples to show that the bound doesn't hold for $d < 3$ and $k < 5$. I am having trouble showing that it will always hold for $d \geq 3$ and $k \geq 5$. –  josh Oct 19 '12 at 15:07
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.