Instructor  Emre Telatar 
Office  INR 117 
Phone  +41 21 69 37693 
emre.telatar@epfl.ch  
Office Hours  By appointment 
Teaching Assistant  Erixhen Sula 
Phone  +41 21 69 31229 
Office  INR 031 
erixhen.sula@epfl.ch  
Office Hours  By appointment 
Teaching Assistant  Yunus İnan 
yunus.inan@epfl.ch  
Office Hours  By appointment 
Teaching Assistant  JeanBaptiste Cordonnier 
jeanbaptiste.cordonnier@epfl.ch  
Office Hours  By appointment 
Teaching Assistant  Pierre Quinton 
pierre.quinton@epfl.ch  
Teaching Assistant  Simon Guilloud 
simon.guilloud@epfl.ch 
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 
Course Information
See the course information.
Special Announcements
Midterm Exam

 Tuesday 30 October, 13:1516:00, Location: AAC 2 31.
 The exam is closed book and notes, 1 twosided A4 cheat sheet is allowed.
 Histogram of midterm grades can be found here: midterm_histo
Graded Homework

 Due Monday, December 3. You can prepare handwritten or typewritten sheets for the solutions.
Final Exam

 Tuesday 29 January, 08:1511:15, Location CE4.
 The exam is closed book and notes, 2 twosided A4 cheat sheet is allowed.
 Some old final exams: final2018, final_sol2018, final2016, final_sol2016
Detailed Schedule
Date  Topics Covered  Assignment  Solutions  Remarks  

Sep 17  Public Holiday  
Sep 18  – Introduction to Source Coding – Nonsingular codes – Uniquely decodable codes – Prefixfree codes – Kraft’s inequality for prefixfree codes – Kraft’s sum for products of codes – Kraft’s inequality for nonsingular codes 
hw1.pdf  sol1.pdf  
Sep 24  – Kraft’s inequality for uniquely decodable codes – Reverse Kraft’s inequality – Expected codeword length – Entropy as a lowerbound to the expected codeword length – Existence of prefixfree codes with expected length at most entropy + 1 

Sep 25  – Properties of optimal codes – Huffman procedure – Equivalence of prefixfree codes and strategies for guessing via binary questions 
hw2.pdf  sol2.pdf  
Oct 01  – 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 

Oct 02  – Short reminder for Markov Chains – Minimal and maximal values of H(U) – Data Processing inequality – Entropy Rate – Entropy rate of Stationary Processes – Coding Theorem for Stationary Sources – FixedtoFixed Length Source Codes – Typicality – Properties of Typical Sets – Asymptotic Equipartition Property 
hw3.pdf  sol3.pdf  
Oct 08  – Properties of Typical Sets (cont.) – Source Coding via Typicality – Finite state machine (FSM) compressors – Invertible machines, information lossless (IL) machines 

Oct 09  – Lower bound to the output length for IL FSMs – Universal coding example for iid binary sources – LempelZiv data compression algorithm – analysis and competitive optimality of LempelZiv with respect to FSMs. – asymptotic optimality of LempelZiv 
hw4.pdf  sol4.pdf  Notes on LempelZiv  
Oct 15  – Communication channels – memoryless/stationary channels, communication without feedback – C(W) = max I(X;Y), examples with binary erasure channel and binary symmetric channels 

Oct 16  – Fano’s inequality – Converse Part of Channel Coding Theorem 
hw5.pdf  sol5.pdf  
Oct 22  Computation of C(W), KKT conditions  
Oct 23  – Channel coding theorem – Proofs by random constructions 
hw6.pdf  sol6.pdf  Some old midterm exams  
Oct 29  – Proof of the channel coding theorem via random codes and typicality decoder  
Oct 31  – Midterm  midterm  solutions  
Nov 05  Feinstein’s Theorem  
Nov 06  Channels with input cost Coding theorem for channels with cost 
hw7.pdf  sol7.pdf  
Nov 12  Differential Entropy Properties of Differential Entropy Gaussian Channel 

Nov 13  Parallel Gaussian Channels, waterfilling Bandlimited AWGN Channels 
hw8.pdf  sol08.pdf  
Nov 19  – Hamming code – Hamming weight – Hamming distance 

Nov 20  – Spherepacking bound – Gilbert bound – Singleton bound – Linear codes – Generator and parity check matrices 
hw9.pdf  sol9.pdf  Notes on Coding  
Nov 26  – Polar Codes  
Nov 27  – Polar Codes  hw10.pdf  sol10.pdf  
Dec 3  – Polar Codes  
Dec 4  – RateDistortion Theory (converse part)  hw11.pdf  sol11.pdf  
Dec 10  – RateDistortion Theory (achievability part)  
Dec 11  – Distributed Source Coding (SlepianWolf)  hw12.pdf  sol12.pdf  
Dec 17  – Multiple Access Channel (MAC)  
Dec 18  – Multiple Access Channel (MAC)  hw13.pdf  sol13.pdf  
Jan 29  – Final Exam  final  solutions 
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 LempelZiv 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, McGrawHill.

S. M. Ross, A First Course in Probability, Pearson Education.