Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I recently posted a question if it was possible to extend a code with odd minimum distance in some other way than the single parity check if you want to increment the minimum distance. This question has a similar flavor.
Given a $(k+1,k,2)_2$ single parity check code with $k>1$, is it possible to extend this to a $(k+2,k,3)_2$ code? I am pretty confident the answer is no but I'm not sure how to prove it.
This will not be possible because the new code would be MDS. It is known that such codes do not exist for $n>k+1$.
Supplementing Benjamin Lindqvist's answer with the details of how this can be shown in this case from first principles. All this assuming that the codes are to be binary for larger field alphabets the claim is false.
Assume that a binary linear code $C$ of length $n=k+2$, dimension $k$ and minimum distance $d\ge3$ exists. The code is defined by two check equations, so its parity check matrix $H$ has type $2\times n$. In particular its columns consist of two bits each, so they all are one of $\binom 0 0$, $\binom 0 1$, $\binom 1 0$, $\binom 1 1$.
Obviously $H$ cannot contain a column $\binom 0 0$. For if column $i$ were all zeros, then the code $C$ would have a word of weight one, with the sole $1$ at position $i$. Less obvious but still not difficult to see is that $H$ cannot have two equal columns. For if the columns $i$ and $j$ were equal, then the vector $x$ of weight two with ones at positions $i$ and $j$ would satisfy the equation $Hx^T=\binom 0 0$. Meaning that $x\in C$, in violation of the assumption that the minimum weight of $C$ is $\ge3$.
So all the $n$ columns of $H$ are non-zero and distinct. Therefore there can be at most three of them. In other words $3\ge n=k+2$ and $1\ge k$.
