Posted by: atri | February 27, 2009

## Homework is out!

I’ll hand out copies in class today but you can also find a copy on the webpage. The writeup contains all the relevant instructions. The homework is due March 23 in class. Please use the comments section if you have any questions on the homework. (I’ll make this post sticky so it is easy to access.)

UPDATE (March 1): The hint for 4(b) was not quite right. I have fixed it in the current version of the homework on the course webpage (follow the link above).

## Responses

1. I have some questions for the homework. For the benefit of others I will write them here.

Q1:
****removed by Atri****

Also: What does it mean to have a non-linear code? Say we have a q-ary (n,k,d) code, and k need not be an integer. So k can be e.g. 2½. What does this code look like?

Q3:
Once again I think the understanding of non-linear code will help me. That being said, here’s my question:
That thing to be proved is the lower bound for the distance. The H^-1 function, is that the function we called Hq in class? Or is it 1/Hq? (q being 2 here, I suppose)

—–

Thank you. There is more to come, I am sure.

2. Hmm, my first post go messed up. I guess I used some wrong characters or something. So here’s my second try, please disregard the first one:

—————-

I have some questions for the homework. For the benefit of others I will write them here.

Q1:
***removed by Atri****

Q2:
I assume that the tricks lies in using a proof that states that a q-ary (n,k) code has the distance d leads to it is a q-ary (n,k,d) code. I can’t find that we have a proof for this anywhere. I can only find a proof that states that a code with a given distance leads to the fact that a minimum number of errors can be corrected. Where did we have a proof for the distance of a code?

Also: What does it mean to have a non-linear code? Say we have a q-ary (n,k,d) code, and k need not be an integer. So k can be e.g. 2½. What does this code look like?

Q3:
Once again I think the understanding of non-linear code will help me. That being said, here’s my question:
That thing to be proved is the lower bound for the distance. The H^-1 function, is that the function we called Hq in class? Or is it 1/Hq? (q being 2 here, I suppose)

—–

Thank you. There is more to come, I am sure.

3. JD,

Q1) I removed your comment as I think it gives away the real essence of the problem. However, as “hint” to you and others, let me mention a fact that I should have done earlier in the class. For any linear code of dimension $k$ and block length $n$, its $k\times n$ generator matrix has rank $k$. (Convince yourself that this follows from the fact that the code has dimension $k$.)

Q2) I’m not sure I get your question but I think your confusion is with the notation. The notation $(n,k,d)_q$ denotes a $q$-ary code with dimension $k$, block length $n$ and distance $d$.

Regarding your second point, in Q2 you cannot assume anything about the code other than what is given (i.e. block length, dimension, distance, alphabet size and whether the code is linear or not). Hence, what you have been asked to prove are “general purpose” conversion methods.

If your question regarding non-linear code is you want an example of how such a code might look like, here is an example of a $(4,1/2)_4$ code (I used $1/2$ instead of your $5/2$ to make the example easier). Consider the code over $\mathbb{Z}_4$ which has the codewords $(0,0,0,1)$ and $(1,1,1,1)$. Note that this code has the claimed parameters but it is not a linear code, e.g., as the vector $(0,0,0,1)+(1,1,1,1)=(1,1,1,2)$ is not in the code.

However, I repeat again: in Q2 you cannot use any specific property of the codes other than the parameters of the code that are given.

Q3) Sorry for using the $H^{-1}(\cdot)$ notation without defining it. I have added a definition in the homework: see the updated version on the course webpage. (And yes, I did mean $q=2$.)

4. A few more questions:

Q5b:
What does this mean delta = delta(gamma, p)? I think the proof is very similar to Shannon’s Capacity Theorem proof, but do I replace (p + gamma) with delta?

Q6a:
How many matrices G do we have? What are the properties of these matrices? And what do they do/how are they used?
Why do we have more than one matrix? I thought a code was generated by using a single matrix.

Q6b:
In the original proof of Shannon’s Capacity Theorem we find the expectation of the probability that y is received when E(x) was sent. We do this by splitting the vector space up into those y’s that lie within the hamming ball centered around E(x) with distance (p+gamma)n and those y’s that lie outside of this ball. Now we have an erasure channel with a linear code, so how do we split up the vector space in this case?

Q7:
First, alpha is a single element from Fq, right?
What does the alpha^i mean? I suppose it would be a function applied something like a^2 = a¤a, but what kind of function is “¤” then?

I just have a hard time using the first hint, since my trials with small q’s and n’s does not sum to zero (I’m trying addition and multiplication as functions). So there is obviously something I’m missing.

Thank you.

5. JD,

Below are my responses to your questions. Please let me know if the explanations do not make sense.

Q5b) $\delta=\delta(\gamma, p)$ means that $\delta$ is a number that depends only on $\gamma$ and $p$. In particular, if $\gamma$ and $p$ are constants, then so is $\delta$.

Also I don’t think the proof of 5b is similar to that of Shannon’s capacity theorem (at least not for the proof idea I have in mind).

Q6a) This part of the question has nothing to do with codes per se. As the question says $G$ is a $k\times n$ matrix over $\mathbb{F}_q$ and that is all you have to “play” with. Also the sentence in the parenthesis was stated in a slight confusing manner: I have fixed it in the writeup now. Maybe the new statement in the parenthesis will make the question clearer.

Even though this part of Q6 has nothing to do with codes per se, you will use the statement in part (a) to prove the claimed statement in part (b).

Q6b) The proof here is somewhat different from the proof that we saw in the class. In particular, in part (b) of this question note that you are asked to show the probability of a decoding error conditioned on the erasures taking place in the locations indexed by $J$.

The reason problem 6 is divided into four parts is partly because the proof for the erasure channel is a bit different from that for the $BSC_p$ that we did in the class. The four parts in some sense are the four main steps in the proof and in this problem you are supposed to prove each of these steps in sequence.

Q7) Yes, $\alpha$ is an element in $\mathbb{F}_q$ (but is not the zero element). Also $\alpha^i$ is $\alpha$ “multiplied” with itself $i$ times. The multiplication here is not just “normal” multiplication (say on reals or integers). We defined how multiplication is defined for finite fields in lecture 5 earlier in the semester. Unfortunately, the final polished notes are not up yet.

In short when $q=p$ is a prime, then the elements in the field are $\{0,1,\dots,p-1\}$ and the “addition” and “multiplication” are the “usual” addition and multiplication but modulo $p$. When $q=p^s$ is a prime power, then the elements of $\mathbb{F}_q$ are polynomials of degree $s-1$ over $\mathbb{F}_p$ and the addition and multiplication are polynomial addition and multiplication modulo an irreducible polynomial of degree $s$.

If you are not that comfortable with general finite fields, to get some intuition going I encourage you to think about the case when $q$ is a prime number.