| Instructor | Emre Telatar |
| Office | INR 117 |
| Phone | +41 21 69 37693 |
| [email protected] | |
| Office Hours | By appointment |
| Teaching Assistant | Mani Bastani Parizi |
| Phone | +41 21 69 31359 |
| Office | INR032 |
| [email protected] | |
| Office Hours | By appointment |
| Teaching Assistant | Rafah El-Khatib |
| Phone | +41 21 69 31361 |
| Office | INR 032 |
| [email protected] | |
| Office Hours | By appointment |
| Lectures | Monday | 13:00 – 15:00 (Room: ELA 1) |
| Tuesday | 13:00 – 15:00 (Room: ELA 2) | |
| Exercises | Tuesday | 15:00 – 17:00 (Room: ELA 2) |
| Language: | English | |
| Credits : | 7 ECTS |
See the course information.
Special Announcements
Midterm Exam
Your midterm exam will take place on Tuesday October 27, at 13:15 in rooms ELA2, DIA003, and CO120.
-
Please find your room and seat before the exam according to the following seating plan:
-
This is a closed book exam but you are allowed to have one A4 page of notes (double-sided) with you.
Here is some statistics about midterm grades:
| Average | Standard Deviation | |
|---|---|---|
| P1 | 6.39 | 3.72 |
| P2 | 9.51 | 4.45 |
| P3 | 5.09 | 4.09 |
| Total | 21 | 9.18 |
You can also find a histogram of the grades here.
Final Exam
Your final exam will take place on Monday, January 11, 2016, at 8:15 in rooms INM200 and INM202.
-
Please be there well in advance to find your room and seat.
-
This is a closed book exam, but you are allowed to bring two A4 pages of notes (double-sided) with you.
Detailed Schedule
| Date | Topics Covered | Assignment | Solutions | Remarks | |
|---|---|---|---|---|---|
| Sep 14 | – Introduction to Source Coding – Non-singular codes – Uniquely decodable codes – Prefix-free codes – Kraft’s inequality for prefix-free codes – Kraft’s inequality for extensions of codes |
||||
| Sep 15 | – Kraft’s inequality for uniquely decodable codes – Reverse Kraft’s inequality – Expected codeword length – Entropy as a lower-bound to the expected codeword length |
hw1.pdf | sol1.pdf | ||
| Sep 21 | Public Holiday  |
||||
| Sep 22 | – Existence of prefix-free codes with average length at most entropy + 1 – Entropy of multiple random variables – Properties of optimal codes – Huffman procedure |
hw2.pdf | sol2.pdf | ||
| Sep 28 | – Equivalence of prefix-free codes and strategy for guessing via binary questions – Interpretation of entropy as expected number of questions for guessing the random variable – Conditional Entropy and Mutual Information – Chain Rules for entropy and mutual information |
||||
| Sep 29 | – Review of Markov Chains – Data Processing inequality – Entropy Rate – Entropy rate of Stationary Processes |
hw3.pdf | sol3.pdf | ||
| Oct 5 | – Coding Theorem for Stationary Sources – Fixed-to-Fixed Length Source Codes – Typicality |
||||
| Oct 6 | – Properties of Typical Sets – Asymptotic Equipartition Property – Source Coding by AEP – Variable-to-Fixed Length Source Codes – Valid and Prefix-Free Dictionaries |
hw4.pdf | sol4.pdf | ||
| Oct 12 | – Relationship between word- and letter-entropies for valid, prefix-free dictionaries – Tunstall procedure – Analysis of Tunstall procedure |
Notes on Tunstall Coding | |||
| Oct 13 | – Universal Source Coding – Lempel–Ziv method – Analysis of Lempel–Ziv (finite state machine compressions, FSM compressibility of a sequence, LZ compressibility of a sequence) |
hw5.pdf | sol5.pdf | ||
| Oct 19 | – Information-Lossless FSM Compressors – Lower bound on the output length of an IL FSM Compressor |
Notes on Lempel–Ziv Compression | |||
| Oct 20 | – LZ Compressibility of sequences – Optimality of Lempel–Ziv – Communication Channels – Discrete Memoryless Channels |
hw6.pdf | sol6.pdf | ||
| Oct 26 | – Examples of Discrete Memoryless Channels (BSC and BEC) – Transmission with or without feedback – Channel Capacity – Fano’s Inequality |
||||
| Oct 27 | Midterm Exam | midterm.pdf | midsol.pdf | ||
| Nov 2 | – Converse to the Channel Coding Theorem | ||||
| Nov 3 | – Proof of the Channel Coding Theorem | hw7.pdf | sol7.pdf | ||
| Nov 9 | – Capacity of BSC and BEC – Jensen’s Inequality – Concavity of Mutual Information in Input Distribution – KKT Conditions |
||||
| Nov 10 | – KKT Conditions (cont’d) – Application of KKT: Capacity of Z Channel – Continuous Alphabet: Differential Entropy |
hw8.pdf | sol8.pdf | ||
| Nov 16 | – Properties of differential entropy – Entropy-typical seqeuences – Quantization – Entropy of Gaussian distribution |
||||
| Nov 17 | – Capacity under cost constraint – Capacity of AWGN – Converse to the channel coding theorem with cost constraint – Parallel Gaussian channels (water-filling) |
hw9.pdf | sol9.pdf | ||
| Nov 23 | – Proof of Channel Coding Theorem for general channels via Threshold Decoding | ||||
| Nov 24 | – Channel Codes – Minimum Distance – Singleton Bound – Sphere-packing Bound – Gilbert–Varshamov Bound |
hw10.pdf | sol10.pdf | ||
| Nov 30 | – Linear Codes – Generator Matrix – Parity-check Matrix – Hamming Codes |
||||
| Dec 1 | – Reed–Solomon Codes | hw11.pdf | sol11.pdf | ||
| Dec 7 | – Polar Codes | ||||
| Dec 8 | – Polar Codes | hw12.pdf | sol12.pdf | ||
| Dec 14 | – Polar Codes | ||||
| Dec 16 | – Rate–Distortion Theory | ||||
| Jan 11 | Final Exam | final.pdf | finalsol.pdf |
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.