ECE-5973/TCOM-5970: Information Theory
Prerequisites: ECE 4523 or instructor permission
This is a graduate introductory course in information theory targeted to graduate and senior students. The goal is to both inspire students with the thought-provoking ideas of information theory and provide them enough knowledge necessary for further study of the subject.
Course Outline (tentative):
- Overview (1 lecture)
- Review of probability theory (1 week)
- Lossless source coding theory, Huffmann coding, and introduction to Arithmetic coding (1 week)
- Asymptotic equipartition property (AEP), typicality and joint typicality (1 week)
- Entropy, conditional entropy, mutual information, and their properties (2 weeks)
- Introducing project (1 lecture)
- Channel coding theory, capacity, and Fano’s inequality (1 week).
- Continuous random variables, differential entropy, Gaussian source, and Gaussian channel (1 week)
- Bandlimited AWGN channel, parallel Gaussian channels, waterfilling and inverse waterfilling (1 week)
- Error correcting codes, linear codes, and introduction to low-density parity check code (1 week)
- Lossy source coding theory and rate-distortion function (1 week)
- Duality of source and channel coding, separation theorem (1 lecture)
- Computation of capacity and rate-distortion function (1 week)
- Method of type, large deviation theory (1 week)
Textbook
“Elements of Information Theory,” by Cover and Thomas, New York: Wiley.
Second edition is a bit better. But 1st edition is okay too, given that it is way cheaper in Amazon. You probably can get one below 20 bucks.
Auxiliary and Reference Material:
- Shannon, C. E. (1948) A mathematical theory of communication. Bell Sys. Tech. J. 27: 379-423, 623-656.
- “Information Theory, Inference, and Learning Algorithms,” by David J.C. Mackay, Cambridge: Cambridge University Press.
- “A First Course in Information Theory,” by Raymond W. Yeung, New York: Springer.
- “Information Theory and Reliable Communication,” by R. Gallager, New York: Wiley.
- “Information Theory,” by Csiszar and Korner, New York: Academic Press.
- “Entropy and Information Theory,” by R. M. Gray, Springer-Verlag, 1990.
- “Probability, Random Processes, and Ergodic Properties,” by R. M. Gray, Springer-Verlag, 1988.
- Information Theoretic Inequality Prover
Grading
Quiz 1 (15%)
Quiz 2 (15%)
Quiz 3 (15%)
Homework (25%)
Project/case study (30%)
The project means to give students a chance to dig deeper into a particular topic of interest. Potential projects include studying the application and relation of information theory to other disciplines such as statistics, bioinformatics, economics, and physics. Project report is due on December 14 (firm deadline!). Please email me directly your report. I'll send back acknowledgement email to every of you. Please don't hesitate to bug me if you don't receive an acknowledgement.
Late Policy
Late assignment is generally subjected to 20% penalty per day.Calendar
| Summary | Course notes | Other materials | |
| 8-21-2007 | Overview | 01 overview.pdf | |
| 8-23-2007 | Review of probability theory | 02 probability.pdf | |
| 8-28-2007 | Constrained optimization | 02a optimization.pdf | hw1.pdf due 9/4 |
| 8-30-2007 | Kraft inequality | 03 lossless source coding.pdf | |
| 9-4-2007 | Compression and entropy | hw2.html due 9/11 | |
| 9-6-2007 | Huffmann coding, Shannon-Fano-Elias Coding, Arithmetic Coding; AEP | 04 AEP.pdf | hw1soln.pdf |
| 9-11-2007 | Properties of entropy, relative entropy, conditional entropy, mutual information | 05 information measures.pdf | hw3.html due 9/20 |
| 9-13-2007 | Conditional mutual information, chain rule | hw2soln.pdf | |
| 9-18-2007 | No class due to conference | ||
| 9-20-2007 | Sufficient statistics, entropy rate | 05a hidden markov model.pdf | hw4.html due 9/27, hw3soln.pdf |
| 9-25-2007 | Random walk on graph, hidden Markov model | project plan due 10/4 | |
| 9-27-2007 | Quiz 1 | ||
| 10-2-2007 | Quiz 1 review | quiz1soln.pdf, hw4soln.pdf | |
| 10-4-2007 | Channel coding theorem | 06 channel coding theorem.pdf | hw5.html due 10/11 |
| 10-9-2007 | Channel coding theorem (con't) | ||
| 10-11-2007 | Differential entropy | 07 differential entropy.pdf | hw6.html due 10/18 |
| 10-16-2007 | Differential entropy (con't) | hw5soln.pdf | |
| 10-18-2007 | Gaussian channel, waterfilling for parallel Gaussian channel | 08 gaussian channel.pdf (08 Gaussian channel.rar) | hw7.html due 10/25 |
| 10-23-2007 | Error correcting codes | 09 error correcting codes.pdf (09 error correcting codes.rar) | hw6soln.pdf |
| 10-25-2007 | LDPC codes | hw8.html due 11/1 | |
| 10-30-2007 | Rate distortion functions | 10 rate distortion function.pdf (10 rate distortion function.rar) | hw7soln.pdf |
| 11-1-2007 | Revision | hw9.html due 11/13 | |
| 11-6-2007 | Quiz 2 | hw8soln.pdf | |
| 11-8-2007 | Proof of rate distortion theorem | ||
| 11-13-2007 | Convexity properties of mutual information and entropy | 11 capacity and rate distortion function computation.pdf (11 capacity and rate-distortion computation.rar) | hw10.html due 11/27, quiz2soln.pdf |
| 11-15-2007 | Computation of capacity | ||
| 11-20-2007 | Separation theorem and duality | 12 separation theorem and duality.pdf (12 separation theorem and duality.rar) | |
| 11-22-2007 | Thansgiving | hw9soln.pdf | |
| 11-27-2007 | Method of Type | 13 the method of type.pdf (13 the method of type.rar) | hw11.html due 12/4 |
11-29-2007 |
Universal source coding | 14 universal source coding.pdf (14 universal source coding.rar), 15 large deviation theory.pdf (15 large deviation theory.rar) | hw10soln.pdf (HW10 codes.rar) |
12-4-2007 |
Large deviation theory | hw11soln.pdf | |
12-6-2007 |
Quiz 3 | quiz3soln.pdf |
On request of some of you, lecture notes 1-7 are now available in Windows Journal Viewer format.