Sergio Servetto

ECE 562: Fundamental Information Theory

Announcements

4/03, 9pm: Updated course syllabus (all included till end of semester). There is a good chance now that we will indeed need a makeup lecture, for the one we lost on March 16th due to my early departure for Princeton because of the snow storm. We will discuss this in class, and I will update this later.

Older announcements:

3/30, 1:20pm: Added missing problems and updated syllabus for Part II.
3/04, 1:50pm: Updated course syllabus (Part II included now).
2/27, 1:20pm: Review session is today, 2-5pm, in 280 Rhodes.
1/29, 2:15am: added relevant sections from Cover/Thomas to the syllabus.
1/27: First lecture.

Syllabus

Part I: Information Measures -- the Toolbox

Topics to cover: entropy, relative entropy, mutual information, their properties, weak and strong typicality, elementary tail inequalities, and random binning. The goal is to develop a solid understanding of these basic tools, before proceeding to tackle the basic questions of information theory.

Date	Lectures on	Read for next time	Problems to start working on
1/27	Course presentation	Yeung: Ch. 1, 2.1, 2.2, 2.3; Cover/Thomas: Ch. 1, 2, 4.	none yet
1/29	Information measures: independence, Markov chains, continuity.	Yeung: Ch. 2.4, 2.5, 2.6; Cover/Thomas: Ch. 2.	Yeung: Probs. 2.1, 2.2, 2.3, 2.7, 2.8, 2.9, 2.11.
2/03	Information measures: chain rules, relative entropy, basic inequalities.	Yeung: Ch. 2.7, 2.8, 2.9; Cover/Thomas: Ch. 2, 4.	Yeung: Probs. 2.10, 2.15, 2.16, 2.17, 2.18.
2/05	Information measures: more inequalities, entropy rates.	Yeung: Ch. 4; Cover/Thomas: Ch. 3.	Yeung: problem 2.19; Cover/Thomas: Probs. 4.3, 4.5, 4.10, 4.11, 4.12, 4.13.
2/10	Weak typicality: the weak AEP, source coding, generalization to ergodic stationary sources.	Motwani/Raghavan: Ch. 3.1, 3.2, (3.6 quick look), 4.1.	Yeung: Probs. 4.1, 4.5, 4.6; Cover/Thomas: Probs. 3.1, 3.2, 3.3, 3.4, 3.5, 3.6.
2/12	Strong typicality: tail inequalities, random binning.	Yeung: Ch. 5.1, 5.2; Cover/Thomas: Ch. 13.6.	Motwani/Raghavan: Probs. 3.1, 3.2, 3.5, 4.1, 4.4, 4.22.
2/17	Strong typicality: the strong AEP, and how it is stronger than the weak AEP.	Yeung: Ch. 5.3, 5.4; Cover/Thomas: Ch. 13.6.	Yeung: Probs. 5.1, 5.4, 5.5.
2/19	Strong typicality: joint typicality, Berger's Markov lemma.	Cover/Thomas: Ch. 2, 3, 4; Yeung: Ch. 2, 4, 5; Motwani/Raghavan: Ch. 3.1, 3.2, 3.6, 4.1.	none.
2/24	Review lecture.	Cover/Thomas: Ch. 2, 3, 4; Yeung: Ch. 2, 4, 5; Motwani/Raghavan: Ch. 3.1, 3.2, 3.6, 4.1.	none.
2/26	Review lecture.	TBA	none.

First homework due on Friday February 27th (all problems listed above -- worth 370 points).

Part II: Zero-Error Data Compression

Topics to cover: Yeung, Chapter 3; Cover/Thomas, Chapters 5, 14.4.

Date	Lectures on	Read for next time	Problems to start working on
3/02	Codes, Kraft's inequality.	Yeung: Ch. 3; Cover/Thomas: Ch. 5.3-4.	none yet
3/04	Performance of codes, Huffman codes.	Cover/Thomas: Ch. 5.12.	Cover/Thomas: Probs. 5.1, 5.3-7, 5.9, 5.11, 5.13-17, 5.21-24, 5.26.
3/09	Generation of discrete distributions from fair coins.	Cover/Thomas: Ch. 14.4. Review Motwani/Raghavan.	No new problems.
3/11	Data compression based on random binning.	Cover/Thomas: Ch. 14.4.	No new problems.
3/30	The Slepian-Wolf Theorem -- Achievability Proof.	Cover/Thomas: Ch. 14.4.	Cover/Thomas: Probs. 14.8, 14.9. Prove R1+R2>H(XY) ==> P(E_12) < epsilon (hint: look at equations 14.165-14.169, pp. 412-413).
4/01	The Slepian-Wolf Theorem -- Converse Proof.	Yeung: Ch. 8; Cover/Thomas: Ch. 8.	No new problems.

