18.424 Seminar in Information Theory

This site can be accessed at http://www-math.mit.edu/~shor/18434.html and will be continuously updated.

When and where: The class meets on MWF from 1:00 to 2:00 in room 2-142.

Instructor: Peter Shor, room 2-369.

Paper Topics: Here are some suggestions for paper topics. I may be adding to this list in the next week or so (e.g., the week before spring break) if I think of any more.

Office hours: I will be available by appointment to help prepare the presentations if need be.
I will hold office hours Wednesday afternoon, from 2:00 to 3:30. I will also hold office hours the day before homework is due, from 2:30 to 3:30 unless otherwise posted.
NO OFFICE HOURS APRIL 2. Wednesday, April 3, 10:30-11:30 and 2:00-3:30.


Homework 1: 2.4, 2.6, 2.9, 2.10, 2.15 from Cover and Thomas
Due Friday, Feb. 15.

Homework 2: 2.29, 5.3, 5.12, 5.20, 5.30, 5.32 from Cover and Thomas
Due Wednesday, Feb. 27.

Homework 3: Problems 5.8, 5.19, 13.4, 13.8, from Cover and Thomas and this Burrows-Wheeler transform question.
Due Friday, Mar. 7.

Homework 4: Problems 11.4, 6.6, 7.8, 7.9, 7.24, 7.28 from Cover and Thomas. Also, please give a one-paragraph description of the subject for your final paper.
Due Wednesday, April 2.

This is an undergraduate seminar in information theory. It carries CIM credit for the math department. Enrollment is limited by the department.

The textbook is Elements of Information Theory, 2nd edition, by Cover and Thomas. The good news about this textbook is that the 2nd edition came out last year, and has numerous mistakes fixed, many more exercises, and additional material. It is available in the book store. The bad news is because it's new, you may not be able to get a 2nd hand copy of the 2nd edition cheaply, and the 1st edition is really quite different. We will also do some material in MacKay's book, which is available online as well as in hardcopy. MacKay's book is less dense than Cover and Thomas. It covers some material better than Cover and Thomas for some material, and covers some other materially nowhere near as well.

This is a seminar class, so you will actually be teaching it to yourselves. Everybody will have to give 2.5 to 3 periods worth of lectures, depending on how many people are in the class.

I think Information Theory is a fairly good topic for a seminar class, since (except for certain explicit constructions of error correcting codes) it is fairly broad. There is a small amount of material that underlies all of it. These are the concepts of information and entropy, and the properties of these quantities. There are many different possible branches of information theory that build on this, but which are relatively independent. Everybody is thus going to have to learn the underlying material fairly well. So I feel that I should probably start off by giving two lectures about properties of information. I will also give approximately five homework assignments during the term.

We will then start off by having students give lectures on various methods of source coding. After the source coding section, we'll do the channel coding theorem, possibly do some methods for channel coding, and we will also do certain other applications of information theory. These will include how information theory relates to probabilistic inference and gambling, and might also be rate-distortion theory, information capacity of networks, the information theory of continuous channels, or others. Exactly what we do will depend on the students' interests. I expect around half of the topics will be out of the textbook.

Students will be expected to present for approximately two to three class periods during the term, depending on the number of students. You will also be expected to write a 10-page paper on some topic related to information theory.

Dates You should come up with a topic for your term paper around March 31. The first draft of the paper will be due on April 25.

Grading policy. Your grade will be based on your participation (i.e. your own presentations, and also your participation during other presentations), the homework, and your project, in the ratio 40% participation, 30% homework, and 30% project. You are expected to attend all lectures (if not excused).

The prerequisites are having some courses on linear algebra and probability theory.

Here is a partial list of possible topics.


