Group theory / codes

Question

Show that there is no linear code $D$ with $4$ words over $V(4,2)$ that can correct single errors then contrust a linear code $E$ with $4$ words over $V(5,2)$ that can correct single errors.

What I have so far:
a)Let's assume $\exists D: D=\{a_1,a_2,a_3,a_4\}$ and $D$ can correct single errors.

• $\Rightarrow (d-1)\div2=1 \Rightarrow d=3 \Rightarrow \forall b,c \in D, d(b,c)\geq3$ and $\forall b \in D, w(b)\geq3$
  
• $a_1=0000$ must satisfy $a_1\in D \Rightarrow a_2,a_3,a_4 \in \{0111,1011,1101,1110,1111\}$
  
• Since $D$ is a code, $\forall b,c \in D,(b+c)\in D$
  
• Is is then enough to show that $\nexists$ a combination of these codewords : their sum is also a codeword?
  

b) To construct a code word $E=\{e_1,e_2,e_3,e_4\}:E$ can correct single errors

• By the same arguments as a bove, $d= 3\Rightarrow \forall b,c \in E, d(b,c)\geq3$ and $\forall b \in E, w(b)\geq3$
  
• $e_1=00000$ must satisfy $e_1 \in E$ $\Rightarrow e_4,e_2,e_3 \in \{00111,01110,11100,10101,10011,11001,11110,11101, 11011,10111,01111,11111\}$
• To contrust the code, do I just work by trial and error by choosing combinations that will give me codewords or is there a more efficient method?
  I have done it by trial and error and I have a code $E=\{00000,00111,11001 ,11110\}$ which satisfies everything above so it's not the answer that I'm searching for but a less exhaustive method.
  Thank you.

Answer 1

For (a): yes, you need to show you cannot pick two such codewords such that their linear span is $1$-error correcting, i.e. has no codewords of weight $<3.$

I think your proofs are fine, but I will just mention some connections to more general ideas that you might find interesting.

First of all, you can pretty much characterize $1$-error correcting codes as Hamming codes. Hamming codes are optimal in a sense, and by comparing with Hamming codes you can see that you can't have such a $4$-word code in $V(4,2)$; and by restricting the $2^4$-codeword Hamming code in $V(7,2)$ you can get a $4$-word code in $V(5,2).$

Hamming codes are optimal in the sense that they meet the sphere packing bound, and you can use the sphere packing bound directly to prove (a).

One way to construct and analyse Hamming codes is via the dual code, or parity check matrix. The condition on the parity check matrix is that no column is zero and no two columns are linearly independent (i.e. equal, for binary codes). You can check that a $4\times 2$ matrix cannot have this property, which a $5\times 3$ matrix can.

A small fact that you might find useful is that at least half the codewords of a binary linear code have even weight. For (a) this means you would have to have $1111$ as a codeword, which cuts down the possibilities. Another trick is that the linear group acts transitively on the non-zero vectors in $V(2,2)$ - this can help cut down the number of options to consider.

Answer 2

The hamming sphere around any vector $a \in V(4,2)$ with radius 1 has $$\binom{4}{0}+\binom{4}{1}=5,$$ vectors.

All these spheres must be disjoint for the code to be $1-$error correcting, which then would require the space $V(4,2)$ to have $5\times 5=25,$ vectors in total. But this is a contradiction since it has only $2^4=16$ vectors.

Thus there is no linear or nonlinear code satisfying your requirements.

When you consider $V(5,2)$ the computation of the required number of points becomes $$ 4\times \left(\binom{5}{0}+\binom{5}{1}\right)=24<2^5, $$ which suggests this may be possible.

Then you can apply the linear independence property pointed out by the answer by @Dap, to complete the argument.