| Lectures | Monday | 11:00 – 13:00 (Room: BC01) |
| Tuesday | 13:00 – 15:00 (Room: ELA 2) | |
| Exercises | Tuesday | 15:00 – 17:00 (Room: ELA 2) |
| Language: | English | |
| Credits : | 7 ECTS |
Course Information
See the course information.
Special Announcements
Midterm Exam (40%)
-
- Midterm date: 29 October, Place: ELA2 and DIA 004.
- Closed book, closed notes.
- ONE two-sided A4 cheat sheet allowed.
Graded Homework (10%)
-
- Due Tuesday, December 3, at the beginning of the exercise session. You can prepare handwritten or typewritten sheets for the solutions.
Final Exam (50%)
-
- Final date: 18 January, 08.15-11.15, Place: CE4.
- Closed book, closed notes.
- TWO two-sided A4 cheat sheet allowed.
Detailed Schedule
| Date | Topics Covered | Assignment | Solutions | Remarks |
|---|---|---|---|---|
| Sep 16 | Public Holiday | |||
| Sep 17 | – Introduction to Source Coding – Non-singular codes – Uniquely decodable codes – Prefix-free codes – Kraft’s inequality for prefix-free codes – Kraft’s sum for products of codes |
hw1.pdf | sol1.pdf | |
| Sep 23 | – Kraft’s inequality for non-singular codes
– Kraft’s inequality for uniquely decodable codes – Reverse Kraft’s inequality – Expected codeword length |
|||
| Sep 25 |
– Entropy as a lower-bound to the expected codeword length – Existence of prefix-free codes with expected length at most entropy + 1 – Properties of optimal codes – Huffman procedure – Equivalence of prefix-free codes and strategies for guessing via binary questions |
hw2.pdf | sol2.pdf | |
| Sep 30 |
– Entropy of multiple random variables – Source coding by describing words of n letters – Conditional entropy and mutual information – Chain Rules for entropy and mutual information – Short reminder for Markov Chains – Minimal and maximal values of H(U) – Data Processing inequality |
|||
| Oct 01 |
– Entropy Rate – Entropy rate of Stationary Processes – Coding Theorem for Stationary Sources – Fixed-to-Fixed Length Source Codes – Typicality – Properties of Typical Sets – Asymptotic Equipartition Property |
hw3.pdf | sol3.pdf | |
| Oct 07 | – Source Coding via Typicality
– Finite state machine (FSM) compressors |
|||
| Oct 08 | -Invertible machines, information lossless (IL) machines
– Lower bound to the output length for IL FSMs |
hw4.pdf | sol4.pdf | |
| Oct 14 | (Lecture by Ruediger Urbanke)
– Communication channels – memoryless/stationary channels, communication without feedback – C(W) = max I(X;Y), examples with binary erasure channel and binary symmetric channels -Multi-letter Fano’s Inequality |
|||
| Oct 15 | (Lecture by Ruediger Urbanke)-Weak converse of noisy channel coding theorem
-The necessity part of KKT condition for capacity achieving input distribution. |
hw5.pdf | sol5.pdf | |
| Oct 21 | -Review of the last lecture
-The sufficiency part of KKT condition for capacity achieving input distribution. -Computation of capacity C(W). |
|||
| Oct 22 | -Information Lossless machines cont.
-Lempel Ziv Algorithm |
hw6.pdf | sol6.pdf | Some old midterm exams |
| Oct 28 | – Channel coding theorem
– Channels with input cost – Proofs by random constructions |
|||
| Oct 29 | Midterm | midterm.pdf | midsol.pdf | histogram |
| Nov 4 | Exercise session (No lecture) |
hw7.pdf | sol7.pdf | |
| Nov 5 | -Differential Entropy
-Properties of Differential Entropy |
|||
| Nov 11 | -Relationship between H(X) and h(X)
-Entropy of Gaussian R.Vs -Capacity of Gaussian Channel |
|||
| Nov 12 | -Parallel Gaussian Channels, water-filling
-Bandlimited AWGN Channels |
hw8.pdf | sol8.pdf | |
| Nov 18 | – Hamming codes- Hamming weight
– Hamming distance |
Notes on coding | ||
| Nov 19 | – Sphere-packing bound- Gilbert bound
– Singleton bound – Linear codes – Generator and parity check matrices |
hw9.pdf | sol9.pdf | gradedHW |
| Nov 25 | – Polar Codes | |||
| Nov 26 | – Polar Codes | hw10.pdf | sol10.pdf | |
| Dec 2 | – Polar Codes | |||
| Dec 3 | -Rate-Distortion Theory | hw11.pdf | sol11.pdf | |
| Dec 9 | -Rate-Distortion Theory | |||
| Dec 10 | -Slepian-Wolf Coding | hw12.pdf | sol12.pdf | |
| Dec 16 | -Multiple Access Channels (MAC) (Achievability) | |||
| Dec 17 | -Multiple Access Channels (MAC) (Converse) | hw13.pdf | sol13.pdf | |
| Jan 18 | Final Exam | Final | Final Sol |
Textbook
-
T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley 2006.
Additional Reading Material
- C. E. Shannon, A Mathematical Theory of Communications, Bell System Technical Journal, 1948.
-
Notes on Tunstall Coding.
-
Notes on Lempel-Ziv Algorithm
To Review Basic Probability Theory
-
K. L. Chung, A Course in Probability Theory, Academic Press.
-
W. Feller, An Introduction to Probability Theory and Its Applications, Wiley.
-
G. Grimmett and D. Stirzaker, Probability and Random Processes, Oxford University Press.
-
A. Papoulis, Probability, Random Variables, and Stochastic Processes, McGraw-Hill.
-
S. M. Ross, A First Course in Probability, Pearson Education.