Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
5  
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
1  
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
1  
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.