test
- Lecturer: Samuel Cohen
Category: Michaelmas
General prerequisites:
Part A Probability would be very helpful, but not essential.
Course term: Michaelmas
Course lecture information: 16 lectures
Course weight: 1
Course level: H
Assessment type: Written Examination
Course overview:
Information theory is a relatively young subject. It played an important role in the rise of the current information/digital/computer age and still motivates much research in diverse fields such as statistics and machine learning, physics, computer science and engineering. Every time you make a phone call, store a file on your computer, query an internet search engine, watch a DVD, stream a movie, listen to a CD or mp3 file, etc., algorithms run that are based on topics we discuss in this course. However, independent of such applications, the underlying mathematical objects arise naturally as soon as one starts to think about "information" in a mathematically rigorous way. In fact, a large part of the course deals with two fundamental questions:
How much information is contained in a signal/data/message, and how do we compress it? (source coding)
What are the limits to information transfer over a channel that is subject to noisy perturbations, and how to encode and decode in this setting? (channel coding)
How much information is contained in a signal/data/message, and how do we compress it? (source coding)
What are the limits to information transfer over a channel that is subject to noisy perturbations, and how to encode and decode in this setting? (channel coding)
Learning outcomes:
The student will have learned about entropy, mutual information and divergence, their basic properties, how they relate to information transmission. Knowledge of fundamentals of block/symbol/channel coding. Understand the theoretical limits of transmitting information due to noise. They will have experience applying these methods to data.
Course synopsis:
(Conditional) entropy, mutual information, divergence and their basic properties and inequalities (Fano, Gibbs').
(Strong and weak) typical sequences: the asymptotic equipartition property, and applications to block coding.
Symbol codes: Kraft--McMillan, optimality, various symbol codes (Huffman, Elias, Arithmetic codes) and their construction and complexity.
Channel coding: discrete memoryless channels, channel codes/rates/errors, Shannon's noisy channel coding theorem, block linear codes. Methods for decoding noisy signals.
(Strong and weak) typical sequences: the asymptotic equipartition property, and applications to block coding.
Symbol codes: Kraft--McMillan, optimality, various symbol codes (Huffman, Elias, Arithmetic codes) and their construction and complexity.
Channel coding: discrete memoryless channels, channel codes/rates/errors, Shannon's noisy channel coding theorem, block linear codes. Methods for decoding noisy signals.