Information Theory and Coding

Instructor Emre Telatar
Office INR 117
Phone +41 21 69 37693
Email [email protected]
Office Hours By appointment
   
   
Teaching Assistant Yunus Inan
Phone +41 21 69 36604
Office INR 033
Email [email protected]
Office Hours By appointment
   
   
Lectures Monday 11:00 – 13:00 (Room: BC 01)
  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.

Moodle link

 

Special Announcements

The weekly homeworks are not graded. The graded homework will be announced explicitly.

 

Midterm Exam

  • 40%, November 2nd, 13:15 pm.
  • The exam will take place in ELA2 (Arruat-Ozalp) and DIA3 (Pariset-Zimmermann)
  • The exam coverage is until and including Universal Compression, i.e., Handout 11. Channel coding is not part of the exam
  • You are allowed to bring ONE A4 cheat sheet, whose BOTH sides can be scribed.
  • Bring your CAMIPRO cards, or a valid ID with a visible photo.

Graded Homework

  • 10%, Due 10 Dec, 17:00, you can prepare handwritten or typewritten sheets for the solutions.

Final Exam

  • 50%, February 1st, 8:15 am
  • The exam will take place in INM202
  • You are allowed to bring TWO A4 cheat sheets, whose BOTH sides can be scribed.
  • Bring your CAMIPRO cards, or a valid ID with a visible photo.

 

Detailed Schedule

Date   Topics Covered     Assignment Solutions Remarks  
Sep 20             Public Holiday  
Sep 21   – 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 27   – 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 28   – Existence of prefix-free codes with expected length at most entropy + 1
– Properties of optimal codes		     hw2.pdf sol2.pdf    
Oct 4   – Huffman procedure
– Entropy of multiple random variables
– Source coding by describing words of n letters		            
Oct 5   – Conditional entropy and mutual information
– Chain Rules for entropy and mutual information
– Short reminder for Markov Chains
– Minimal and maximal values of H(U)
– Data Processing inequality		     hw3.pdf sol3.pdf    
Oct 11   – Entropy Rate
– Entropy rate of Stationary Processes
– Coding Theorem for Stationary Sources
– Fixed-to-Fixed Length Source Codes		            
Oct 12   – Typicality
– Properties of Typical Sets		     hw4.pdf sol4.pdf    
Oct 18   – Asymptotic Equipartition Property
– Source Coding via Typicality		         Notes on Universal Coding  
Oct 19   -Invertible machines, information lossless (IL) machines
– Lower bound to the output length for IL FSMs		     hw5.pdf sol5.pdf    
Oct 25   -Lempel-Ziv algorithm
– Upper bound to the output length for Lempel-Ziv
– Communication channels
-Memoryless/stationary channels, communication without feedback		            
Oct 26   – C(W) = max I(X;Y), examples with binary erasure channel and binary symmetric channels
-Multi-letter Fano’s Inequality		     hw6.pdf sol6.pdf Some Previous Midterms
mt2019 sol2019
mt2018 sol2018		  
Nov 1   -Channel coding converse
-The necessity part of KKT condition for capacity achieving input distribution		            
Nov 2   -Midterm     mt.pdf mt_sol.pdf    
Nov 8   -The sufficiency part of KKT condition for capacity achieving input distribution
-Computation of capacity C(W)		            
Nov 9   -Channel coding theorem & Proofs by random constructions     hw7.pdf sol7.pdf    
Nov 15   -Channel coding theorem (cont.)
-Differential entropy		            
Nov 16   -Properties of Differential Entropy
-Relationship between H(X) and h(X)		     hw8.pdf sol8.pdf    
Nov 22   -Entropy of Gaussian R.Vs
-Entropy maximizing distributions		            
Nov 23   -Capacity of Gaussian Channel
-Parallel Gaussian Channels, water-filling
-Bandlimited AWGN Channels		     hw9.pdf sol9.pdf    
Nov 29   -Rate-Distortion Theory            
Nov 30   -Rate-Distortion Theory (cont.)     hw10.pdf sol10.pdf Graded Hw 
Graded_Hw_Sol		  
Dec 6   -Hamming codes
-Hamming weight
-Hamming distance
-Sphere-packing bound		         Notes on Coding  
Dec 7   -Gilbert–Varshamov bound
-Singleton bound
-Linear codes		     hw11.pdf sol11.pdf    
Dec 13   -Generator and parity check matrices
-Reed–Solomon codes		            
Dec 14   -Polar codes     hw12.pdf sol12.pdf    
Dec 20   -Polar codes            
Dec 21   -Polar codes     hw13.pdf sol13.pdf    
Feb 1   -Final Exam         final_exam
final_exam_sol		  

 

Textbook

Additional Reading Material

To Review Basic Probability Theory