Back to overview over all lectures...

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%).
The grade of the homework will not be based on the correctness of the answers, but rather on the effort the student shows in trying to solve them. This course is worth 3 credits.

Special Remarks

The lecture will be held in English.

Time Table

W Date Topic Handouts Exercise (due on) Solutions Comments
1 16 Sep. Introduction, measure of information: entropy Syllabus (Version 2) Exercise 1 (23 Sep.)   Chapter 2
  19 Sep. IT Inequality, conditional entropy, chain rule Handout 1   ----- Chapter 2
2 23 Sep. Chain rule, relative entropy, mutual information, Jensen's inequality, data compression: efficient coding of a single RV Handout 2 Exercise 2 (30 Sep.)   Chapter 2, Handout 2, Chapter 5
  26 Sep. Leaf-counting, leaf-depths, Kraft inequality     Solutions 1 Handout 2, Chapter 5
3 30 Sep. Trees with probabilities, path length lemma, leaf-entropy theorem, coding theorem for a single RV, Shannon-Fano coding, types of codes   Exercise 3 (7 Oct.)   Handout 2, Chapter 5
  3 Oct. McMillan's Theorem Handout 3   Solutions 2 Handout 2, Chapter 5
4 7 Oct. Binary Huffman codes, D-ary Huffman codes, coding of an information source: block–to–variable-length coding, variable-length–to–block coding Handout 4 Exercise 4 (14 Oct.)   Handout 2 & 4, Chapter 5
  10 Oct. No lecture (Holiday)     -----  
5 14 Oct. Coding of an information source: variable-length–to–block coding, Tunstall coding, stochastic processes, stationarity, Markovity Handout 5 Exercise 5 (21 Oct.) Solutions 3 Handout 4, Chapter 5, Handout 5, Chapter 4
  17 Oct. Stochastic processes, Markovity, entropy rate     Solutions 4 Handout 5, Chapter 4
6 21 Oct. Entropy rate, Cesáro mean, coding of sources with memory, Elias-Willems universal coding scheme, Elias codes for integers   Exercise 6 (28 Oct.)   Handout 5, Chapter 4 & 13
  24 Oct. Elias-Willems universal coding scheme, Lempel-Ziv universal coding scheme     Solutions 5 Handout 5, Chapter 13 & 12
7 28 Oct. Lempel-Ziv universal coding scheme, maximum entropy distribution   Exercise 7 (4 Nov.)   Chapter 13 & 12
  31 Oct. Lempel-Ziv universal coding scheme, AEP     Solutions 6 Chapter 13 & 3
8 4 Nov. AEP, typical sets, data compression revisited, gambling and horse betting Handout 6 Exercise 8 (18 Nov.)   Chapter 3 & 6
  7 Nov. Gambling and horse betting, bookie's perspective     Solutions 7 Chapter 6, Handout 6
9 11 Nov. Midterm Exam   -----   ATTENTION: This is a 3 hours exam: 15:40-18:30
  14 Nov. Discussion midterm exam, convex and concave functions, Kuhn-Tucker conditions     ----- Chapter 6, Handout 6
10 18 Nov. Kuhn-Tucker conditions, subfair odds, betting with side-information   Exercise 9 (25 Nov.)   Chapter 6, Handout 6
  21 Nov. Dependent horse races, transmission over a noisy channel     Solutions 8 Chapter 6 & 7
11 25 Nov. Transmission over a noisy channel, Fano's lemma, data processing inequality, Converse Coding Theorem, jointly typical sequences   Exercise 10 (2 Dec.)   Chapter 2 & 7
  28 Nov. Jointly typical sequences, Channel Coding Theorem     Solutions 9 Chapter 7
12 2 Dec. Channel Coding Theorem, computing capacity: strongly symmetric DMCs Handout 7 Exercise 11 (16 Dec.)
Exercise 12 (16 Dec.)
  Chapter 7, Handout 7
  5 Dec. No lecture (Conference)     -----  
13 9 Dec. No lecture (Conference)   -----    
  12 Dec. Computing capacity: strongly & weakly symmetric DMCs, Kuhn-Tucker conditions     Solutions 10 Handout 7, Chapter 7
14 16 Dec. Computing capacity: Kuhn-Tucker conditions; Joint Source Channel Coding Theorem; differential entropy   Exercise 13 (23 Dec.)   Chapter 7 & 8
  19 Dec. Differential entropy, AEP for continuous RVs     Solutions 11
Solutions 12
Chapter 8
15 23 Dec. AEP for continuous RVs, Gaussian channel   Exercise 14 (30 Dec.)   Chapter 8 & 9
  26 Dec. Gaussian channel, sampling theorem Handout 8   Solutions 13 Chapter 9
16 30 Dec. Sampling theorem, bandlimited AWGN channel, parallel Gaussian channels   Exercise 15 (6 Jan.)   Chapter 9
  2 Jan. No lecture (Holiday)     -----  
17 6 Jan. Parallel Gaussian channels, introduction to cryptography (not part of exam)   Exercise 16 (9 Jan.) Solutions 14 Chapter 9; Class evaluation online until January 16
  9 Jan. Introduction to cryptography (not part of exam), questions     Solutions 15,
Solutions 16
Chapter 9
18 13 Jan. Final Exam   -----   ATTENTION: This is a 3 hours exam: 15:40-18:30
  16 Jan. Discussion Final Exam     -----  

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


Last modified: Thu Feb 19 08:23:37 UTC+8 2009