Information theory

Fall 2019 at ENS Lyon

General information

This course is an introduction to information theory and error correcting codes from the computer science point of view.

Resources

For some online resources on probability (for computer science), you can look at these notes or these notes (starting at Lecture 10).

Grading

The grading scheme will take into account

Schedule

Date Topic References
Sep 10th Admin. Overview of the fundamental problem of noisy channel coding. Definition of entropy.
Ch 1 of [Mac], Ch 2 of [CT], Shannon's paper
Sep 17th Conditional entropy, mutual information, relative entropy. Data compression, variable-length lossless compressor.
Ch 8.1 of [PW], Ch 4 of [Mac], Ch 2,3,5 of [CT]
Sep 24th Continuing variable-length coding. Prefix codes, Kraft's inequality, H(X) < L(C) < H(X)+1.
Fixed-length compression, general bound in the size of the smallest set with prob >= 1-delta.
Ch 8.2 of [PW], Ch 5,6 of [Mac], Ch 5 of [CT], Ch 9.1 of [PW]
Oct 8th Shannon's source coding theorem
Universal compression: arithmetic coding. See here for more details on compression
Ch 16.1 of [PW], Ch 6 of [Mac]
Oct 9th Channel coding: Information capacity of a channel.
Additivity of information capacity for independent channels. Converse bounds
Ch 16.3 [PW], Ch 7 of [CT].
Oct 16th Achievability bounds. Shannon noisy coding theorem.
Ch 16.4 [PW], Ch 7 of [CT]
Oct 22nd Zero-error channel coding. Lovasz theta function. Information theory and combinatorics.
Entropy and counting

Homeworks