• Lecturer: Prof. Dr. Walter
• Language: English
• Credits: 5 CP
• Programs: B.Sc/M.Sc. IT-Security, M.Sc. Computer Science, M.Sc. Applied Computer Science
• Examination: 100 % Written Exam (120 Minutes) + 10 % Homework

Prior Knowledge

Familiarity with discrete probability (we will briefly remind you of the most important facts). Some experience with precise mathematical statements and rigorous proofs (since we will see many of these in the course). Some of the homework will require programming in Python.

Learning Outcomes

You will learn basic concepts, algorithms and results of information theory. Upon successful completion of this course, you will know the mathematical model of information theory, know how to design and analyze algorithms for a variety of information processing tasks, and how to implement them in Python. You have independently familiarized yourself with a topic in information theory and presented it to your fellow students. You will be prepared for a more advanced course or research or final project in this field. You can find a detailed list of the learning objectives on the course homepage.

Course Description

This course will give an introduction to information theory - the mathematical theory of information. Ever since its inception, informatino theory has had a profound impact on society. It underpins important technological developments, from reliable memories to mobile phone standards, and its versatile mathematical toolbox has found use in computer science, machine learning, physics, electrical engineering, mathematics, and many other disciplines. Starting from probability theory, we will discuss how to mathematically model information sources and communication channels, how to optimally compress information, and how to design error-correcting codes that allow us to reliably communicate over noisy communication channels. We will also see how techniques used in information theory can be applied more generally to make predictions from noisy data.

Topics to be covered:

• Welcome, Introduction to Informatino Theory
• Probability Theory Refresher
• Numerical Random Variables, Convexity and Concavity, Entropy
• Symbol Codes: Lossless Compression, Huffman Algorithm
• Block Codes: Shannon’s Source Coding Theorem, its Proof, and Variations
• Stream Codes: Lempel-Ziv Algorithm
• Stream Codes: Arithmetic Coding
• Joint Entropies & Communication over Noisy Channels
• Shannon’s Noisy Coding Theorem
• Proof of the Noisy Coding Theorem
• Proof of the Converse, Shannon’s Theory vs Practice
• Reed-Solomon Codes
• Message Passing for Decoding and Inference, Outlook
• Student Presentations