PDF (Handout)

=====================

EE 595: Spring 2003: Information Theory (Part I)

Course Pre-requisites: EE 505 and familiarity with basic concepts of probability.

Course Outline:
This course will serve as the first among the sequence of two courses in the area of Information Theory. 

The first part of the first course will introduce the ideal of uncertainty, which is a useful measure in studying the data compression and deriving the results related to compression. Compressing data naturally leads to the need for coding strategies that can represent the data in the most efficient way. This problem is studied in the context of optimal coding and the notion of optimality is introduced. The folk wisdom of twenty questions is brought back in this context and related to the Shannon-Fano-Elias coding. We will also deal with the correlated sources in which case the Slepian-Wolf Lemma provides the main result for compression.

The second part of the first course will deal with the results that relate to the communication channel and the rate of transmission in a given noisy channels. In particular, we shall derive the result dealing with the capacity of the channel followed by the rate distortion theory followed by the network information theory. Gaussian channel will be of special interest to us. Course wraps up with the joint source-channel results.

Course Syllabus:
The course will closely follow the textbook, which is excellent at the introductory level. The topics to be covered in this course in the order in which they appear in the text are:
1. Definition of entropy, relative entropy and mutual information. Relevant inequalities such as log sum; Jensen's; Data processing; Fano's;
2. Concept of typical sets and asymptotic equi-partition set.
3. Entropy rates and examples.
4. Data Compression: Kraft inequality; optimal codes; Bounds on optimal codes; Specific codes -- Huffman, Shannon Fano Elias; Optimality of Huffman codes; Arithmetic Codes.
5. Channel Capacity: Definition, derivation of the result and the converse.
6. The capacity of Gaussian Channel including the colored noise case.
7. Rate Distortion Theory. 
8. Network Information Theory: The multiple access channels; Application of Slepian-Wolf Lemma for multiple access channels.

Grading:  

• Homework Assignments - 30%
• Midterm - 30%
• Final - 40%

Required Text: Elements of Information Theory
Authors: Cover and Thomas
Publisher: Wiley-Interscience
Year: 1991

References:

• Information Theory: Coding Theorems for Discrete Memoryless Systems by Imre Csiszar, Janos Korner, Publisher: Akademiai Kiado; 2nd edition (December 1997). Comments: Abstract and thorough; 
• Information Theory by Robert B. Ash, Publisher: Dover Publications; (December 1990). Comments: A classic, clear introduction. A bargain in the Dover reprint.
• Information Theory and Statistics by Solomon Kullback, Publisher: Dover Publications (July 1997).
• Information Theory and Reliable Communication by Robert G. Gallager, Publisher: John Wiley & Sons (1968). A beautifully written, rigorous treatment of Shannon theory.
• Principles and Practice of Information Theory by Blahut, R., Publisher: Addison-Wesley (June 1987)
• Rate Distortion Theory: A Mathematical Basis for Data Compression by T. Berger, Publisher: Prentice-Hall (1971).