This is a graduate-level introduction to the fundamental ideas and results of information and source coding. The course moves quickly but does not assume prior study in information theory. It is intended for graduate students from mathematics, engineering or related areas wanting a good background in fundamental and applicable information theory. It also provides solid preparation for advanced courses in information theory.

Roughly the first third of the course discusses elementary measures and properties of information at a more sophisticated level. The middle third discusses typical sets and the main results of Shannon’s theory, manly the coding theorems for source coding. The remainder touches on topics that are explored more fully in later courses.

Course announcement

I shall be able to answer questions on your homework assignments every Wednesday in my office A4.19 between 5 p.m. to 6 p.m., but you can also ask questions via e-mail to pablo.piantanida@centralesupelec.fr

Summary of lectures

1. 1.Properties of Shannon's Information Measures: Introduction and Main Definitions, Entropy, Relative Entropy and Mutual Information, Venn Diagrams, Jensen's Inequality and Properties of Relative Entropy, Differential and Absolute Entropy, Entropy of Binary and Gaussian RVs.
   

2. 2.Markov Chain, Fundamental Inequalities and Entropy of Stationary Sources: Convexity Properties of Information Measures, Entropy Maximization, Fano's Inequalities, Markov Chains and Data Processing Inequality, Chain Rules for Entropy, Relative Entropy and Mutual Information, The Log-Sum Inequality and Entropy Power Inequality.
   

3. 3.Lossless Source Coding: Weak Typical Sequences, Noiseless Source Coding and its Coding Theorem, Entropy Rate of Stationary Sources, Proof of the Coding Theorem.
   

4. 4.Strong Typical Sequences: Definitions, Strong Typical Sets, Delta Sequences, Bounds on the Size of Strong Typical Sets.
   

5. 5.Coding Theorem for Noisy Channels: Coding Theorem, Capacity of Binary Symmetric Channels, Gaussian Channels (AWGN), Proof of the Coding Theorem and its weak converse.
   

6. 6.Coding Theorem for Lossy Source Coding: Quantization and Distortion, Coding Theorem, Rate Distortion Function of Binary and Gaussian Sources, Proof of the Coding Theorem and its weak converse.
   

7. 7.Lossy Compression with Side Information: Causal Side Information Available at the Decoder, Noncausal Side Information Available at the Decoder, Source Coding When Side Information May Be Absent. 
   

8. 8.Distributed Lossless Compression: Distributed Lossless Source Coding for Two Sources, Inner and Outer Bounds on the Optimal Rate Region, Slepian-Wolf Theorem, Extension to More than Two Sources.
   

Textbooks

1. (COV) Elements of Information Theory by Cover, Thomas M. and Joy A Thomas, New York, Wiley, 1991.
   

2. (SAY) Introduction to Data Compression by Khalid Sayood, Morgan Kaufmann, 4 edition, 2012.
   

3. (CSIS) Information Theory: Coding Theorems for Discrete Memoryless Systems by Imre Csiszar and Janos Korner, Academic Press, 1997.
   

4. (ASH) Information Theory by Robert B. Ash, Interscience Publishers, 1966.
   

5. (TSU) Information-Spectrum Methods in Information Theory by Te Sun Han, Springer Verlag.
   

Optional references:

1. Robert Gallager. Information Theory and Reliable Communication. New York: John Wiley and Sons, 1968.
   

2. Raymond W. Yeung. A First Course in Information Theory, Kluwer Academic/Plenum Publishers, 2002.
   

3. David J. C. MacKay. Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003.
   

4. C. E. Shannon, ‘‘A mathematical theory of communication,’’ Bell Syst. Tech. J., vol. 27, pp. 623-656, Oct. 1948 (.pdf).
   

5. C. E. Shannon, ‘‘Coding theorems for a discrete source with a fidelity criterion,’’ IRE Nat. Conv. Rec., part 4, pp. 142-163, 1959.
   

Lecture notes

Lecture notes will be distributed during the course and available via e-mail to pablo.piantanida@centralesupelec.fr

Advice to students

I hope you will enjoy the variety and beauty of the theory discussed in this course. The course provides a fairly thorough study of basic information theory techniques at the graduate level, plus an introduction to some additional topics.

Background. The course is an introduction, but at the graduate level. It assumes mathematical maturity, which means familiarity with elementary undergraduate mathematics and a level of comfort with reading and writing proofs. There is no specific prerequisite in information theory; we will develop all the theory from the beginning. However, the course moves quickly and covers a lot. What matters more than specific background is interest in the material and a commitment to work hard.

Website. Along with the course the web site will have the homework posted week by week, plus any other handouts. There is also a list of books that I asked to be placed on reserve. There will be reading assignments from these books. Also maintained on the web will be a summary of the lecture topics and a list of typos discovered in the text. Please let me know of any typos you find, except that in the index tell me only about terms that need to be added.

Feedback. Please feel free to offer feedback by email or in office hour about the lectures, text, topics, homework, etc. Also feel free to ask questions in class.

Homework. Start early on homework assignments, and ask questions if anything is unclear or if you need guidance. The purpose of the homework is to help students understand the ideas, so it is okay to toss around some thoughts with others. Be sure to write up solutions on your own. Solutions should include full justifications in sentences. The texts and class cover classical examples, and working other problems for homework leads to deeper understanding. I listen and answer questions about the homework in small groups of students. Usually more than half of the students attend these sessions; others prefer to work on their own or at other times. Whether you attend or not, you should still try to solve the problems before the next lecture.

Homework solutions. From past experience, I know that some of you will need to improve your written exposition. An important part of doing mathematics is communicating it clearly. I suggest trying the following technique. Instead of solving all the problems first and then writing them up, write up problems right away when you solve them. You will then have a chance to forget what you wrote for the first few problems while you work on the others. At the end, before fishing the homework, read over what you wrote earlier. If you find it hard to follow, be aware that graders will find it even harder! At this point revise your exposition so that it really communicates what you had in mind. When you think of a proof and write it down, it seems clear to you because the ideas are fresh in your mind. Revising after you have a chance to forget the thoughts is very important, and it is the only way you can be confident that what you have written expresses what you meant. Another benefit is that this process will help you discover habits of expression that make your exposition unclear, and then your early drafts of future work will be better.

The lectures aim to increase your interest in these topics and to convey a basic understanding of the techniques and proofs and how they fit together. Sometimes you may not fully understand all details just by attending lecture; that why the details are in the text. With your lecture notes as a guide, review the text to understand the details securely (also ask questions if something is not adequately explained!) Mastery of the material comes from reflecting on it at your own pace and from solving problems, which is why the homework is so important.

I hope you all have a great time and learn a lot!

Pablo Piantanida