ECE 563  Information Theory (Fall 2022)
Lecturer: Olgica Milenkovic (Office hours: Tuesday 3:004:00pm, 311 CSL or by appointment as needed)
Teaching Assistants: Rebecca Golm (Office hours: Wednesday 2:003:30pm, ECEB 5034; rgolm2@illinois.edu)
Lectures: Tuesday and Thursday, 12:30pm, Electrical and Computer Engineering Building ECEB 3081
Problem Solving Sessions: The sessions will start in the week of September 12th, 2022. Attendance is optional, Wednesday 3:30pm4:30pm, ECEB 2015
Course Objectives:
Catalog Description
Mathematical models for channels and sources; entropy, information, data compression, channel capacity, Shannon's theorems, and ratedistortion theory.
Prerequisites: Solid background in probability (ECE 534, MATH 464, or MATH 564).
Textbook: T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006.
Grading: Homework (25%), Midterm exam: 5:00pm7:00pm, October 21st, 2022 in ECEB 2015 (25%), Final exam: 8:00am11:00am, Tuesday Dec. 13, 2022 (25%), Group project/paper (25%)
Midterm I: 5:00pm7:00pm, October 21st, 2022 in ECEB 2015
Project Presentations: December 2022, Exact time/location TBD.
Final Exam: 8:00am11:00am, Tuesday Dec. 13, 2022, Location: TBD
Research Project Topics
Genomic Data Compression Review paper
The Information Bottleneck Problem Research paper
Lovasz number of a graph Lecture notes
Quantized Deep Learning Blog
Capacity of DNAStorage Channels Research paper
Polar codes Research paper
Network coding Text
Quantum information theory Introduction
Renyi entropy NeurIPS paper
Deletion errorcorrection and capacity of deletion channels Review paper by Sloane
Channel dispersion: finite blocklength regime Y. Polyansky et al., see also the prior work by Strassen.
Additional Instructional Material
Entropy in Physics (Video, TEDed)
Operational Characterization of Entropy (Video, Khan Academy)
The first lecture on the axiomatic derivation of Shannon's entropy is based on R. Ash, Information Theory, pp. 512. More on axiomatic approaches can be found here Entropy axioms
Lecture subjects, Fall 2022
2. Thursday, August 25th: Axioms of Shannon entropy, derivation of the Shannon entropy function through an axiomatic approach, properties of Shannon entropy
3. Tuesday, August 30th: Conditional entropy, Joint entropy, Conditioning reduces entropy, KulbackLeibler divergence, Mutual information
4. Thursday, September 1st: Problem solving session
5. Tuesday, September 6th: Data processing inequality, Jensen's inequality, the Logsum inequality, Fano's inequality
6. Thursday, September 8th: Typical sequences and the asymptotic equipartition property, compressing typical sequences
8. Thursday, September 15th: Data compression  Shannon codes, Huffman codes, optimality of Huffman codes
9. Tuesday, September 20th: Data compression  Extended Huffman codes, Entropy rates and compression of stationary sources
10. Thursday, September 22th: Data compression  Adaptive Huffman codes
11. Tuesday, September 27th: Data compression  Adaptive Huffman codes continued
12. Thursday, September 29th: Data compression  Tunstall codes, Runlength codes
13. Tuesday, October 4th: Examples of channels, information channel capacity, symmetric channels
14. Thursday, October 6th: Joint typicality
15. Tuesday, October 11th: Shannon's second theorem (channel capacity theorem)  achievability
16. Thursday, October 13th: Recap of Fano's inequality, Shannon's second theorem (channel capacity theorem)  converse
17. Thursday, October 18th: Practical errorcorrection codes  Hamming codes, paritycheck matrices, minimum Hamming distance of codes, linear codes
18. Thursday, October 20th: Practical errorcorrection codes  Dual codes, spherepacking bound, Singleton bound, introduction to finite fields
19. Tuesday, October 25th: Practical errorcorrection codes  Constructions of finite fields, irreducible and primitive polynomials and elements, BCH and RS code
20. Thursday, October 27th: Practical errorcorrection codes  Regular and irregular LDPC codes, the peeling decoder for BECs, stopping sets, belief propagation decoding for the BSC
Homework, Fall 2022
Problem Solving Sessions, Fall 2019
Recitations, Fall 2022
Topics:
Course Schedule from Fall 2019
Date  Topic  Reading Assignment  Learning Objectives  Multimedia Supplements 
8/28 
1. The problem of communication, iInformation theory beyond communication [slides] 


8/30 
2. The idea of errorcontrol coding and linear codes [slides] [handwritten] 


9/4  3. Information measures and their axiomatic derivation 



4. Basic inequalities with information measures 


9/11  5. Asymptotic Equipartition Property 



9/13  6. Source Coding Theorem 



9/18  7. Variablelength Codes 


9/20  8. Entropy Rate of Stochastic Processes 


9/25  9. Distributed Source Coding 


9/27  10. Universal Source Coding 



10/2  11. Method of Types 


10/4  12. Allerton Conference [no lecture]  
10/9  13. Hypothesis Testing 


10/11  14. Channel Coding Theorem: Converse and Joint AEP 



10/16  15. Channel Coding Theorem: Achievability and Examples 


10/18  16. Midterm [no lecture]  
10/23  17. SourceChannel Separation 


10/25  18. Differential Entropy, Maximum Entropy, and Capacity of RealValued Channels 


10/30  19. RateDistortion Theorem: Converse and Examples 



11/1  20. RateDistortion Theorem: Achievability and More Examples 


11/6  21. Quantization Theory 


11/8  22. BlahutArimoto 


11/13  23. Strong Data Processing Inequalities 


11/15  24. Large Deviations 


11/27  25. Error Exponents for Channel Coding 


11/29  26. Error Exponents for Channel Coding 


12/4  27. Multiple Access Channel: Achievability 


12/6  28. Quantum Information Theory [guest lecture]  
12/11  29. Multiple Access Channel: Converse, Examples, and Duality 