Date Presenter Topic Reference
W Feb 6 Peter Shor Introduction Beginning of chapter 2.
F Feb 8 Peter Shor Information inequalities Thomas and Cover Chapter 2.1-2.6, 2.8, 2.10.
M Feb 11 Peter Shor Asymptotic Equipartition Property Thomas and Cover 3.1,3.2, and 3.3 if it fits in the time.
W Feb 13 Alex Source coding, prefix codes and Kraft's inequality 5.1-5.3
F Feb 15 Eric Optimal codes, block coding, and McMillan's inequality. 5.4-5.5
T Feb 19 Alec Huffman codes (and maybe adaptive Huffman codes if time permits) 5.6 - 5.8
W Feb 20 Mavis More source coding5.9, 5.10, and maybe 5.11
F Feb 22 Bo Markov chains and entropy 4.1-4.3
M Feb 25Danny arithmetic codes 13.3 and Wikipedia. I believe the big difference here is that Wikipedia discusses an End-of-Data symbol, which is an important concept. 13.4
W Feb 27 Adam Lempel-Ziv (13.4.1 and 13.5.1) or (13.4.2 and 13.5.2)
F Feb 29 Xing Burrows-Wheeler transform Wikipedia, original paper and this paper
M Mar 3 Lacey audio compression Some discussion of psychoacoustics, Fourier transforms, and lossy compression. Wikipedia and How MP3 Works: Inside the Codec (although too detailed) are good references.
W Mar 5Alex Channel Capacities and Hamming Codes 7.1, 7.2, 7.11
F Mar 7 Peter Shor Channel Capacities Theorem I: Jointly typical sequences 7.4, 7.6, and the pieces of 7.5 needed for 7.6
M Mar 10 Bo Channel Capacities Theorem, II the rest of 7.5 and 7.7
W Mar 12 Alec Fano's Inequality and the Converse Channel Capacity theorem 2.10, 7.9 (and 7.10 if time permits)
F Mar 14 Cherrie Gambling and information theory 6.1-6.2
M Mar 17 Jimmy Gilbert Varshamov bound and Shannon's bound for linear codes MacKay Chap. 13.5 (and maybe some of 13.6 - 13.8) and 14.1
W Mar 19 Mavis method of types? 11.1-2
F Mar 21 Sarah Sanov's theorem? 11.4, 11.5
M Mar 31 Cherrie Hypothesis Testing 11.7, (and if time, explain theorem 11.8.3; there won't be time to go over the proof of it.)
W Apr 2 Lily BCH Codes 1
F Apr 4 Daniel BCH Codes 2
M Apr 7 Sarah Differential Entropy 8.1-8.5 (but skip the proof of the AEP; there's not time, and we've probably seen enough of them) and Thms. 8.6.1, 8.6.3-5.
W Apr 9 Lily Gaussian Channels 9.1-9.2
F Apr 11 Sebastian more on Gaussian channels channels 9.3-9.4,
M Apr 14 Adam Multiple-user channels 15.1-15.1.3; 15.2 (theorem 15.2.1); 15.3.0
W Apr 16 Lacey 15.4: Slepian-Wolf theorem. (feel free to skip some of the calculations in the proof, if you can get the idea across without going through them in detail. And you probably don't have time to do 15.4.2, so skip it completely. Maybe do 15.5, if there is time) 15.3.1-15.3.3
F Apr 18 Eric Price Shannon's paper on secrecy On-line here
W Apr 23 Alec Wyner "The Wire-Tap Channel"
F Apr 25 Peter Shor MacKay Chap. 48: convolution codes and turbo codes (web link needs updating)
M Apr 28 Peter Shor Rate-distortion theory?
W Apr 30 Sebastian The last piece on Gaussian channels 9.5-9.6
F May 2 Jimmy image compression?
M May 5 Xing, Sarah Low-density parity codes MacKay check codes/ first student project
W May 7 Alex, Lacey, Daniel Student Projects
F May 9 Cherrie, Bo, Adam Student Projects
M May 12 Mavis, Alec, Sebastian Student Projects
W May 14 Xing, Eric, Lily Student projects