Conditions for a $(n,k,d)_q$ code to have $d>n/2$

Question

This seems like such an silly question that I'm almost afraid to ask it.

Clearly some codes have $d>n/2$, for example the $(n,1,n)$ repitition code. But it doesn't seem possible to construct a binary code with $k=2$ that has $d>n/2$ (I haven't proven this, but it seems reasonable based on toying around with codebook matrices). So a reasonable conjecture would be that $d>n/2$ is possible if and only if $k<q$. Is this true?

Answer 1

I don't think the "if and only if" part of the conjecture is quite true. A minimum distance $d > n/2$ cannot be achieved for all $k < q$. A more reasonable conjecture would be that for $d$ to exceed $n/2$, it must be that $k$ is smaller than $n/2$, but even this is not supported by the evidence.

Consider the binary $[n,k,d] = [3,2,2]$ code with codewords $$000\quad 011\quad 101\quad 110$$ Both $k$ and $d$ have value $2$ exceeding $n/2 = 1\frac 12$.

A doubly-extended Reed-Solomon code over a finite field with $q$ elements has parameters $[n,k,d] =[q+1,k,q+2-k]$ where the distance $d$ equals $n-k+1$, that is, the Singleton bound is satisfied with equality.

• If $q$ is even, that is, the field has characteristic $2$, set $k = \frac{q+2}{2} > n/2$ to get a code with minimum distance $d = \frac{q+2}{2} > n/2$.

• If $q$ is odd, set $k=\frac{q+1}{2} = n/2$ to get a code with minimum distance $d = \frac{q+1}{2} + 1 > n/2$

Answer 2

Supplementing Dilip's answer with the observation that for low dimensional codes the Griesmer bound is more accurate than the (in the binary world mostly useless) Singleton bound. For $q=2=k$ it implies that the minimum distance of a 2-dimensional binary linear code is at most $2n/3$. When $n=3m$ is a multiple of three the bound is achieved by the linear code gotten from Dilip's example $\{(000,110,101,011)\}$ by repeating all the bits (or blocks) $m$ times. The minimum distance of the resulting code with four words is obviously $2m$.