Find smallest possible n [n,60,4]

Question

I have linear binary code [n,60,4]. What is the smallest possible n I know that parity matrix H has every 3 columns linearly independent. Do I use $2^{n-60}-1\geq n$ or does the fact that every 3 columns are independent gives me something more specific. I mean if every 3 columns are independent then they are at least all different right?

Answer 1

If every 3 columns are linearly independent and 3 is the maximal such integer, the minimum distance of the code is at least 4 (since there exists a nonzero weight $\geq 4.$ vector in the kernel of $H$.)

Let us assume the minimum distance is actually $4.$ Then one can use various bounds to see how short an $n$ may work.

For example since spheres with radius $d/2$ must be disjoint we have

$$ 2^{60} \times \left(1+ \binom{n}{1} +\binom{n}{2}\right) \leq 2^{n}, $$ and this gives $n\geq 68.$

Answer 2

I might go about this as follows. Let's first puncture a single position. Then we get an $[n-1,60,3]$ code $C'$. The reason I wanted to puncture is that $3$ is a more convenient minimum distance to be handled by the criterion you described. You see, a parity check matrix $H'$ for $C'$ must have $n-1$ columns and $(n-1)-60=n-61$ rows. Furthermore, it suffices that any two columns of $H$ are linearly independent. That makes life easier because over the binary field two vectors are linearly independent if and only if they are non-zero and distinct.

So $H'$ has $n-1$ columns, all in the space $V=\Bbb{Z}_2^{n-61}$. For this to make sense we need $n>61$, in which case $V$ has $2^{n-61}-1$ non-zero vectors. We thus have the inequality closely related to the one you mentioned: $$ 2^{n-61}-1\ge n-1. $$ We see that $n=67$ fails, but just barely: $2^6-1=63<66$, so $n\ge 68$.

But to give a complete answer, we need to construct a $[68,60,4]$ code. This is easy by the process known as adding an overall parity check bit. We begin by selecting $67$ distinct non-zero vectors $h_1,h_2,\cdots,h_{67}$ from $V=\Bbb{Z}_2^7$. By the result you described, the code $C'$ defined by the parity check matrix $H'$ with columns $h_1,h_2,\ldots,h_{67}$ has parameters $[67,60,3]$ (it is easy to show that no matter how we selected those $67$ vectors the matrix $H'$ has full rank $7$).

As the polishing step we add a $68$th bit to all the $2^{60}$ words of $C'$ according to the scheme that the extra bit of the word $w$ is $0$ if $w$ has an even weight (necessarily $\ge4$) but it is $1$, if the weight of $w$ is odd (in which case the word $w1$ again has weight $\ge4$. The process preserves linearity so we get a linear code $C$ with parameters $[68,60,4]$.

Equivalently, we can add first add zero to the end of all the seven rows of $H'$ and then add an eighth row to the resulting matrix consisting of $68$ ones. The resulting matrix $H$ is then a parity check matrix of the code $C$ we constructed above. It is also easy to see why any three columns of $H$ are linearly independent. A set of three distinct vectors can only be dependent if their sum is the zero vector. The shared eight component of all the columns is one, making this impossible.