Information Theory and Coding

 

Instructor Emre Telatar
Office INR 117
Phone +41 21 69 37693
Email [email protected]
Office Hours By appointment
   
   
Teaching Assistant Elie Najm
Phone +41 21 69 37535
Office INR141
Email [email protected]
Office Hours By appointment
   
   
Teaching Assistant Aleksei Triastcyn
Phone +41 21 69 36674
Office INR 238
Email [email protected]
Office Hours By appointment
   
   
Teaching Assistant Pierre Quinton
Email [email protected]

 

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 31st, at 13:15 in BCH 2201.
  • You are allowed to bring a two-sided A4 handwritten cheat sheet.
  • The material covered is up to and including Homework 6.

Graded Homework

  • The graded homework is out on Tuesday, November 21st and is due on Monday, December 4th 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 23rd, at 08:15 in CM 1105 and CM 1106.
  • You are allowed to bring 2 two-sided 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
– Non-singular codes
– Uniquely decodable codes
– Prefix-free codes
– Kraft’s inequality for prefix-free codes
– Kraft’s sum for products of codes
– Kraft’s inequality for non-singular codes

    hw1.pdf sol1.pdf    
Sep 25  

– Kraft’s inequality for uniquely decodable codes
– Reverse Kraft’s inequality
– Expected codeword length
– Entropy as a lower-bound to the expected codeword length

           

Sep 26

  

– 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    
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
– Fixed-to-Fixed 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   – Lempel-Ziv data compression algorithm
– analysis and competitive optimality of Lempel-Ziv with respect to FSMs.
– asymptotic optimality of Lempel-Ziv 		    hw5.pdf sol5.pdf Notes on Lempel-Ziv  
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
– Converse to the coding theorem

    hw6.pdf sol6.pdf    
Oct 30  

– computation of C(W), KKT conditions

    

midterm_2015.pdf

midterm_2014.pdf

midterm_2013.pdf

midsol_2015.pdf

midsol_2014.pdf

midsol_2013.pdf

    
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
– Entropy-typical 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 (water-filling)
– Proof of Channel Coding Theorem for general channels via Threshold Decoding
– Hamming code
– Hamming weight
– Hamming distance

   

hw9.pdf

Graded Homework

sol9.pdf

Graded homework sol

    
Nov 27   – Sphere-packing bound
– Gilbert bound
– Singleton bound
– Linear codes
– Generator and parity check matrices 		           
Nov 28   – Reed-solomon 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   – Multi-access channel            
Dec 19   – Multi-access channel     hw13.pdf sol13.pdf    
Jan 23         final.pdf finalsol.pdf    

Textbook

Additional Reading Material

To Review Basic Probability Theory