Existence of linear code with length $7$, dimension $4$ and distance $4$

Question

Suppose I want to construct a linear node such that the code has length $7$, dimension $4$ and distance $4$. Before constructing such a code, we need to prove the existence of the code. But I don't know how to prove it. Can anyone guide me?

Answer 1

If your code is meant to binary, I need to break you some bad news - such a code does not exist. This is strongly hinted by the fact that the $(7,4,3)$ Hamming code is perfect - and you are aiming at improving it!

A two-line proof of non-existence would be to refer to the Griesmer bound stating that a binary linear code with parameters $(n,k,d)$ satisfies the inequality $$ n\ge\sum_{i=0}^{k-1}\left\lceil\frac d{2^i}\right\rceil. $$ With $d=k=4$ this gives $$ n\ge4+2+1+1=8. $$

---

If your alphabet is a field with at least $7$ elements, then you CAN construct such a code by shortening/puncturing a Reed-Solomon code.

For example over $\Bbb{F}_{16}$ we can do the following. Let $\gamma\in\Bbb{F}_{16}$ be a zero of the polynomial $x^4+x+1$. This is a primitive element of this field. See this answer for the related discrete logarithm table, and how to do arithmetic in this field.

A possible generator polynomial for a Reed-Solomon code is then $$ \begin{aligned} g(x)&=(x-1)(x-\gamma)(x-\gamma^2)=x^3+(1+\gamma+\gamma^2)x^2+(\gamma+\gamma^2+\gamma^3)x+\gamma^3\\ &=x^3+\gamma^{10}x^2+\gamma^{11}x+\gamma^3. \end{aligned} $$ Thus the matrix $$ G=\left(\begin{array}{ccccccc} \gamma^3&\gamma^{11}&\gamma^{10}&1&0&0&0\\ 0&\gamma^3&\gamma^{11}&\gamma^{10}&1&0&0\\ 0&0&\gamma^3&\gamma^{11}&\gamma^{10}&1&0\\ 0&0&0&\gamma^3&\gamma^{11}&\gamma^{10}&1 \end{array}\right) $$ generates a $(7,4,4)_{16}$ code.