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.

Advertisements

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 | Reply

    • 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 | Reply

  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 | Reply

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

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


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: