Information Theory

Course manual 2022/2023

Course content

Information theory was developed by Claude E. Shannon in the 1950s to investigate the fundamental limits on signal-processing operations such as compressing data and on reliably storing and communicating data. These tasks have turned out to be fundamental for all of computer science.

In this course, we quickly review the basics of probability theory and introduce concepts such as (conditional) Shannon entropy, mutual information and entropy diagrams. Then, we prove Shannon's theorems about data compression and channel coding. An interesting connection with graph theory is made in the setting of zero-error information theory. We also cover some aspects of information-theoretic security such as perfectly secure encryption.

Study materials

Literature

• Good reference: [CF] Ronald Cramer, Serge Fehr: 'The Mathematical Theory of Information, and Applications': http://homepages.cwi.nl/%7Eschaffne/courses/inftheory/2016/notes/CramerFehr.pdf, lecture notes, Version 2.0
• Good reference: [CT] Thomas M. Cover, Joy A. Thomas. 'Elements of information theory': http://onlinelibrary.wiley.com/book/10.1002/0471200611, 2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4.
• Good reference: [MacKay] David J. C. MacKay. 'Information Theory, Inference, and Learning Algorithms': http://www.inference.phy.cam.ac.uk/mackay/itila/book.html. Cambridge University Press, 2003. ISBN 0-521-64298-1

Other

• The material will be presented in black-boards lectures.

Objectives

• compute the probability of an event using the most common discrete probability distributions (Bernoulli, binomial, and geometric)
• compute inverse probabilities using Bayes' rule
• compute the means and variances of commonly used probability distributions
• compute the means and variances of sums or products of a random variables with known distributions
• bound the probability of an extreme event using inequalities such as the Markov bound, Chebyshev's inequality, or Hoeffding's inequality
• compute the entropy of a random variable
• compute the mutual information between two random variables
• use entropy diagrams to reason about the relative size of the entropies, conditional entropies, and mutual information of two or three random variables
• use Jensen's inequality to bound the mean of a random variable defined in terms of convex or concave function of another random variable
• construct a d-ary Huffman code for a random variable
• use Kraft's inequality to check whether a prefix-free code can be constructed to fit certain codeword lengths
• bound the possible rate of lossless compression of output from a given source using Shannon's source coding theorem
• define a typical set and reason about its size, probability, and elements
• compute the Shannon-Fano-Elias codeword for a sample from a stochastic process
• compute the entropy rate of a Markov process
• construct a probability model of a communication channel given a verbal description 
• compute the channel capacity of a channel 
• use Shannon's channel-coding theorem to bound the achievable rate of reliable communication over a channel
• use Bayes' rule to decode corrupted messages sent using an error-correcting code 
• evaluate the rate and reliability of such codes 
• define the jointly typical sets of a source and channel, and use such sets to decode outputs from the channel
• present solutions of mathematical problems orally to peers

Teaching methods

• Lecture
• Seminar

This is a 6 ECTS course, which comes to roughly 20 hours of work per week.

There will be homework exercises every week to be handed in one week later before the start of the exercise session. The answers should be in English (feel free to use LaTeX, but readable handwritten solutions are fine). The homework exercises will be solved in groups of 3-4 students. 

Additionally, there will be short quizzes to be solved on canvas. You are encouraged to solve these quizzes individually to test your understanding of the course material before attempting the homework problems. 

Learning activities

Attendance

This programme does not have requirements concerning attendance (TER-B).

Assessment

The final grade will be determined by the following calculation:

60% exam grade + 30% homework grade + 10% quiz grade

The same rule applies for the re-sit exam.

There will be one homework problem set per week (in total 6), posted on the course homepage by Monday. You must submit your completed homework (on Canvas) before Monday the week after. We will ask you to collaborate and submit in groups of 3-4 students. The solutions will be discussed in the exercise classes (among other things). Assignments will be accepted late only if you have extenuating circumstances (such as sickness or family emergency) and provided you confirm with the lecturer before the deadline. Your problem set with the lowest score will be ignored (this includes any problem set you did not submit).

Everything that we discussed in class, on the homeworks, on in the canvas modules is in principle in scope for the exam. We recommend that you revisit the homework problems and the exercises as a preparation.

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Timetable

The schedule for this course is published on DataNose.

Additional information

Familiarity with probability theory will be useful, but is not explicitly required. No programming will be required for this course.

Contact information

Coordinator

• Nicolas Resch