Information theory and coding
COM-404
This file is part of the content downloaded from Information theory and coding.
Course Instructor
- Emre Telatar, INR 117, emre.telatar@epfl.ch
Teaching Assistants
- Adway Girish, INR 139, adway.girish@epfl.ch
- Adrien Vandenbroucque, INR 033, adrien.vandenbroucque@epfl.ch
Lectures
- Monday, 11h15-13h00, BC 01
- Tuesday, 13h15-15h00, CM 012
Exercise session
- Tuesday, 15h15-17h00, DIA 004
Grading scheme
- Midterm 40% (October 29th, 2024, 13h15 to 16h15, in ELD 020)
- Graded Homework 10% (tentatively due mid-December)
- Final 50% (January 13th, 2025)
Textbook
- T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley.
(9/9)
Source coding / Data compression (Chapter 5 of the textbook):
- Injective, uniquely decodable, prefix-free (binary) codes
- Kraft sum, Kraft inequalities
(10/9)
- (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)
(16/9) [Holiday]
(17/9)
- Expected codeword length: lower and upper bounds, asymptotic per-letter tightness
Information measures (Chapter 2 of the textbook):
- Entropy
- KL divergence
(17/9)
- Expected codeword length: lower and upper bounds, asymptotic per-letter tightness
Information measures (Chapter 2 of the textbook):
- Entropy
- KL divergence
- Lecture 3 (2020) (URL)
- Lecture 3 Notes (2020) (File)
- Homework 2 (File)
- Solutions to Homework 2 (File)
(23/9)
- Huffman code/algorithm
- Mutual information
- Examples, properties
- Data processing inequality
- Huffman code/algorithm
- Mutual information
(24/9)
- Conditional mutual information- Examples, properties
- Data processing inequality
- Homework 3 (File)
- Solutions to Homework 3 (File)
- Lecture 4 (2020) (URL)
- Lecture 4 Notes (2020) (File)
(30/9)
- Chain rule for mutual information
- Typicality
(1/10)
- Properties of typical sets/sequences
- Entropy rate
- Chain rule for mutual information
- Typicality
(1/10)
- Properties of typical sets/sequences
- Entropy rate
- Homework 4 (File)
- Solutions to Homework 4 (File)
- Lecture 5 (2020) (URL)
- Lecture 6 (2020) (URL)
- Lecture 5 Notes (2020) (File)
- Lecture 6 Notes (2020) (File)
(7/10)
- More on entropy rate
Universal data compression (notes on Lempel-Ziv on Moodle, Chapter 13 of the textbook):
- Universal compression: Lempel-Ziv
(8/10)
- Universal compression
- More on entropy rate
Universal data compression (notes on Lempel-Ziv on Moodle, Chapter 13 of the textbook):
- Universal compression: Lempel-Ziv
(8/10)
- Universal compression
- 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)
(14/10)
- Universal compression and predictionTransmission of data (Chapter 7 of the textbook):
- Channels
(15/10)
- Stationary, memoryless channels without feedback
- 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] 21 October - 27 October
[Midterm week] 28 October - 3 November
(28/10)
- Converse theorem of channel coding
(29/10) Midterm exam, 13h15 to 16h15, in ELD 020 (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.
- Six previous years' midterms and their solutions have been uploaded below, for your practice.
- Previous midterms (Folder)
- Lecture 11 (2020) (URL)
- Lecture 11 Notes (2020) (File)
- Midterm 2024 (File)
- Solutions to Midterm 2024 (File)
(4/11)
- KKT conditions for capacity
(5/11)
- Random coding argument to show achievability of coding theorem
- KKT conditions for capacity
(5/11)
- 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)
(11/11)
- Channel coding: good news proof
(12/11)
Differential entropy (Chapter 8 of the textbook):
- Definition
- Channel coding: good news proof
(12/11)
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)
(18/11)
- Properties of differential entropy
(19/11)
- Gaussian channel
- Properties of differential entropy
(19/11)
- 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)
(25/11)
- 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
(2/12)
- Good news theorem of rate-distortion theory
(3/12)
Rudimentary coding theory (Notes on coding, Moodle---posted in next week's section)
- Good news theorem of rate-distortion theory
(3/12)
Rudimentary coding theory (Notes on coding, Moodle---posted in next week's section)
- 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)
(9/12)
- Coding theory
(10/12)
- More coding theory
- 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)
(16/12)
- Polar codes
(17/12)
- 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)