Information Theory and Coding

Instructor Emre Telatar
Office INR 117
Phone +41 21 69 37693
Email emre.telatar@epfl.ch
Office Hours By appointment
   
   
Teaching Assistant Rajai Nasser
Phone +41 21 69 37554
Office INR 036
Email rajai.nasser@epfl.ch
Office Hours
   
   
Teaching Assistant Serj Haddad
Phone +41 21 69 31357
Office INR038
Email serj.haddad@epfl.ch
Office Hours

Schedule to be confirmed

Lectures Monday 13:00 – 15:00 (Room: ELA01)
  Tuesday 13:00 – 15:00 (Room: ELA02)
Exercises Tuesday 15:00 – 17:00 (Room: ELA02)

 

Language:   English
Credits :   7 ECTS

See the course information.

Special Announcements

Midterm results: midtermresults.pdf.

FINAL EXAM ANNOUNCEMENT
The final exam has been set on Thursday January 16th from 16:15 to 19:15. It will take place in room PO 01. The exam will cover all the topics in the course. You can have twice the number of sheets as in the midterm. No book, no notes, no cellphones, no pocket calculators, or any other electronic devices.
Notes on Tunstall coding, the Lempel-Ziv algorithm, coding theory and polar coding are posted on “Additional Reading Material” section.

Detailed Schedule

 

Date Topics Covered Assignment Solutions Remarks
Sep 16       public holiday,
        no course :-)
         
         
         
Sep 17 Intro to source coding; non-singular, Homework 1 Solutions 1  
  uniquely decodable, prefix-free codes;      
  Kraft’s inequality for prefix-free codes.      
         
         
         
Sep 23 Kraft’s inequality for uniquely decodable      
  codes; lower bound on optimal codes.      
         
         
         
Sep 24 Upper bound on optimal codes; Homework 2 Solutions 2  
  Huffman codes.      
         
         
         
Sep 30 Entropy (H); Properties of H; Joint entropy;      
  Divergence; Conditional entropy;      
  Mutual information (I); Chain rule for H.      
         
         
         
Oct 01 Conditioning reduces entropy; Properties Homework 3 Solutions 3  
  of I; Conditional mutual information;      
  Chain tule for I; Interpretation of H.      
         
         
         
Oct 07        
         
         
         
Oct 08   Homework 4 Solutions 4  
         
         
         
Oct 14        
         
         
         
Oct 15   Homework 5 Solutions 5  
         
         
         
Oct 21        
         
         
         
Oct 22   Homework 6 Solutions 6  
         
         
         
Oct 28        
         
         
         
Oct 29   Midterm Solutions  
         
         
         
Nov 04        
         
         
         
Nov 05   Homework 7 Solutions 7  
         
         
         
Nov 11        
         
         
         
Nov 12   Homework 8 Solutions 8  
         
         
         
Nov 18        
         
         
         
Nov 19   Homework 9 Solutions 9  
         
         
         
Nov 25        
         
         
         
Nov 26   Homework 10 Solutions 10  
         
         
         
Dec 02        
         
         
         
Dec 03        
         
         
         
Dec 09        
         
         
         
Dec 10   Homework 11 Solutions 11  
         
         
         
Dec 16        
         
         
         
Dec 17   Homework 12 Solutions 12  
         
         
         
         
         
         
         
  Final exam 2012 Final Solutions  
         
         
         
  Final exam 2013 Final Solutions  
         
         
         
  Final exam 2014 Final Solutions  

Textbook

Elements of information theory, Thomas M. Cover, Joy A. Thomas, 2006. ISBN:0-471-24195-4

Additional Reading Material

Claude Shannon’s A Mathematical Theory of Communication, published in Bell System Technical Journal, 1948 (part 1 in July, part 2 in October)

Notes on Tunstall codes: Tunstall
Notes on the Lempel-Ziv algorithm: Lempel-Ziv
Notes on coding theory: Coding
Presentation on polar codes: Polar