2
$\begingroup$

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$.

  • 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$.2012-10-19

0 Answers 0