Introduction to Information Theory

 

 

Fall 2008:  ECE 2422

Course Number 34656

Period: 08/25/08-12/13/08

 

Prof. Heung-No Lee

Office: 437 Benedum Hall

Campus Phone: 412-624-9677

E-mail: hnlee@pitt.edu

Office Hours:  Monday 11:00am – 12:00pm, Wed 11:00am – 12:00pm, or by making appointment via e-mail.

  

Class meets at 5:20pm - 7:50pm every Tuesday, BEH 522.

 

Co-requisite: Introductory courses on stochastic processes, random variables and probability (e.g. ECE2521, offered this semester on Thursday, from 5:20 to 7:20pm, by Prof. Luis Chaparro)

Textbook: Elements of Information Theory, by Cover and Thomas, Wiley, New York, 2006.

 

 

 

Tentative Class Schedule

 

HWs are due in one week unless otherwise stated

 

 

 

1st week

8/26

Introduction to Information Theory, Read Shannon’s year 1948 paper.

Primer on Probability (Do HW#0 to self evaluate your skill on probability and random variables)

2nd Week

9/2

Entropy, Relative Entropy and Mutual Information

 

HW#1

3rd Week

9/9

Entropy, Relative Entropy and Mutual Information

 

HW#2

4th Week

9/16

Asymptotic Equipartition Property

 

HW#3

5th Week

9/23

Asymptotic Equipartition Property/Entropy Rates of a Stochastic Process

HW#4

6th Week

9/30

Entropy Rates of a Stochastic Process/Data Compression

 

7th Week

10/7

Midterm #1

8th Week

10/14

No class due to Fall Break shifting of classes: Monday’s classes are held on Tuesday.

9th Week

10/21

Data Compression/Channel Capacity

HW#5

10th Week

10/28

Channel Capacity

 

HW#6

11th Week

11/4

Differential Entropy/Gaussian Channel

HW#7

12th Week

11/11

Gaussian Channel/Multiple Access Channel

 

HW#8

13th Week

11/18

Multiple Access Channel

 

14th Week

11/25

Midterm #2

15th Week

12/2

Student Presentation

16th Week

 

12/9

Student Presentation

 

 

 

 

 

Have you ever wondered about the following questions?

·        Living in an Information Age?  What’s information?

o       I obtained information about Information Theory course from Prof. Lee’s home-page.

o       Information of a binary source can be transferred from one location to the other. 

o       Are they used in the same sense?

·        What’s the minimum number of storage devices to store the front page of today’s N.Y. times paper?

·        Can we quantify the following statements?

o       Weather in L.A. is much more predictable than in Pittsburgh. 

o       A typical article in N.Y. times carries much more information than a city paper article does.

·        What’s the information capacity of a noisy channel?

o       You have a hard disk which has a defection rate of 1 in a thousand.  What is the maximum amount of information per cell that can be safely stored.

o       Red army vs. Blue army: Two Red army platoons are separated by the Blue army platoon which is camped in the middle.  Red army flies a series of message carrying pigeons to communicate with each other.  Blue army shoots down the flying pigeons with a certain success rate.  Each pigeon carries a single alphabet letter.  Releasing pigeon every sec, how much information can be transferred across this noisy channel?

o       You have a cell phone.  How much information can be carried by each call you make? 

·        In addition,

o       Can we quantify the viewing capacity of human eyes?

o       Can I control computers by thoughts or by hand waving?

o       What’s the capacity of the human brain?

o       What’s the capacity of human hands?

 

If you have and would like to learn a systematic way to answer these questions, you are seating at the right place.

 

This course is intended as an introduction of the Information Theory to the first and second year graduate students in electrical and computer engineering. The field of Information theory was started by C.E. Shannon in 1948 who attempted to answer most fundamental questions in communication theory such as: What is the ultimate data compression rate, and what is the ultimate transmission rate of communication over a channel? Today, the field of information theory has grown significantly and it is used throughout many disciplines including statistics, economics, computer science, signal processing, bio-informatics, video coding, multimedia communications, and control. 

 

At the University of Pittsburgh, we have many interesting research projects going on which potentially benefit from using Information theory.  Examples include researches on brain implants, neural encoding/decoding, and wireless communications and networking.  All of these areas can use the Information Theory as one of the fundamental toolsets for analysis and design.

 

Throughout the course, we will draw various kinds of mathematical tools from stochastic processes, probability theory, the law of large numbers, and optimization.  It would be beneficial if you have prior exposure to them; otherwise you might run into troubles and will not be able to appreciate the beauty of Information theory.  To them, the following co-requisite is recommended. 

Co-requisite: Introductory courses on stochastic processes, random variables and probability (offered on Thursday 5:20-7:20pm this semester by Prof. Luis Chaparro)

I will use the following textbook from where most of homework problems will be assigned.

Textbook: Elements of Information Theory, by Cover and Thomas, Wiley, New York, 2006.

Course grading will be given as follows:

  • Two midterms: 50%
  • 8-9 HW sets and class participation:  30%
  • Class Presentation of One Journal Paper: 20%

Selection of a journal paper for class presentation

·        Purpose:  See if you can apply the knowledge learned in class to expand the topics of your reading.

·        Procedure

o       Find the area of your interests (you can discuss this with me)

o       Use search engines (e.g. IEEEexplore, INSPEC, SCI, …) to find a paper

o       Send the pdf file to me for an approval, by Tuesday of 12th week.

o       Read the paper and its references

o       Summarize your understanding of the paper in PPT charts for 30 min. in class presentation

o       PPT charts should be written succinctly

§         Font size > 18

§         Number of pages < 30

·        Credits:

o       What’s the main contribution of the paper?

§         What is the problem solved in the paper?

§         Who else attempted to solve the problem?

§         What are the approaches taken by these predecessors?

§         What are the major differences that this paper provides from these previous approaches?

o       Discuss the technical details of the paper

§         What are the technical approaches arriving to the main results?

§         Can you explain the techniques?

§         Provide examples

o       Discuss the results

§         Explain the metrics the authors of the paper choose for comparisons

§         Summarize the new capabilities enabled by the paper.

·        IEEE journals are preferred.

·        The selected paper should be relevant to Information Theory.  For example, they should use it as the main tool to approach their problems.  The areas of interests include, but not limited to, the following:

o       Information embedded in neuron spiking activities

o       Control and information transfer in sensory systems

o       Encoding/decoding of neuron spiking activities

o       Wireless communications and networks

o       Information theoretic analysis of DNA and protein sequences