Second homework due on Tuesday April 6th, in class (all problems listed above -- worth 210 points).

No lecture on 3/16-18 (to attend CISS).
Week #9 (3/20-28) is our Spring Break.

Part III: Channel Capacity

Yeung, Chapter 8; Cover/Thomas, Chapters 8, 14.3.

Date	Lectures on	Read for next time	Problems to start working on
4/06	Problem Overview, Definitions, Examples. Statement of the Channel Capacity Theorem.	Yeung: Ch. 8.4-5; Cover/Thomas: Ch. 8.7-8.	Yeung: Probs. 8.3,7-10; Cover/Thomas: Prob. 8.7.
4/08	The Channel Capacity Theorem -- Achievability Proof.	Cover/Thomas: Ch. 8.9-10.	Cover/Thomas: Prob. 8.11.
4/13	The Channel Capacity Theorem -- Converse Proof.	Yeung: Ch. 8.6; Cover/Thomas: Ch. 8.12.	Cover/Thomas: Probs. 14.1-2,6 (this is not a mistake -- start now).
4/15	Channel Capacity with Feedback.	Yeung: Ch. 8.7; Cover/Thomas: Ch. 8.13.	Yeung: Prob. 8.4.
4/20	The Joint Source/Channel Coding Theorem.	Cover/Thomas: Ch. 14.3.	No new problems.
4/22	The Multiple-Access Channel.	Yeung: Ch. 9, Cover/Thomas: Ch. 13.	No new problems.

Third homework due on Tuesday April 27th, in class (all problems listed above -- worth 110 points).

Part IV: Rate/Distortion

Yeung, Chapter 9; Cover/Thomas, Ch. 13.1-4.

Date	Lectures on	Read for next time	Problems to start working on
4/27	Problem Overview, Definitions, Examples. Statement of the Rate/Distortion Theorem.	Cover/Thomas: Ch. 13.4.	Yeung: Prob. 9.2; Cover/Thomas: Probs. 13.4-5,9.
4/29	The Rate/Distortion Theorem -- Converse Proof.	Yeung: Ch. 9.5.	Cover/Thomas: Prob. 13.10 (each of 10.a-10.f worth 10 points).
5/04	The Rate/Distortion Theorem -- Achievability Proof.	Nothing.	No new problems.

Fourth (and final) homework due on Thursday May 6th, in class (all problems listed above -- worth 100 points).

Part V: Selected Topics

By now the course is over. But you should walk out of this course feeling you have barely scratched the surface on these topics... and for this purpose, we reserve one lecture to tell you about our own research work.

Date	Lectures on	Read for next time	Problems to start working on
5/06	Research Work by Instructor/TAs, and Overview of ECE 662.	Nothing.	None.

About the course

Course staff:

Instructor: Sergio Servetto

TAs: Ron Dabora, An-swol Hu, Megan Owen, Christina Peraki.

Grader: Mingbo Zhao.

Meeting times and place, and office hours:

Class: TuTh 2:55-4:10pm, 203 Phillips.

Office hours: MWF, 2 hours, exact time TBA.

Prerequisites:

ECE 411 (or some other basic class on random processes).

(Talk to the instructor if you are unsure on whether your probability background is enough.)

Grading:

100% homework.

Reading materials

This is a first course in information theory. The goal is to develop the basic theorems for zero-error data compression, channel capacity, and rate/distortion, for general discrete ergodic sources and channels. Main textbooks:

R. W. Yeung. A First Course in Information Theory. Kluwer, 2002.
T. M. Cover, J. A. Thomas. Elements of Information Theory. Wiley, 1991.

Both of these textbooks cover all the material we will see in this class, so you can get either one. They are different in style though, and depending on your taste, you might like more one or the other. In any case, I will always point to appropriate sections in both texts.

Some other strongly recommended reference texts, out of which we will cover some amount of material at one point or another in the course:

I. Csiszar, J. Koerner. Information Theory: Coding Theorems For Discrete Memoryless Systems. Academic Press, 1981.
R. Graham, D. Knuth, O. Patashnik. Concrete Mathematics: A Foundation for Computer Science (2nd. ed). Addison-Wesley, 1994.
R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Other books, with a different emphasis from that of this course, but still extremely useful and also required reading for anyone in the field:

Prof. Berger's 1978 lecture notes on Multiterminal Source Coding.
T. Berger. Rate Distortion Theory: A Mathematical Basis for Data Compression. Prentice Hall, 1971.
R. G. Gallager. Information Theory and Reliable Communication. Wiley, 1968.
J. M. Wozencraft, I. M. Jacobs. Principles of Communication Engineering. Wiley, 1965.