# Information Theory 2017

University of Amsterdam course, Nov/Dec 2017
Master of Logic
Lecturer: Christian Schaffner (UvA / email)
Teaching assistants: Yfke Dulek (email)
Alvaro Piedrafita (email)

#### News:

6 Feb 2017: first update of page
See here for the Spring 2014 and Fall 2014, Fall 2015, Fall 2016 editions of this course.

• Create an account on this Moodle site, or log in if you already have an account.
• enrol yourself in the Information Theory course.
• Leave a welcome message in the course forum
• Attend the first lecture on Tuesday, 30 October 2017, 9:00 at Science Park C0.05 and subsequent exercise session. Please bring along your laptop or smartphone with access to the Moodle site.

## Content of the course

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.

## Requirements

Students are required to know the (theory) contents of the course Basic Probability: Theory in the Master of Logic (no programming will be required for this course). Study the script and the theory homework exercises.

## Intended Learning Outcomes

At the end of the course, you will be able to solve problems of the following kinds:

(Probability)

• 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.

(Entropy and related concepts)

• 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.

(Data compression)

• 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.

(Noisy-channel coding)

• 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;

• draw the confusability graph of a given channel, and describe the channel depicted by a given confusability graph;

• compute the independence number and the zero-error capacity of a confusability graph;

## Course website

Updated information about the course can be found on http://homepages.cwi.nl/~schaffne/courses/inftheory/2016/

## Study Material

The material will be presented in black-boards lectures. The following are good references:

## Lectures and Exercise sessions

please check Datanose for the definite times and locations.