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%)

Entropy in Physics

Operational Characterization of Entropy

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

Homeworks, Fall 2019

• Homework 1 (issued September 11th, due September 19th in class)
• Homework 2 (issued September 21th, due October 1st in class)

Homeworks, Fall 2018 with Solutions

Problem Solving Sessions, Fall 2018

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

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 8/30 2. The idea of error-control coding and linear codes [slides] [handwritten] Chapter 7.11 (Hamming Codes) of Cover & Thomas 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" Federico Echenique and  Roland G. Fryer, Jr., "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 9/11 5. Asymptotic Equipartition Property Chapter 3.1 of Cover & Thomas 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 Raymond Yeung, "Source Coding Theorem" 9/18 7. Variable-length Codes Chapter 5 of Cover & Thomas 9/20 8. Entropy Rate of Stochastic Processes Chapter 4 of Cover & Thomas 9/25 9. Distributed Source Coding Chapter 15.4 of Cover & Thomas 9/27 10. Universal Source Coding Chapter 13 of Cover & Thomas David Brailsford, "Elegant Compression in Text (The LZ77 Method)" 10/2 11. Method of Types Chapter 11.1-11.3 of Cover & Thomas 10/4 12. Allerton Conference [no lecture] 10/9 13. Hypothesis Testing Chapter 11.7-11.10 of Cover & Thomas 10/11 14. Channel Coding Theorem: Converse and Joint AEP Chapter 7.9 and 7.6 of Cover & Thomas Brit Cruise 10/16 15. Channel Coding Theorem: Achievability and Examples Chapter 7.7 and 7.1 of Cover & Thomas 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) 10/25 18. Differential Entropy, Maximum Entropy, and Capacity of Real-Valued Channels Chapter 8, 9, and 12 of Cover & Thomas 10/30 19. Rate-Distortion Theorem: Converse and Examples Chapter 10 of Cover & Thomas 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) 11/6 21. Quantization Theory Chapters 5 and 6 of Gersho & Gray 11/8 22. Blahut-Arimoto Chapter 10.8 of Cover & Thomas (and Chapter 10 of Yeung) 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. 11/15 24. Large Deviations Chapter 11.4-11.5 of Cover & Thomas 11/27 25. Error Exponents for Channel Coding Chapter 5.6 of Blahut 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" 12/4 27. Multiple Access Channel: Achievability Chapter 15.3 of Cover & Thomas 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