Coding theory (existence of codes with given parameters)

Explain why each of the following codes can't exist:

1. A self complementary code with parameters $(35, 130, 15)$. (I tried using Grey Rankin bound but 130 falls within the bound)

2. A binary $(15, 2^8, 5)$ code. (I tried Singleton Bound but no help)

3. A $10$-ary code $(11, 100, 10)$ subscript 10. (I tried using Singleton Bound but again, it falls within the bound)

Solution 1:

Let me elaborate on problem #2. As I said in my comment that claim is wrong, because there does exist a binary code of length 15, 256 words and minimum Hamming distance 5.

I shall first give you a binary $(16,256,6)$ code aka the Nordstrom-Robinson code.

Consider the $\mathbf{Z}_4$-submodule $N$ of $\mathbf{Z}_4^8$ generated by the rows of the matrix $$ G=\left( \begin{array}{cccccccc} 1&3&1&2&1&0&0&0\\ 1&0&3&1&2&1&0&0\\ 1&0&0&3&1&2&1&0\\ 1&0&0&0&3&1&2&1 \end{array}\right). $$

Looking at the last four columns tells you immediate that $N$ is a free $\mathbf{Z}_4$-module with rows of $G$ as a basis, and therefore it has $256$ elements. It is easy to generate all 256 them, e.g. by a fourfold loop. Let us define a function called the Lee weight $w_L$. It is a modification of the Hamming weight. We define it first on elements of $\mathbf{Z}_4$ by declaring $w_L:0\mapsto 0$, $1\mapsto 1$, $2\mapsto 2$, $3\mapsto 1$, and then extend the definition to vectors $\vec{w}=(w_1,w_2,\ldots,w_8)$ by $$ w_L(\vec{w})=\sum_{i=1}^8w_L(w_i). $$ It is now relatively easy to check (e.g. by listing all the 256 elements of $N$, but there are also cleaner ways of doing this) that for any non-zero $\vec{w}\in N$ we have $w_L(\vec{w})\ge 6$.

Then we turn the $\mathbf{Z}_4$-module $N$ into a binary code. We turn each element of $\mathbf{Z}_4$ to a pair of bits with the aid of the Gray mapping $\varphi:\mathbf{Z}_4\rightarrow \mathbf{Z}_2^2$ defined as follows: $\varphi(0)=00$, $\varphi(1)=01$, $\varphi(2)=11$, $\varphi(3)=10$. We then extend this componentwise to a mapping from $\mathbf{Z}_4^8$ to $\mathbf{Z}_2^{16}$. For example, the first generating vector becomes $$ \varphi: 13121000 \mapsto 01\ 10\ 01\ 11\ 01\ 00\ 00\ 00. $$ The mapping $\varphi$ is not a homomorphism of groups, so the image $\varphi(N)$ is not a subgroup of $\mathbf{Z}_2^{16}$, i.e. $\varphi(N)$ is not a linear code. However, we make the key observation that $\varphi$ is an isometry. Basically it turns the Lee weight into Hamming weight. So if $\varphi(\vec{w})$ and $\varphi(\vec{w}')$ are two distinct elements of $\varphi(N)$, then $$ d_{Hamming}(\varphi(\vec{w}),\varphi(\vec{w}'))=w_L(\vec{w}-\vec{w}')\ge6. $$ It is easy to show this by first checking that this relation holds for all pairs of elements of $\mathbf{Z}_4$. As the corresponding function on vectors is the componentwise sum, the relation holds for vectors as well.

Therefore $\varphi(N)$ is a (non-linear) binary $(16,256,6)$ code.

Finally, we get at a non-linear binary $(15,256,5)$-code by dropping, say, the last bit from all the vectors of $\varphi(N)$.