Back to Teaching

ECE 562: Fundamental Information Theory

Syllabus (tentative, minor changes likely during the semester)

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/24 Course presentation Yeung: Ch. 1, 2.1, 2.2, 2.3; Cover/Thomas: Ch. 1, 2, 4. none yet.
1/26 Information measures: independence, Markov chains, continuity.
Scribe notes: rt67, jma65, aa332, sk482.		 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.
1/31 Information measures: chain rules, relative entropy, basic inequalities.
Scribe notes: jz87, zz37, oek2.		 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/02 Information measures: more inequalities, entropy rates.
Scribe notes: rt67, jma65, fmc3.		 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/07 Weak typicality: the weak AEP, source coding, generalization to ergodic stationary sources.
Scribe notes: jz87, sab222, ak387, sk374.		 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/09 Strong typicality: tail inequalities, random binning.
Scribe notes: hy98, wc267, ss556, hm95.		 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/14 Strong typicality: the strong AEP, and how it is stronger than the weak AEP.
Scribe notes: hy98, wc267, ss555, ss556.		 Yeung: Ch. 5.3, 5.4; Cover/Thomas: Ch. 13.6. Yeung: Probs. 5.1, 5.4, 5.5.
2/16 Strong typicality: joint typicality, Berger's Markov lemma.
Scribe notes: ssj8, wjk9, jjc55, cl426.		 Cover/Thomas: Ch. 2, 3, 4; Yeung: Ch. 2, 4, 5; Motwani/Raghavan: Ch. 3.1, 3.2, 3.6, 4.1. none.
2/21 Review/buffer lecture.
Scribe notes: sab222, ak387, sk374, ilw4.		 Cover/Thomas: Ch. 2, 3, 4; Yeung: Ch. 2, 4, 5; Motwani/Raghavan: Ch. 3.1, 3.2, 3.6, 4.1. none.
2/23 Review/buffer lecture.
Scribe notes: dmr58, ssj8, wjk9, cl426.		 TBA none.

First homework due on Tuesday February 28th, in class (all problems listed above -- worth 370 points).

Take-home midterm exam handed out on Thursday March 2nd, in class. Exam due back on Saturday March 4th, at noon, in the instructor's office. Covers only Part I.

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
2/28 Codes, Kraft's inequality.
Scribe notes: tc228, jjc55, mds72, mey7, dkl32.		 Yeung: Ch. 3; Cover/Thomas: Ch. 5.3-4. none yet.
3/02 Performance of codes, Huffman codes.
Scribe notes: sk482, tc228, mds72, ac438, dkl32.		 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/07 Generation of discrete distributions from fair coins.
Scribe notes: ???, ???, ???.		 Cover/Thomas: Ch. 14.4. Review Motwani/Raghavan. No new problems.
3/09 Data compression based on random binning.
Scribe notes: mkl28, jcw48, so69, hm95.		 Cover/Thomas: Ch. 14.4. No new problems.
3/28 The Slepian-Wolf Theorem -- Achievability Proof.
Scribe notes: skp27, mey7, so69, an222.		 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).
3/30 The Slepian-Wolf Theorem -- Converse Proof.
Scribe notes: ???, ???, ???.		 Yeung: Ch. 8; Cover/Thomas: Ch. 8. No new problems.

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

No lecture on 3/14-16 (to attend ITW).
The week 3/20-24 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/04 Problem Overview, Definitions, Examples. Statement of the Channel Capacity Theorem.
Scribe notes: ???, ???, ???.		 Yeung: Ch. 8.4-5; Cover/Thomas: Ch. 8.7-8. Yeung: Probs. 8.3,7-10; Cover/Thomas: Prob. 8.7.
4/06 The Channel Capacity Theorem -- Achievability Proof.
Scribe notes: ???, ???, ???.		 Cover/Thomas: Ch. 8.9-10. Cover/Thomas: Prob. 8.11.
4/11 The Channel Capacity Theorem -- Converse Proof.
Scribe notes: an222, sg355, ???.		 Yeung: Ch. 8.6; Cover/Thomas: Ch. 8.12. Cover/Thomas: Probs. 14.1-2,6 (this is not a mistake -- start now).
4/13 Channel Capacity with Feedback.
Scribe notes: dmr58, skp27, fmc3, sg355.		 Yeung: Ch. 8.7; Cover/Thomas: Ch. 8.13. Yeung: Prob. 8.4.
4/18 The Joint Source/Channel Coding Theorem.
Scribe notes: ???, ???, ???.		 Cover/Thomas: Ch. 14.3. No new problems.
4/20 The Multiple-Access Channel.
Scribe notes: sh366, ss555, ac348.		 Yeung: Ch. 9, Cover/Thomas: Ch. 13. No new problems.

Third homework due on Tuesday April 25th, 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/25 Problem Overview, Definitions, Examples. Statement of the Rate/Distortion Theorem.
Scribe notes: sh366, bl64, ???.		 Cover/Thomas: Ch. 13.4. Yeung: Prob. 9.2; Cover/Thomas: Probs. 13.4-5,9.
4/27 The Rate/Distortion Theorem -- Converse Proof.
Scribe notes: bl64, ???, ???.		 Yeung: Ch. 9.5. Cover/Thomas: Prob. 13.10 (each of 10.a-10.f worth 10 points).
5/02 The Rate/Distortion Theorem -- Achievability Proof.
Scribe notes: ???, ???, ???.		 Nothing. No new problems.

Fourth (and final) homework due on Thursday May 4th, 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/04 Research Topics in Information Theory. Nothing. None.

Take-home final exam handed out on Thursday May 4th, in class. Exam due back on Saturday, May 6th, at noon, in the instructor's office. The exam is comprehensive.

About the course

Course staff:

Instructor: Sergio Servetto
No TAs.

Meeting times and place, and office hours:

Class: TuTh 2:55-4:10pm, 403 Phillips.
Office hours: Thursdays after class, and by appointment.

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:

9% -- Self-graded homework.
1% -- Course evaluation.
10% -- Scribe assignments.
30% -- Take-home midterm exam.
50% -- Take-home final exam.

Scribe Instructions:

Jeff Erickson's style file for producing scribe notes.
A sample file using Jeff's style file.
Scribe assignments are due one week after the lecture.

Please note: use Latex only to typeset text. For including figures, just leave a blank space in the file, draw the figures by hand, and scan them. And if you do not have a scanner, just give us a printout and we will take care of scanning them. This will take you far less time to do than using a package like xfig or similar to generate graphics.

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

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