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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!


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|cite|improve this question
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
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

Your Answer


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

Browse other questions tagged or ask your own question.