# 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)

-
We will not do your homework here. –  Listing Mar 6 '12 at 14:21
I've tried but failed..:( –  newbowl Mar 6 '12 at 14:26
I think that there is an error in problem #2. I'm interpreting your notation to mean that the codes don't need to be linear. There is a celebrated non-linear binary code called the Nordstrom-Robinson code. It has parameters $(16,256,6)$. If you puncture a single bit position of that code, you actually get a (non-linear) $(15,256,5)$ code! Your teacher may need to recheck his/her sources :-). –  Jyrki Lahtonen Mar 8 '12 at 7:11
The last exercise is also tricky. It is easy to construct $(n+1,n^2,n)_n$-codes when $n=9$ or $n=11$. This means that proving their non-existence in the case $n=10$ needs relatively powerful tools. I am tempted to say that the desired answer is simply to state that "There does not exist a finite field of ten elements, so the usual method does not work". The first and third parts have the air of combinatorial mess that I don't want to touch. This is one serious set of HW problems. I'm fairly sure that you are not supposed attack these armed with the Si(mp/ng)leton bound alone. –  Jyrki Lahtonen Mar 8 '12 at 10:57

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 Grey 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)$.

-