Relative distance in Codes

Question

I'm studying coding theory. In my lecture we saw that Hadamard codes have an optimal relative distance of $1/2$. The relative distance of a code $C$ with minimum distance $d(C)$ and block length $n$ is defined by: $$\dfrac{d(C)}{n}.$$

According to this, the minimum distance for a Hadamard code with block length $n=2^k$ is $\dfrac{n}{2} = 2^{k-1}$. Is there any code $C$ with block length $n$ and minimum distance $d(C)>n/2$? How can I prove it?

Answer 1

Yes. There are such codes, but they necessarily have a very low rate. For example:

• The repetition code of length $n$ has minimum distance $n$. Its rank is one, so its rate is $\rho=1/n$.
• If $n=3t$ is a multiple of three, we have the binary linear codes of rank two and minimum distance $2n/3=2t$. You get the four words of this code by repeating each of the bit patterns $000, 011, 101$ and $110$ $t$ times.
• Similarly, the Griesmer bound tells us that if $d=4t$ is a multiple of four, then a rank-three binary linear code will have length at least $n=7t$. Such codes exist and are gotten by replicating the eight words of a $(7,3,4)$-code $t$ times. You get a $(7,3,4)$ code as the even weight subcode of the $(7,4,3)$ Hamming code. These codes have relative distance $4/7$.

Answer 2

It depends what kind of code you want. In its simplest form, a $q$-ary block code of length $n$ is just a subset of $\mathbf{F}_q^n$. Hence it is trivial to construct a block code of length $n$ with minimal distance $n$: $\{0^n,1^n\}$. This code is also linear, and even cylic.