Instructor  Emre Telatar 
Office  INR 117 
Phone  +41 21 69 37693 
emre.telatar@epfl.ch  
Office Hours  By appointment 
Teaching Assistant  Elie Najm 
Phone  +41 21 69 37535 
Office  INR141 
elie.najm@epfl.ch  
Office Hours  By appointment 
Teaching Assistant  Aleksei Triastcyn 
Phone  +41 21 69 36674 
Office  INR 238 
aleksei.triastcyn@epfl.ch  
Office Hours  By appointment 
Teaching Assistant  Pierre Quinton 
pierre.quinton@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
 Your midterm exam will take place on Tuesday October 31^{st}, at 13:15 in BCH 2201.
 You are allowed to bring a twosided A4 handwritten cheat sheet.
 The material covered is up to and including Homework 6.
Graded Homework
 The graded homework is out on Tuesday, November 21^{st} and is due on Monday, December 4^{th} at 13:15.
 You are allowed to collaborate among yourselves but you have to write your own solution and indicate who you collaborated with.
Final Exam
 Your final exam will take place on Tuesday January 23^{rd}, at 08:15 in CM 1105 and CM 1106.
 You are allowed to bring 2 twosided A4 handwritten cheat sheets (2 sheets, 4 pages).
 The exam covers all the material seen in class during the semester.
Detailed Schedule
Date  Topics Covered  Assignment  Solutions  Remarks  

Sep 18  Public Holiday  
Sep 19 
– Introduction to Source Coding 
hw1.pdf  sol1.pdf  
Sep 25 
– Kraft’s inequality for uniquely decodable codes 

Sep 26 
– Existence of prefixfree codes with expected length at most entropy + 1 
hw2.pdf  sol2.pdf  
Oct 02  – 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 03  – Short reminder for Markov Chains – Minimal and maximal values of H(U) – Data Processing inequality – Entropy Rate – Entropy rate of Stationary Processes 
hw3.pdf  sol3.pdf  
Oct 09  – Coding Theorem for Stationary Sources – FixedtoFixed Length Source Codes – Typicality 

Oct 10  – Properties of Typical Sets – Asymptotic Equipartition Property – Source Coding via Typicality – Universal coding example for iid binary sources 
hw4.pdf  sol4.pdf  
Oct 16  – Finite state machine (FSM) compressors – invertible machines, information lossless (IL) machines – lower bound to the output length for IL FSMs 

Oct 17  – LempelZiv data compression algorithm – analysis and competitive optimality of LempelZiv with respect to FSMs. – asymptotic optimality of LempelZiv 
hw5.pdf  sol5.pdf  Notes on LempelZiv  
Oct 23  – Communication channels – memoryless/stationary channels, communication without feedback – C(W) = max I(X;Y), examples with binary erasure channel and binary symmetric channels 

Oct 24 
– Fano’s inequality 
hw6.pdf  sol6.pdf  
Oct 30 
– computation of C(W), KKT conditions 

Oct 31  Midterm  midterm.pdf  midsol.pdf  
Nov 06  – channel coding theorem – proofs by random constructions 

Nov 07  – proof of the channel coding theorem via random codes and typicality decoder  hw7.pdf  sol7.pdf  
Nov 13  – revisit the random coding method for the BEC – differential entropy and its properties 

Nov 14  – Properties of differential entropy – Entropytypical seqeuences – Quantization – Entropy of Gaussian distribution 
hw8.pdf  sol8.pdf  
Nov 20  – Capacity under cost constraint – Capacity of AWGN – Converse to the channel coding theorem with cost constraint 

Nov 21 
– Parallel Gaussian channels (waterfilling) 

Nov 27  – Spherepacking bound – Gilbert bound – Singleton bound – Linear codes – Generator and parity check matrices 

Nov 28  – Reedsolomon codes – Polar codes 
hw10.pdf  sol10.pdf  
Dec 04  – Polar codes  Coding Notes  
Dec 05  – Polar codes  hw11.pdf  sol11.pdf  
Dec 11  – Rate distortion  
Dec 12  – Rate distortion  hw12.pdf  sol12.pdf  
Dec 18  – Multiaccess channel  
Dec 19  – Multiaccess channel  hw13.pdf  sol13.pdf  
Jan 23  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 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.