Checking if a linear code exists - singleton , hamming and gilbert-varshamov bounds do not help.

Question

Suppose I want to check if a (11, 6, 4) code exists.

I cannot prove non-existence using the singleton and the hamming bound. I also cannot prove existence using the gilbert-varshamov bound. I'm not sure what is the best way to go then - shall I just try to create a parity-check matrix?

Answer 1

I tried to simply create a parity check matrix for the code and it turned out to be quite easier than I thought.

Assuming $r = n - k = 5$

$$ H=\left(\begin{array}{l} 11100\\ 01110\\ 00111\\ 10011\\ 11001\\ 11111\\ 10000\\ 01000\\ 00100\\ 00010\\ 00001 \end{array}\right) $$

Any 3 $(d-1)$ rows are linearly independent and there is at least one set of of 4 $(d)$ linearly dependent rows.

Answer 2

An extended Hamming code has parameters $(16,11,4)$. By shortening it in five positions you get the desired $(11,6,4)$-code. The process can also be described as follows. Let $C$ be that $(16,11,4)$-code. Select a set of five bit positions. Let $C'$ be the subspace consisting of those words of $C$ that have a zero at all those five positions. This amounts to adding five extra parity checks, so $C'$ is a linear code. Because all the words of $C'$ are also words of $C$, its minimum weight is still $\ge4$. Because we place 5 extra parity checks, the dimension of $C'$ is at least $11-5=6$. Finally, if we throw away the five shared zeros of all the words of $C'$, we get a code of length $11$.

---

Equivalently you can just throw away any five columns from the parity check matrix $$ H=\left(\begin{array}{l} 1111 1111 1111 1111\\ 0000 0000 1111 1111\\ 0000 1111 0000 1111\\ 0011 0011 0011 0011\\ 0101 0101 0101 0101 \end{array}\right) $$ of the $(16,11,4)$ extended Hamming code.