Information theory and coding
COM-404
Course Instructor
- Emre Telatar, INR 117, emre.telatar@epfl.ch
Teaching Assistants
- Serhat Emre Coban, INR 036, serhat.coban@epfl.ch
Lectures
- Monday, 11h15-13h00, BC 03
- Tuesday, 13h15-15h00, MXG110
Exercise session
- Tuesday, 15h15-17h00, CM 013
Grading scheme
- Midterm 40% (October 28th, 2025, 13h15 to 16h15 (location: SG0213))
- Graded Homework 10% (tentatively due mid-December)
- Final 50% (To be announced by SAC)
Textbook
- T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley.
(8 september)
Source coding / Data compression (Chapter 5 of the textbook):
- Injective, uniquely decodable, prefix-free (binary) codes
- Kraft sum, Kraft inequalities
(9 september)
- (Partial) converse to Kraft inequality
- Expected codeword length: lower bound
- Homework 1 (File)
- Solutions to Homework 1 (File)
- Lecture 1 (2020) (URL)
- Lecture 2 (2020) (URL)
- Lecture 1 Notes (2020) (File)
- Lecture 2 Notes (2020) (File)
- Expected codeword length: lower and upper bounds, asymptotic per-letter tightness
Information measures (Chapter 2 of the textbook):
- Entropy
- KL divergence
- Huffman code/algorithm
(16 sept)
- Some properties of Entropy
- Conditional Entropy, Joint Entropy, Chain rule for entropy
- Source coding with side information
- Mutual information, conditional mutual information
- Properties of mutual information
- Chain Rule for mutual information
- Lecture 3 (2020) (URL)
- Lecture 4 (2020) (URL)
- Lecture 3 Notes (2020) (File)
- Lecture 4 Notes (2020) (File)
- Homework 2 (File)
- Solutions to Homework 2 (File)
- Public Holiday in Vaud (No lecture)
- Data processing inequality
- Markov Chains
- Homework 3 (File)
- Solutions to Homework 3 (File)
- Lecture 4 (2020) (copy) (URL)
- Lecture 5 (2020) (URL)
- Lecture 4 Notes (2020) (copy) (File)
- Lecture 5 Notes (2020) (File)
- Entropy on stationary processes
- Typicality
(30 sept)
- Properties of typical sets/sequences
- Entropy rate
- KL divergence as regret
- minmax regret
- Homework 4 (File)
- Solutions to Homework 4 (File)
- Lecture 5 (2020) (Entropy rate, stationary processes, typical sequences) (URL)
- Lecture 6 (2020) (Typicality) (URL)
- Lecture 7 (2020) (for KL divergence and minmax regret part) (URL)
- Lecture 5 Notes (2020) (Entropy rate, stationary processes, typical sequences) (File)
- Lecture 6 Notes (2020) (Typicality) (File)
- Lecture 7 Notes (2020) (for KL divergence and minmax regret part) (File)
- More on entropy rate
- Universal compression Example
- Lempel-Ziv
(7/10)
- Lempel-Ziv
- Finite State Machines (FSM)
- Some related concepts (Information Lossless (IL), Distinct Parsings)
- Analysis of Lempel-Ziv algorithm in comparison to IL-FSM
- Homework 5 (File)
- Solutions to Homework 5 (File)
- Lempel-Ziv Notes (File)
- Lecture 7 (2020) (URL)
- Lecture 8 (2020) (URL)
- Lecture 7 Notes (2020) (File)
- Lecture 8 Notes (2020) (File)
- Data Transmission
- Channels and Capacity
(14 October)
- Stationary, memoryless channels without feedback
- Fano Inequality
- Channel coding with stationary sources
- Relating error-rate with entropy-rate and channel capacity
- Homework 6 (File)
- Solutions to Homework 6 (File)
- Lecture 9 (2020) (URL)
- Lecture 10 (2020) (URL)
- Lecture 9 Notes (2020) (File)
- Lecture 10 Notes (2020) (File)
[Break] 20 October - 26 October
[Midterm week] 27 October - 2 November
(27 October)
- Converse theorem of channel coding
(28 October) Midterm exam, 13h15 to 16h15, in SG0213 (note the different location)
- You are allowed a single A4 sheet (2 sides) as a cheatsheet. This may be prepared however you like --- hand-written on
paper, printed from tablet, LaTeX, and so on --- but you are strongly
encouraged to make your own.
- Seven previous years' midterms and their solutions have been uploaded below, for your practice.
- Previous midterms (Folder)
- Midterm Solutions (copy) (File)
- Lecture 11 (2020) (URL)
- Lecture 11 Notes (2020) (File)
- KKT conditions for capacity
(4 November)
- Random coding argument to show achievability of coding theorem
- Homework 7 (File)
- Solutions to Homework 7 (File)
- Lecture 12 (2020) (URL)
- Lecture 13 (2020) (URL)
- Lecture 12 Notes (2020) (File)
- Lecture 13 Notes (2020) (File)
- Channel coding: good news proof
(11 november)
Differential entropy (Chapter 8 of the textbook):
- Definition
- Homework 8 (File)
- Solutions to Homework 8 (File)
- Lecture 14 (2020) (URL)
- Lecture 15 (2020) (URL)
- Lecture 14 Notes (2020) (File)
- Lecture 15 Notes (2020) (File)
- Midterm Solutions (File)
- Properties of differential entropy
(18 november)
- Gaussian channel
- Homework 9 (File)
- Solutions to Homework 9 (File)
- Lecture 16 (2020) (URL)
- Lecture 17 (2020) (URL)
- Lecture 16 Notes (2020) (File)
- Lecture 17 Notes (2020; waveform channels, not covered this year) (File)
(24 November)
- Parallel Gaussian channel
Lossy compression (Chapter 10 of the textbook):
- Rate-distortion theory
- Homework 10 (File)
- Solutions to Homework 10 (File)
- Lecture 18 (2020; second half will be covered later) (URL)
- Lecture 19 (2020; polar codes will be covered later) (URL)
- Lecture 18 Notes (2020; second half will be covered later) (File)
- Lecture 19 Notes (2020; polar codes will be covered later) (File)
[Graded HW] 4 December - 10 December
- Good news theorem of rate-distortion theory
2 December
Rudimentary coding theory (Notes on coding, Moodle---posted in next week's section)
- Graded Homework (File)
- latex template for graded hw (Folder)
- Solutions to Graded Homework (File)
- Homework 11 (File)
- Solutions to Homework 11 (File)
- Lecture 20 (2020) (URL)
- Lecture 21 (2020; contd. from second half of Lecture 18 Notes) (URL)
- Distributed source coding (2020; not covered this year) (URL)
- Lecture 20 Notes (2020) (File)
- Lecture 21 Notes (2020; contd. from second half of Lecture 18 Notes) (File)
- Distributed source coding Notes (2020; not covered this year) (File)
8 December
- Coding theory
9 December
- More coding theory
- Notes on coding (File)
- Homework 12 (File)
- Solutions to Homework 12 (File)
- Lecture 22 (2020) (URL)
- Lecture 23 (2020) (URL)
- Lecture 22 Notes (2020) (File)
- Lecture 23 Notes (2020) (File)
15 December
- Polar codes
16 December
- Polar codes
- Homework 13 (File)
- Solutions to Homework 13 (File)
- Lecture 24 (2020) (URL)
- Lecture 25 (2020) (URL)
- Lecture 26 (2020) (URL)
- Lecture 24 Notes (2020) (File)
- Lecture 25 Notes (2020) (File)
- Lecture 26 Notes (2020) (File)
[Final month] 1 January - 22 January
Final exam, January 22 Thursday, 9h15 to 12h15, in CM 1106
- You are allowed two A4 sheets (total of 4 sides) as a cheatsheet. This may be prepared however you like --- hand-written on
paper, printed from tablet, LaTeX, and so on --- but you are strongly
encouraged to make your own.
- Eight previous years' finals and their solutions have been uploaded below, for your practice.