Information Theory, 2021



The course provides a general introduction to the topic of Information Theory with a focus on the application of Information Theory to communications in general and on channel coding and capacity in particular.

Outline: entropy and mutual information, the asymptotic equipartition principle, entropy for stochastic processes (entropy rate), introduction to data compression and source coding, channel capacity and coding for noisy channels, capacity for different channel models (with emphasis on discrete memoryless channels and Gaussian channels), finite field theory, design and analysis of error correcting codes (with a focus on linear block codes), introduction to network information theory

Format: Teaching the course will be based on one meeting, or seminar, per week (with about 12 meetings total, for the complete doctoral student version). The examination of the course will be based on: active participation, homework problems and, for the doctoral student version (see below), presentation/review of an article in the field. The overall emphasis is on individual off-class problem solving, based on relatively demanding homework problems. More information about these can be found here.

Two versions: The course is eligible for both undergraduate (EQ2840, 7.5cu) and doctoral (FEO3210, 12cu) students. The difference between the two versions of the course is in the extent and level of difficulty of the material included. With reference to the course schedule the senior undergraduate version, EQ2840, will amount to the material treated in meetings 1-8 while FEO3210 includes in addition the theoretically more demanding material corresponding to meetings 9-11 as well as a separate presentation/review of a research paper in the field.

Course responsible: Mikael Skoglund


Requirements

The main focus is on homework problems. Homework assignments will be handed out at meetings and will also be made available on the homepage. The deadline for handing in solutions for the assignment handed out on meeting N is at meeting N+1.

Each assignment (set of homework problems) will be graded according to (thresholds given are approximate):
-1:less than 5% of assignment solved correctly
0:between 5% and 40% of assignment solved correctly
1:between 40% and 80% of assignment solved correctly
2:more than 80% of assignment solved correctly
Note that solving less that 5%, or failing to hand in by the deadline, gives minus one point.

Based on the above, the total grade for the course will be set according to:

Senior undergraduate version, 8 assignments total:
grade A: 15-16 points
grade B: 13-14 points
grade C: 10-12 points
grade D: 8-9 points
grade E: 6-7 points
grade F: less than 6 points


Doctoral student version, 11 assignments total:
pass: > 14 points + paper presentation


Course Material

Textbooks

Main textbook: "Elements of Information Theory," Second. Ed., by T. Cover and J. Thomas (Wiley 2006: ISBN 0-471-24195-4, available as e-book via the KTH library).

Second textbook: "Introduction to Coding Theory," R. M. Roth (Cambridge 2006: ISBN 0-521-84504-1)

Other material used: Journal papers in the field, handouts will be provided.


Homework Problems

Teaching the course and its examination will be based on mandatory homework problems. Solutions to homework problems are to be handed in.

Cooperation between students will be allowed according to the following principle: Students are allowed to discuss homework problems orally. That is, students are not allowed to use paper and pen, a computer, a white/black board, etc., when discussing the homework problems with other students.


Preliminary Schedule 2021

lecdatetimeroomtopicchteacher
1March 2613:15-15:00Zoomentropy and mutual information2MS
2April 1210:15-12:00Zoomthe AEP, entropy rate, intro to data compression3,4,5MS
3April 1610:15-12:00Zoomlossless source coding5MS
4April 2310:15-12:00Zoomintro to channel capacity and coding7MS
5April 2910:15-12:00ZoomGaussian channels8-9MS
6May 613:15-15:00Zoomblock codes and finite fieldsRoth 2-3MS
7May 1213:15-15:00Zoomfinite fields and cyclic codesRoth 3,7-8MS
8May 2110:15-12:00ZoomBCH and Reed-Solomon codesRoth 5-6MS
9May 2810:15-12:00ZoomGallager (error exponents, Gallager's paper)Gallager's paperMS
10June 410:15-12:00Zoomnetwork info theory15MS
11June 1110:15-12:00ZoomVerdu and Han (a general formula)handoutMS
12Sept 39:30-13:00HNPaper presentationsMS

HN = Harry Nyquist, Malvinas väg 10, floor 7

The lectures will be presented over Zoom (in real-time, leaving room for questions etc.). Zoom links will be posted in the schedule above (fourth column). For the later part of the course we may move to physical meetings, depending on how the Covid-19 situation unfolds in the Stockholm region.


Paper Presentations

For the presentation, you can select any paper that has appeared in the IEEE Transactions on Information Theory. You need to present the paper and its contribution, and you also need to critically assess it and comment on its potential weaknesses. You have 15 minutes.


Downloads

Note: For HW1, submit your solutions scanned or photographed (or written in latex or similar), preferably as a pdf-file, in an email to Mikael. The HW problems will be marked by Amir Zamanisiboni (AZ) and Hasan Basri Celebi (HBC), as indicated below. If you get stuck you can contact Amir or Hasan to get hints. Also, starting from HW2, please send your solutions directly to Amir or Hasan (not to Mikael). The results of the grading will be reported back to you via email (from Amir or Hasan).