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
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 coding | 5.9, 5.10, and maybe 5.11 | |
| F Feb 22 | Bo | Markov chains and entropy | 4.1-4.3 | |
| M Feb 25 | Danny | 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 | 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 5 | Alex | 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 |