ECE563

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

Syllabus, Syllabus Attachment

Homework

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

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