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:

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

 

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 (20%)
Quiz 2 (20%)
Homework (30%)
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.

Late Policy

You'll have 5 day "late credits". You can use these five days for any assignment. After all five days are used up, late assignment will be subjected to 20% penalty per day on the overall score of the late assignment. Please note that holiday counts as well.

Calendar

  Summary Course notes Homework Reference
8-25-2009 Overview; Review of probability theory 01 overview.rar, 02 probability.rar    
8-28-2009 Review of optimization; Lossless source coding 02a optimization.rar, 03 lossless source coding.rar hw1.html; hw1soln.pdf  
9-1-2009 Kraft Inequality      
9-4-2009 Minimum compressible length of a random source      
9-8-2009 Shannon-Fano-Elias Code    
9-11-2009 Arithmetic coding arithmetic encoding, arithmetic decoding hw2.html; hw2soln.pdf [WittenNC'87]
9-15-2009 Distributed arithmetic coding; AEP 04 AEP.rar,ac.pdf   [GrangettoMO'07]
9-18-2009 Information measures 05 information measures.rar  
9-22-2009 Chain rules; Data processing inequality 05a hidden markov model.rar    
9-25-2009 Entropy rate   hw3.html; hw3soln.pdf  
9-29-2009 Random walk on graph      
10-2-2009 Gambling and information theory 05c gambling.pdf hw4.html; hw4soln.pdf  
10-6-2009 Dutch book; Conservation theorem; Entropy of English      
10-9-2009 Binary symmetric channel; Channel coding theorem 06 channel coding theorm.rar    
10-13-2009 Forward proof of channel coding theorem; Fano's inequality      
10-16-2009 Converse proof of channel coding theorem      
10-20-2009 Differential entropy 07 differential entropy.rar    
10-23-2009 Quiz 1      
10-27-2009 Typical sequences for continuous sources 08 Gaussian channel.rar    
10-30-2009 Gaussian channel; Waterfilling; Syndrome decoding 09 error correcting codes.rar hw5.html channel coding chapter
11-3-2009 Hamming codes; Convolutional codes; Viterbi algorithm 09a convolutional codes.rar    
11-6-2009 Belief propagation algorithm 09b belief propagation algorithm.rar hw6.html  
11-10-2009 LDPC docoding using belief propagation      
11-13-2009 LDPC decoding (con't); soft decoding of convolutional codes      
11-17-2009 Linear algebra review math.pdf    
11-20-2009        
11-24-2009        
11-27-2009        

12-1-2009

        

12-4-2009

        

12-8-2009

        

Some lecture notes are available in Windows Journal Viewer format.