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 |
|
-- |
Grades:
· 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.