ECE563

ECE 563 - Information Theory (Fall 2022)

Lecturer: Olgica Milenkovic (Office hours: Tuesday 3:00-4:00pm, 311 CSL or by appointment as needed)

Teaching Assistants: Rebecca Golm (Office hours: Wednesday 2:00-3: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:30pm-4:30pm, ECEB 2015

Course Objectives:

To learn about various forms of entropy and generalizations thereof, and their operational interpretations/characterizations.
To understand how one can characterize the fundamental performance limits of diverse communication systems.
To learn about various concepts in coding theory.
To explore connections between information theory and statistics, machine learning.
To learn about emerging applications of information theory in learning, computing, biology, quantum theory and social sciences.

Catalog Description

Mathematical models for channels and sources; entropy, information, data compression, channel capacity, Shannon's theorems, and rate-distortion 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:00pm-7:00pm, October 21st, 2022 in ECEB 2015 (25%), Final exam: 8:00am-11:00am, Tuesday Dec. 13, 2022 (25%), Group project/paper (25%)

Midterm I: 5:00pm-7:00pm, October 21st, 2022 in ECEB 2015

Project Presentations: December 12th, 2022 starting at noon in CSL141. Presentation Schedule

Join Zoom Meeting: https://illinois.zoom.us/j/82460945685?pwd=SE1Nc3dyanFCckVpTkVXdWdZSFg0dz09

Final Exam: 8:00am-11:00am, Tuesday Dec. 13, 2022, Location: TBD

Syllabus

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 DNA-Storage Channels Research paper

Polar codes Research paper

Network coding Text

Quantum information theory Introduction

Renyi entropy NeurIPS paper

Deletion error-correction and capacity of deletion channels Review paper by Sloane

Channel dispersion: finite block-length 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. 5-12. More on axiomatic approaches can be found here Entropy axioms

Lecture subjects, Fall 2022

1. Tuesday, August 23rd: Introduction, Syllabus Overview, How to measure information in physics, engineering, communication theory and biology

Lecture Slides, August 23, 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, Kulback-Leibler divergence, Mutual information

Lecture Slides, August 30, 2022

4. Thursday, September 1st: Problem solving session

Recitation Slides, Sept. 1, 2022

5. Tuesday, September 6th: Data processing inequality, Jensen's inequality, the Log-sum inequality, Fano's inequality

6. Thursday, September 8th: Typical sequences and the asymptotic equipartition property, compressing typical sequences

7. Tuesday, September 13th: Data compression - uniquely decodable codes, prefix codes, Kraft's inequality for prefix and uniquely decodable code, bounds on optimal code-length

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

Adaptive Huffman reference

11. Tuesday, September 27th: Data compression - Adaptive Huffman codes continued

12. Thursday, September 29th: Data compression - Tunstall codes, Runlength codes

Tunstall codes reference

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 error-correction codes - Hamming codes, parity-check matrices, minimum Hamming distance of codes, linear codes

18. Thursday, October 20th: Practical error-correction codes - Dual codes, sphere-packing bound, Singleton bound, introduction to finite fields

Finite Fields Reference

19. Tuesday, October 25th: Practical error-correction codes - Constructions of finite fields, irreducible and primitive polynomials and elements, BCH and RS code

BCH and RS codes Reference

20. Thursday, October 27th: Practical error-correction codes - Regular and irregular LDPC codes, the peeling decoder for BECs, stopping sets, belief propagation decoding for the BSC

21. Tuesday, November 1st: LDPC codes Reference

Tuesday, November 1st: Polar codes - Reference by Prof. Henry Pfister

22. Thursday, November 3rd: Feedback capacity, source-channel coding separation theorem

23. Tuesday, November 8th: No lecture, election day

24. Thursday, November 10th: Differential entropy

25. Tuesday, November 15th: Additive Gaussian noise channels and their capacity, parallel Gaussian channels and waterfilling arguments

26. Thursday, November 17th: MSE distortion, scalar quantization, optimal uniform scalar quantizers

27. Tuesday, November 22nd: Thanksgiving break

28. Thursday, November 24th: Thanksgiving break

29. Tuesday, November 29th: Nonuniform scalar quantization and Benett's integral, Rate-distortion theory

Homework, Fall 2022

Homework 1 (solutions) (issued September 6th, due September 15th in class)
Homework 2 (solutions) (issued September 18th, due September 29th on Gradescope)
Homework 3 (solutions) (issued October 4th, due October 18th on Gradescope)
Homework 4 (solutions) (issued October 28th, due November 10th on Gradescope)
Homework 5 (solutions) (issued November 14th, due November 26th on Gradescope)
Homework 6 (solutions) (issued November 29th, due December 12th on Gradescope)

Problem Solving Sessions, Fall 2019

Recitations, Fall 2022

Session 1: September 1st, 2022
Session 2: September 7th, 2022
Session 3: September 14th, 2022
Session 4: September 21st, 2022
Session 5: September 28th, 2022 (Thomas and Cover 4.1-4.3)
Session 6: October 5th, 2022
Session 7: October 12th, 2022
Session 8: October 19th, 2022
Session 9: October 26th, 2022: Guest Lecture by Prof. Emina Soljanin
Session 10: November 2nd, 2022
Session 11: November 9th, 2022
Session 11: November 30th, 2022, JPEG Compression

Topics:

The problem of communication / information theory beyond communications
The idea of coding
Information measures and their properties
Concentration of measure, asymptotic equipartition property, and source coding theorem
Variable-length and universal source coding
Entropy rates for stochastic processes
Slepian-Wolf theorem
Noisy channel coding theorem
Source-channel separation
Continuous-valued channels
Strong data processing inequalities and applications
Large deviations and error exponents
Quantization theory
Rate-distortion theory
Blahut-Arimoto algorithm
Multiple-access and two-way channels

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]	Chapter 1 (Introduction and Preview) of Cover & Thomas	objective	The Shannon Centennial: 1100100 years of bits
8/30	2. The idea of error-control coding and linear codes [slides] [handwritten]	Chapter 7.11 (Hamming Codes) of Cover & Thomas	objective	Brit Cruise, "Information Theory part 14: Error correction codes (Hamming coding)"
9/4	3. Information measures and their axiomatic derivation	Chapter 2.1-2.3 (Entropy, Relative Entropy and Mutual Information) of Cover & Thomas T. Berger, "An Axiomatic Derivation of the Information Measure"	objective	*Federico Echenique and Roland G. Fryer, Jr., "A Measure of Segregation Based on Social Interactions," The Quarterly Journal of Economics, vol. 122, May 2007, pp. 441–485.*
	4. Basic inequalities with information measures	Chapter 2.4-2.10 (Entropy, Relative Entropy and Mutual Information) of Cover & Thomas	objective
