ECE 563 - Information Theory (Fall 2018)

Lecturer: Lav Varshney (office hours, Friday 9:30-11:00am, 314 CSL and by appointment)

Teaching Assistants: Ravi Kiran Raman (office hours, Tuesday 4:00-5:00pm, 3036 ECE) and Sam Spencer (office hours, Thursday 2:30-3:30pm, 114 CSL)

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

Problem Solving Sessions: Friday, 2:00pm, 141 Coordinated Science Laboratory [optional]

Course Goals

• Learn how to establish the fundamental limits and optimal designs for communication systems, including the basic conceptual idea of coding.
• Develop skills in mathematical abstraction of engineering and natural systems, so as to define closed deductive systems within which to prove theorems.
• Attain facility with mathematical tools from information theory that may be broadly applicable.
• Gain confidence in using information-theoretic approaches for problems beyond communication, e.g. in learning, computing, biology, 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 [including programming assignments] (25%), Midterm exam [in class] (25%), Final exam [as designated by university] (25%), Group juxtaposition paper [in groups of three, in roughly Allerton format] (25%)

Homework

Problem Solving Sessions

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