ECE563

ECE 563 - Information Theory (Fall 2019)

Lecturer: Olgica Milenkovic (Office hours: Thursday 3:30-5:00pm, 313 CSL or by appointment as needed)

Teaching Assistants: Pattabiraman, Srilakshmi (Office hours, Tuesday 3:00-4:00pm, 3036 ECE; sp16@illinois.edu)

Lectures: Tuesday and Thursday, 12:30pm, 2015 Electrical and Computer Engineering Building

Problem Solving Sessions: The sessions will start on September 13th, 2019 Friday, 2:00pm, 141 Coordinated Science Laboratory [optional]

Course Objectives:

To learn about various forms of entropy and generalizations thereof, and their operational interpretations/characterizations.
To understand how one characterizes 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 [in class] (25%), Final exam [at a date determined by the university] (25%), Group project/paper (25%)

Midterm I: October 24th, 6pm, Room 2017

Midterm I Review: October 22nd, 5:00-6:30pm, Room 2017

Project Presentations: December 6th, 12:00 noon - 5:00pm, Room 311 CSL

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 Text

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

Homeworks, Fall 2019

Homework 1 (issued September 11th, due September 19th in class)
- Solutions

Homework 2 (issued September 21th, due October 1st in class)
- Solutions

Homework 3 (issued October 3rd, due October 15st in class)
- Solutions

Homework 4 (issued October 17th, due October 23rd by noon, 311 CSL)
- Solutions

Homework 5 (issued October 30th, due November 12th in class)
- Solutions

Homework 6 (issued November 17th, due December 2nd in class)
- Solutions

Homework 7 (issued December 3th, due December 12th, CSL 311)
- Solutions

Problem Solving Sessions, Fall 2019

Session 1
Session 2
Session 3
Session 4
Session 5
Session 6
Session 7

Homeworks, Fall 2018 with Solutions

Homework 0 (released August 28, due August 30 in class)
Homework 1 (released September 4, due September 13 in class) [solutions]
Homework 2 (released September 13, due September 25 in class) [solutions]
Homework 3 (released September 25, due October 9 in class) [solutions]
Homework 4 (released October 9, due October 16 in class) [solutions]
Homework 5 (released October 30, due November 8 in class) [solutions]
Homework 6 (released November 15, due December 4 in class) [solutions]
Homework 7 (released December 4, due December 11 in class) [solutions]

Problem Solving Sessions, Fall 2018

Session 1 (Aug. 31)
Session 2 (Sep. 7)
Session 3 (Sep. 14)
Session 4 (Sep. 21)
Session 5 (Sep. 28)
Session 6 (Oct. 5)
Session 7 (Oct. 12)

Exams

Exam 1 (midterm) - Thursday, October 18 in class (try to be on time) [solutions]
Exam 2 (final) - Monday, December 17 at 8:00am in 2015 ECEB

Juxtaposition Paper

[guidelines] [feedback form]

Course Schedule

Date	Topic	Reading Assignment	Learning Objectives	Multimedia Supplements
8/28	1. The problem of communication, information 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

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