INF563 — Introduction to Information Theory
Coordinator : JeanPierre Tillich (jeanpierre.tillich@inria.fr)
Objectives :
Information theory deals with finding the fundamental limits for compressing a signal, storing data or communicating information reliably over a noisy channel for instance. It turns out that all these limits can be expressed in terms of a single quantity which is entropy. The foundations of this domain were laid by Shannon who quantified in a very elegant way these limits.
We will cover during this course his major results and will also give the modern answers to this kind of issue that give very effective schemes for compressing or protecting data against noise. Now this theory has also found applications in many other areas such as cryptography, biology, quantum computing, linguistics, plagiarism detection or pattern recognition. We will cover some of those other applications during the course.
Content :
The course is divided into nine lectures and nine exercise or lab sessions. These cover the main algorithmical and mathematical concepts involved in information theory. The topics covered include:
 Entropy, typical sequences
 Memoryless source coding
 Memoryless source coding, Huffman code, ShannonFanoElias code, Shannon code and arithmetic coding
 adaptative Huffman coding, universal coding of a source
 Stationnary source, typical sequences, AEP
 Channel coding, capacity, Shannon theorem
 Linear codes, Hamming and ReedSolomon codes, decoding, concatenated codes
 Polar codes

Applications of Information Theory to other domains.
Suggested readings:
T. Cover, J. Thomas, "Elements of Information Theory". Wiley Series in Telecommunications, 1991.
Language :
The course material is in English. Lectures can be taught either in French or in English, at the students' convenience.
Evaluation :
The course is validated by an oral examination.
Prerequisites :

Some basic background in statistics or probability theory is desirable but not mandatory.

in computer science: some knowledge of algorithms and programming such as INF411 or INF421.