picture of campanile reflected in window

picture of campanile reflected in window

Home
Research
Teaching
Biography
Publications
Links

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

  1. Overview (1 lecture)
  2. Review of probability theory (1 week)
  3. Lossless source coding theory, Huffmann coding, and introduction to Arithmetic coding (1 week)
  4. Asymptotic equipartition property (AEP), typicality and joint typicality (1 week)
  5. Entropy, conditional entropy, mutual information, and their properties (2 weeks)
  6. Introducing project (1 lecture)
  7. Channel coding theory, capacity, and Fano’s inequality (1 week).
  8. Continuous random variables, differential entropy, Gaussian source, and Gaussian channel (1 week)
  9. Bandlimited AWGN channel, parallel Gaussian channels, waterfilling and inverse waterfilling (1 week)
  10. Error correcting codes, linear codes, and introduction to low-density parity check code (1 week)
  11. Digital fountain, luby code, raptor code (1 lecture)
  12. Lossy source coding theory and rate-distortion function (1 week)
  13. Duality of source and channel coding, separation theorem (1 lecture)
  14. Method of type, large deviation theory, maximum entropy (1 week)
  15. Network information theory (1 week)

Topics not covered (finally):

  1. Network information theory (only covered Slepian-Wolf coding)
  2. Digital fountain, luby and raptor codes
  3. Capacity computation
  4. Separation theorem and duality
  5. Method of type

Other Topics covered but not planned:

  1. Slepian-Wolf coding
  2. Density evolution for LDPC code design
  3. Convolutional codes, trellis coded modulations
  4. Factor graphs and message passing algorithms
  5. Belief propagation and Bethe approximation
  6. Generalized belief propagation

Textbook

“Elements of Information Theory,” by Cover and Thomas, New York: Wiley.

Second edition is quite 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.
  • "Law of Large Number," by Terry Tao.
  •  “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.
  • J. S. Yedidia, W. T. Freeman, and Y. Weiss, "Understanding Belief Propagation and its Generalizations," in Exploring Artificial Intelligence in the New Millennium: Science and Technology Books, 2003.
  • P. A. Chou and Y. Wu, "Network Coding for the Internet and Wireless Networks," Signal Processing Magazine, IEEE, vol. 24, pp. 77-85, 2007.
  • S. Katti, S. Shintre, S. Jaggi, D. Katabi, and M. Medard, "Real Network Codes," in Allerton, 2007.
  • D. J. C. MacKay, "Fountain codes," IEE Communications, vol. 152, pp. 1062-1068, 2005.
  • S. Verdu, "Fifty years of Shannon theory," Information Theory, IEEE Transactions on, vol. 44, pp. 2057-2078, 1998.
  • A. R. Calderbank, "The art of signaling: fifty years of coding theory," Information Theory, IEEE Transactions on, vol. 44, pp. 2561-2595, 1998.
  • I. Csiszar, "The method of types [information theory]," Information Theory, IEEE Transactions on, vol. 44, pp. 2505-2523, 1998.
  • Information Theoretic Inequality Prover

Grading

Quiz 1 (15%)
Quiz 2 (15%)
Quiz 3 (15%)
Homework (25%)
Report (10%)
Project/case study (20%)

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.

Report

You can choose from this list or suggest your own (need to get prior approval at least a week before due date). You should try to understand as much detail as possible. Summarize the paper with your own words. You would like to write it with the usual journal paper format. The report is roughly graded based on understanding (how much understanding you show) , writing (how concise and precise) and coverage (whether you can include the whole paper or maybe even extend beyond it).

Late Policy

Late assignment may be subjected to 20% penalty per day.

Calendar

  Summary Course notes
8-26-2008 Overview 01 overview.rar
8-28-2008 Review of probability theory 02 probability.rar
9-2-2008 Constrained optimization 02a optimization.rar
9-4-2008 Kraft inequality 03 lossless source coding.rar
9-9-2008 Huffmann coding  
9-11-2008 Shannon-Fano-Elias Coding, Arithmetic coding; AEP 04 AEP.rar
9-16-2008 Properties of entropy, relative entropy, conditional entropy, mutual information 05 information measures.rar
9-18-2008 Conditional mutual information, chain rule
9-23-2008 Sufficient statistics, entropy rate  
9-25-2008 Random walk on graph, hidden Markov model 05a hidden markov model.rar
9-30-2008 Revision  
10-2-2008 Quiz 1  
10-7-2008 Lossless source coding with side information  
10-9-2008 Slepian-Wolf coding 05b Slepian-Wolf coding.rar
10-14-2008 Channel coding theorem 06 channel coding theorm.rar
10-16-2008 Converse of channel coding theorem
10-21-2008 Channels with feedback 06a Feedback channel.rar
10-23-2008 Differential entropy 07 differential entropy.rar
10-28-2008 Gaussian channel 08 Gaussian channel.rar
10-30-2008 Waterfilling for parallel Gaussian channel
11-4-2008 Convolutional codes; Trellis coded modulation 09 error correcting codes.rar; 09a convolutional codes.rar
11-6-2008 Block codes; LDPC codes  
11-11-2008 Message passing decoding 09b belief propagation algorithm.rar
11-13-2008 Quiz 2
11-14-2008 Belief propagation and Bethe approximation (makeup class) 09c BP and Bethe approximation.pdf
11-18-2008 Generalized belief propagation 09d Generalized Belief Propagation.pdf
11-20-2008 Rate distortion functions 10 rate distortion function.rar
11-25-2008 LDPC code design using density evolution  
11-27-2008 Thansgiving  

12-2-2008

 ISVC (no class)  

12-4-2008

 Entropy maximization principle; Quiz 3 due  

12-11-2008

 Project presentations  

Lecture notes are now available in Windows Journal Viewer format for better quality.