9/11	5. Asymptotic Equipartition Property	Chapter 3.1 of Cover & Thomas	objective	*L. D. Goodfellow, "A psychological interpretation of the results of the Zenith radio experiments in telepathy," Journal of Experimental Psychology,* 23(6), 601-632, 1938. Raymond Yeung, "Weak Typicality"**
9/13	6. Source Coding Theorem	Chapter 3.2 of Cover & Thomas Chapter 5.2 of Yeung, if you'd like	objective	Raymond Yeung, "Source Coding Theorem"
9/18	7. Variable-length Codes	Chapter 5 of Cover & Thomas	objective	Brit Cruise, "Information Theory part 13: Data Compression via Huffman Coding"
9/20	8. Entropy Rate of Stochastic Processes	Chapter 4 of Cover & Thomas	objective
9/25	9. Distributed Source Coding	Chapter 15.4 of Cover & Thomas	objective
9/27	10. Universal Source Coding	Chapter 13 of Cover & Thomas	objective	David Brailsford, "Elegant Compression in Text (The LZ77 Method)"
10/2	11. Method of Types	Chapter 11.1-11.3 of Cover & Thomas	objective
10/4	12. Allerton Conference [no lecture]		objective
10/9	13. Hypothesis Testing	Chapter 11.7-11.10 of Cover & Thomas	objective
10/11	14. Channel Coding Theorem: Converse and Joint AEP	Chapter 7.9 and 7.6 of Cover & Thomas	objective	Brit Cruise, "Information Theory part 8: Channel capacity"
10/16	15. Channel Coding Theorem: Achievability and Examples	Chapter 7.7 and 7.1 of Cover & Thomas	objective
10/18	16. Midterm [no lecture]
10/23	17. Source-Channel Separation	Chapter 7.13 of Cover & Thomas (and e.g. Gastpar et al., 2003)	objective
10/25	18. Differential Entropy, Maximum Entropy, and Capacity of Real-Valued Channels	Chapter 8, 9, and 12 of Cover & Thomas	objective
10/30	19. Rate-Distortion Theorem: Converse and Examples	Chapter 10 of Cover & Thomas	objective	Claude Shannon, "Scientific Aspects of Juggling" Jordana Cepelewicz, "Overtaxed Working Memory Knocks the Brain Out of Sync" "This duality can be pursued further and is related to a duality between past and future and notions of control and knowledge. Thus we may have knowledge of the past but cannot control it; we may control the future but have no knowledge of it." - Shannon (1959)
11/1	20. Rate-Distortion Theorem: Achievability and More Examples	Chapter 10 of Cover & Thomas (and Chapter 9 of Yeung)	objective
11/6	21. Quantization Theory	Chapters 5 and 6 of Gersho & Gray	objective
11/8	22. Blahut-Arimoto	Chapter 10.8 of Cover & Thomas (and Chapter 10 of Yeung)	objective
11/13	23. Strong Data Processing Inequalities	W. S. Evans and L. J. Schulman, "Signal Propagation and Noisy Circuits," 1999. Y. Polyanskiy and Y. Wu, "Strong Data-Processing Inequalities for Channels and Bayesian Networks," 2017.	objective
11/15	24. Large Deviations	Chapter 11.4-11.5 of Cover & Thomas	objective
11/27	25. Error Exponents for Channel Coding	Chapter 5.6 of Blahut	objective
11/29	26. Error Exponents for Channel Coding	Chapter 5.7 of Blahut G. D. Forney, Jr., "On Exponential Error Bounds for Random Codes on the BSC"	objective
12/4	27. Multiple Access Channel: Achievability	Chapter 15.3 of Cover & Thomas	objective
12/6	28. Quantum Information Theory [guest lecture]
12/11	29. Multiple Access Channel: Converse, Examples, and Duality	Chapter 15.3 and 15.5 of Cover & Thomas