# Introduction to coding theory (CMU, Spr 2010)

## January 24, 2010

### Problem set 1

Filed under: Problem sets — Venkat Guruswami @ 7:27 pm

Problem set 1 is now posted here. It is due on Feb 17, so you have just over 3 weeks to work on it (but I encourage you to start early!). Please use the comments section of this post to ask any questions, point out inaccuracies if you find any, etc.

## 4 Comments »

1. Problem (4b). In class, we established that $Vol(n,\tau n)$ is at least $2^{h(\tau) n – o(n)}$. From this, I do get an asymptotic $1 – h(\tau) + o(1)$ rate bound for $\tau$-covering codes. But, it seems too weak to get the tighter bound mentioned in the first part of the question: $n^3 2^{n-h(\tau) n}$. This, we would get only if $o(n)$ is in fact only logarithmically small.

Are we supposed to derive/know such a tight estimate of the volume? (Or, am I missing something here?)

Comment by Srivatsan — February 9, 2010 @ 11:06 pm

• You are right — we actually proved a lower bound of $2^{h(\tau) n}/O(n)$ for the volume of the ball ${\rm Vol}(n,\tau n)$ (see Notes 2). Using this I think you should be able to get the tighter bound stated in the first part of the question. If you want, you can also use the stronger Stirling’s formula which gives the better lower bound $2^{h(\tau) n}/O(\sqrt{n})$.

Comment by Venkat Guruswami — February 12, 2010 @ 10:37 am

2. Two minor clarifications:

In problem 3, $C_2$ is also a binary linear code.

In problem 5(a), $\mathcal{F}$ is a collection of binary linear codes.

Comment by Venkat Guruswami — February 12, 2010 @ 10:43 am

3. Can you please post the solutions to the problem set? Thank you.

Comment by Ankit Sharma — February 24, 2010 @ 5:50 pm

Blog at WordPress.com.