Information Theory - 2023 Autumn Semester

Consider the fundamental data communication question: “How much information can be reliably transmitted over a noisy medium?”. Claude E. Shannon realized that this is the right question to ask, unlike other communication engineers who asked questions like “How many repetitions are necessary to reliably transmit information?”. He answered the question in a single paper in 1948. He applied many tricks to obtain the ultimate limit for wireless communications, but probably the most novel trick was to remove the “semantic meaning” of the information that should be transmitted. This actually means that it suffices to represent any information by the amount of uncertainty in it that is measured by the metric called “Entropy”. For instance, the messages “I want to eat an apple” and “I want to pass this course” might have the same entropy values independent of their semantic meanings, i.e., the amount of information in each sentence would then be the same. Due to this fundamental trick, Shannon was able to provide the ultimate limit for wireless communications and showed that 1) the limit is asmyptotically achievable by designing codes and 2) no algorithm can break it. With his groundbreaking results, he single-handedly established a new research area called “Information Theory”. Information and coding theoretic methods and analyses are now used in numerous research fields, including communications, data compression/storage, machine learning, provable security and privacy, quantum communications, etc.

This course is an introductory PhD course on Information Theory that targets a large group of students with varied background. This introductory course will provide students with a basic understanding of fundamental information theoretic metrics, proof techniques, analysis, and the Shannon theoretic way of thinking. We will discuss the following topics (after a brief recap of probability theory):

• Information Theory for Discrete Random Variables
• Information Theory for Continuous Random Variables
• Compressing Memoryless Sources
• Compressing Stationary Sequences
• Coding for Reliability

Updates:

0) To the exam, you can bring a cheatsheet of size half an A4 page (one side). Please bring ID as well. The exam starts at 08:30 am but you can enter the room until 09:00 am.

1) We will have to skip the presentations (so it is not necessary to present)

2) The lecture on January 9 will start at 9:00 and will continue until 12:30

3) The exam start time is 08:30 am (to allow an attendee to catch another lecture), but you can also come later at 9:00 am to start with the exam.

4) Homework 2 assignments were distributed. If you have not collected them, you can ask me directly. It seems that I asked 2 questions again, as in homework 1, which was not intentional, but I will keep the questions and they will count for the grading of homework 2.

5) The deadline for homework 1 submission is extended until mid-January.

6) The deadline for homework 2 is January 25.

Registration: Plese send an email with the subject “Information Theory Course” to onur.gunlu@liu.se if you want to register for this course. Note that this course is meant only for students who have not taken any information theory course before.

Prerequisites

Background in Probability Theory

Course Manager and Examiner

Onur Günlü

Suggested credits: 6 hp for the mandatory written exam + 3hp for the optional homework assignments

Course literature

The course will not follow a specific book but the participants can use the classic book Elements of Information Theory by Cover & Thomas as a reference for all topics covered in this course.

Teaching and Learning Activities

The course will include lectures that will be given by Onur Günlü. For most lectures the whiteboard will be used.

The lecture hall will be Systemet for all lectures and the exam

Examination

There will be a mandatory written exam and a presentation at the end of the course. Thus, to claim 6hp and to pass the course, a participant must

1) achieve at least 50 points (out of 100) in the written exam.

There will be also up to n=5 optional homework assignments during the course. To claim extra 3hp from the homework assignments, a participant must

2) achieve at least 60 points (out of 100) as an average over the highest (n-1) homework assignment grades.

In short, to claim any credits from this course, the participant has to satisfy 1) above, which is mandatory for this course and brings 6hp. Satisfying the optional part 2) above will bring 3hp more.

Preliminary Presentation Date: Jan. 30, 2024

Written Exam Date and Time: Feb. 20, 2024 (08:30 - 12:00)

Lectures

Preliminary dates and times (some of which can also be skipped and/or changed)