• Home
• About me
• Publica-
  tions
• IT-Scripts
• Lectures
• Software/
  Manuals
• Links
• Private
•  
•  
• 
  
•  
•  
• 
• 

Information Theory
Fall 2008/2009

⇒ to time table and download of class material

News

• Class Evaluation: The class evaluation will be online between December 30 to January 16. I would very much appreciate your feedback, so please spend a couple of minutes to fill out the online form! Thanks!
• Final Exam: The final exam will take place on
  • Tuesday, 13 January, 15:40-18:30 (Note that this is one hour longer than usual!)
  Regulations:
  • open book: any book is allowed
  • not allowed are: laptop, any telecommunication devices like mobile phones, any "friend" or other help from outside...
  • covered material: everything covered in class during the whole semester, apart from Cryptography (taught in Week 17)
• Conference: I will be abroad on 5 and 9 December. These classes will be canceled. Instead I will teach several times two hours on Friday.
• Mid-Term Exam: The mid-term exam will take place on
  • Tuesday, 11 November, 15:40-18:30 (Note that this is one hour longer than usual!)
  Regulations:
  • open-book: any books or notes are allowed
  • not allowed are: computers, any telecommunication devices like mobile phones, any "friend" or other help from outside...
  • covered material: everything up to and including Lempel-Ziv (AEP is not part of exam anymore)
  • style: similar to exercises, only easier... :-)
  • recommendation: bring a pocket calculator along for simple quick calculations

Course Objectives

This course is an introduction to Information Theory. We will cover the most important results concerning data compression and reliable communication over a communication channel. The course will follow approximately the following schedule:

• Introduction and basic definitions:
  • entropy
  • mutual information
  • relative entropy
  • gambling and horse betting
• Source coding: how to compress data efficiently?
  • Kraft inequality
  • source coding theorem for a single random variable
  • Shannon-Fano codes
  • Huffman codes
  • source coding theorem for a discrete memoryless source
  • Tunstall codes
  • universal codes
• Channel coding: how to transmit data reliably?
  • Fano's inequality and data processing lemma
  • converse to channel coding theorem for discrete memoryless channel
  • AEP and typical sequences
  • channel coding theorem
  • continuous random variables and entropy
  • channel coding theorem for the AWGN channel
  • band-limited AWGN channel

For more detail see the time table below.

We hope that a student who finishes the course will be able to understand the basic principles underlying any communication or data storage system.

Prerequisites

The following lectures/topics are recommended:

• Probability
• once more Probability
• Principles of Communication Engineering I and II (preferably, but not necessary)
• joy in math and engineering

Instructor

Prof. Stefan M. Moser
Engineering Building IV, Office 727
phone: 03-571 21 21 ext. 54548
e-mail:

Teaching Assistant

In case you would like to discuss some questions in Chinese, you may contact the TA of this class:

• Lin Gu-Rong
  e-mail:
  Office: Engineering Building IV, Lab 711
  Phone: 03-571 21 21 ext. 54628

Time and Place

The course is scheduled for 4 hours per week:

• Tuesday, 15:40-17:30, Engineering Building IV, Room 303 (ED303)
• Friday, 10:10-12:00, Engineering Building IV, Room 303 (ED303)

On Friday, the second hour is reserved for exercises. The mid-term and final exams will be 3 hours.
The course starts on Tuesday, 16 September 2008, and finishes Friday, 16 January 2009.

Office Hours

NCTU requests that every teacher offers two hours per week where students may come to ask questions:

• Wednesday, 9:30-11:30, Engineering Building IV, Office 727

However, we would like to encourage you to show up in the teacher's or teaching assistant's office at any time whenever you have questions about the class or related subjects. Moreover, we are always available during and after classes and particularly in the second hour on Friday (the "exercise" lecture).

Textbook

The course will be mainly be based on

• Thomas M. Cover and Joy A. Thomas: "Elements of Information Theory," second edition, Wiley, 2006.

You find here a link to an electronic version of the book. For certain topics additional lecture notes will be handed out during class.

Further references and recommended readings:

• James L. Massey: "Applied Digital Information Theory I and II," lecture notes, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland. (Link to electronic version)
• Robert G. Gallager: "Information Theory and Reliable Communication," Wiley, 1968.
• Po-Ning Chen and Fady Alajaji: "Lecture Notes in Information Theory," Volume I, National Chiao Tung University (NCTU), Hsinchu, Taiwan. (Link to electronic version)
• Po-Ning Chen and Fady Alajaji: "Lecture Notes in Information Theory," Volume II, National Chiao Tung University (NCTU), Hsinchu, Taiwan. (Link to electronic version)
• Raymond W. Yeung: "A First Course in Information Theory," Kluwer Academic Publishers, 2005.

Exercises

Every week, an exercise will be distributed in class and also made available online for download. This exercise will consist of several problems that need to be solved at home and handed in during the class of the following week. A model solution will be distributed and made available online afterwards.

We believe the exercises to be extremely important and crucial to the understanding of the course. They also serve as a preparation for the mid-term and final exams and we therefore highly recommend to solve them. To pass the course you need to hand in at least 10 exercises.

Exams

There will be one mid-term and one final exam. Both exams are going to last three hours and be open-book. Details about the covered material will be published in due time.

Grading

The grade will be an average of

• the homework (15%),
• the midterm exam (35%), and
• the final exam (50%).

Special Remarks

The lecture will be held in English.

Time Table

-||-   _|_ _|_     /    __|__   Stefan M. Moser
[-]     --__|__   /__\    /__   Senior Scientist, ETH Zurich, Switzerland
_|_     -- --|-    _     /  /   Adjunct Professor, National Yang Ming Chiao Tung University, Taiwan
/ \     []  \|    |_|   / \/    Web: https://moser-isi.ethz.ch/