﻿

ECE1502 Information Theory (Fall 2020)

Instructor:

·      Prof. Wei Yu < weiyu@ece.utoronto.ca >

Teaching Assistant:

·      Reza Farsani < reza.farsani@utoronto.ca >

Lectures: (starting Sept 10)

·      Lectures are recorded asynchronously

·      Class discussions are held synchronously on Thursdays 9:30-11:00

·      TA discussions are held synchronously on Mondays 9:30-11:00

Synchronous sessions are on Zoom. Asynchronous lectures are available by streaming.

No lectures/tutorials during Fall study break: Nov 9-13. Last day of the session: Dec 9.

Course Description:

Information theory answers two fundamental questions in communication theory: what is the ultimate limit of data compression (answer: the entropy H), and what is the ultimate limit of transmission rate of communication (answer: the channel capacity C)  - Cover & Thomas

This course is a one-term introduction to information theory at a first-year graduate level. The aim is to provide a comprehensive coverage of the following major areas of information theory:

•          Entropy and mutual information

•          Data compression

•          Channel capacity

This is a fundamental course for students interested in digital communications, data compression and signal processing. It is also of interests to students in Computer Science, Statistics and related disciplines.

Pre-requisite: An undergraduate course in Probability. A fair level of mathematical maturity is expected.

Textbook: Elements of Information Theory

by Thomas M. Cover and Joy A. Thomas, John Wiley, 2nd Edition, 2006.

Course Schedule:

 Date Class discussion Text References TA discussion Sept 10 Introduction Ch. 1.1 Sept 14 Probability refresher Sept 17 Entropy. Joint Entropy. Relative Entropy. Ch. 2.1-2.3 Sept 21 HW #1 Sept 24 Mutual Information. Jensen's inequality. Conditional Entropy. Conditional Mutual Information. Data Processing Inequality. Entropy Rate of Stochastic Process Ch. 2.5-2.6, 2.8 Ch. 4.1-4.2 Sept 28 HW #1 Oct 1 Asymptotic Equipartition Property (AEP) Ch. 3 Oct 5 HW #2 Oct 8 Data Compression, Kraft’s Inequality, Shannon Code, Huffman Code Ch. 5.1-5.9 Oct 12 -- Oct 15 Arithmetic Code, Lempel-Ziv Code. Ch. 13.3-13.4 Oct 19 HW #2 Oct 22 Gambling on Horse Races. Ch. 6.1-7.3 Oct 26 Midterm Oct 29 Discrete Memoryless Channel, Channel Capacity Theorem. Ch. 7.1-7.5 Nov 2 HW #3 Nov 5 Joint Typicality. Achievability Proof. Converse of the Channel Capacity Theorem. Fano's Inequality. Ch. 7.6-7.7, 7.9-7.10, 7.13 Nov 9-13 Fall study break Nov 16 HW #3 Nov 19 Source Channel Separation. Differential Entropy. Gaussian Channel Ch. 7.13, 8.1-8.6 Nov 23 HW #4 Nov 26 Maximum Entropy Distribution. Discrete-Time Gaussian Channel Ch. 12.1-12.2 Ch. 9.1-9.2 Nov 30 HW #4 Dec 3 Gaussian Vector Channels. Water-filling. Band-limited Gaussian Channel. Complex Gaussian Channels. Ch. 9.3-9.5 Dec 7 Multiple-Access Channel. Rate-Distortion Theory. Ch. 15.1-15.3, 10.1-10.5 HW #5 Dec 17 Final Exam --

·      Midterm: 35%

·      Final Exam: 65%. All exams are open-book, take-home exams.

References:

C. E. Shannon: A mathematical Theory of Communications, Bell System Tech. J., vol 27:379-423, 623-656, 1948

R. G. Gallager: Information Theory and Reliable Communications, John Wiley, 1968

I. Csiszár and J. Körner: Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic Press, New York, 1981

Review articles in IEEE Transactions on Information Theory vol. 44, 1998.