Back to overview over all lectures...

Information Theory
Fall 2009/2010


⇒ to time table and download of class material

News

  • Class Evaluation: The class evaluation will be online between 28 December and 8 January. 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, 12 January, 10:10–13:00 (Note that this is one hour longer than usual!)
    Location: Note that the exam will take place in a different class room:
    • Eng. Building V: Room 132 (EE132)
    Regulations:
    • open book: any book is allowed
    • not allowed are: computer, 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)
    • style: similar to mid-term exam
    • recommendation: bring a pocket calculator along for simple quick calculations
  • Mid-Term Exam: The mid-term exam will take place on
    • Tuesday, 10 November, 10:10–13:00 (Note that this is one hour longer than usual!)
    Location: Note that the exam will take place in a different class room:
    • Eng. Building V: Room 132 (EE132)
    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 the exam)
    • style: similar to exercises, only easier... :-)
    • recommendation: bring a pocket calculator along for simple quick calculations

Course Description

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 Assistants

Chen Wei-HsiangLin Hsuan-Yin
e-mail: e-mail:
Engineering Building IV, Office 716A (ED716A)Engineering Building IV, Office 716A (ED716A)
phone: 03-571 21 21 ext. 54630 phone: 03-571 21 21 ext. 54630

Time and Place

The course is scheduled for 4 hours per week:

  • Tuesday, 10:10–12:00 (CD), Engineering Building IV, Room B01 (EDB01)
  • Thursday, 15:40–17:30 (GH), Engineering Building IV, Room B01 (EDB01)

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

Office Hours

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

  • Tuesday, 13:30–15: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 Thursday (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 15 Sep. Introduction, measure of information: entropy Syllabus (Version 1) Exercise 1 (22 Sep.)   Chapter 1 & 2
  17 Sep. IT Inequality, conditional entropy, chain rule    
Chapter 2
2 22 Sep. Relative entropy, mutual information, Jensen's inequality, uniqueness of entropy; data compression: efficient coding of a single RV, leaf-counting and leaf-depths lemma Handout 1
Handout 2
Exercise 2 (29 Sep.)   Chapter 2, Handout 2, Chapter 5
  24 Sep. Kraft inequality, trees with probabilities, path length lemma, leaf-entropy theorem, converse part of coding theorem for a single RV     Solutions 1 Handout 2, Chapter 5
3 29 Sep. Coding theorem for a single RV, Shannon-Fano coding, types of codes, McMillan's Theorem, binary Huffman codes, D-ary Huffman codes Handout 3
Handout 4
Exercise 3 (6 Oct.)   Handout 2, Chapter 5
  1 Oct. Coding of an information source: block–to–variable-length coding, variable-length–to–block coding     Solutions 2 Handout 4, Chapter 5
4 6 Oct. Variable-length–to–block coding, Tunstall coding, stochastic processes, stationarity, Markovity Handout 5 Exercise 4 (20 Oct.)
Exercise 5 (20 Oct.)
  Handout 4, Chapter 5, Handout 5, Chapter 4
  8 Oct. No lecture (Conference)     Solutions 3  
5 13 Oct. No lecture (Conference)  
   
  15 Oct. No lecture (Conference)    
 
6 20 Oct. Stochastic processes, stationarity, Markovity, entropy rate, Cesáro mean   Exercise 6 (27 Oct.)   Handout 5, Chapter 4
  22 Oct. Coding of sources with memory, Elias codes for integers, Elias-Willems universal coding scheme, Lempel-Ziv universal coding scheme     Solutions 4
Solutions 5
Handout 5, Chapter 5, 13 & 12
7 27 Oct. Lempel-Ziv universal coding scheme, maximum entropy distribution   Exercise 7 (3 Nov.)   Chapter 13 & 12
  29 Oct. Lempel-Ziv universal coding scheme     Solutions 6 Chapter 13
8 3 Nov. AEP, typical sets, data compression revisited, gambling and horse betting   Exercise 8 (17 Nov.)   Chapter 3 & 6
  5 Nov. Gambling and horse betting Handout 6   Solutions 7 Chapter 6, Handout 6
9 10 Nov. Midterm Exam  
  ATTENTION: This is a 3 hours exam: 10:10–13:00
ATTENTION: Different Location: EE132
  12 Nov. Discussion midterm exam, gambling and horse betting, convex and concave functions    
Chapter 6, Handout 6
10 17 Nov. Convex and concave functions, Kuhn-Tucker conditions   Exercise 9 (24 Nov.)   Handout 6
  19 Nov. Gambling and horse betting: subfair odds, betting with side-information     Solutions 8 Chapter 6, Handout 6
11 24 Nov. Dependent horse races, transmission over a noisy channel: introduction   Exercise 10 (1 Dec.)   Chapter 6 & 7
  26 Nov. Transmission over a noisy channel: introduction, Fano's lemma     Solutions 9 Chapter 7
12 1 Dec. Transmission over a noisy channel: data processing inequality, Converse Coding Theorem, jointly typical sequences, Channel Coding Theorem   Exercise 11 (8 Dec.)   Chapter 7
  3 Dec. Channel Coding Theorem     Solutions 10 Chapter 7
13 8 Dec. Channel Coding Theorem, computing capacity: strongly symmetric DMCs Handout 7 Exercise 12 (15 Dec.)   Chapter 7, Handout 7
  10 Dec. Computing capacity: strongly & weakly symmetric DMCs, Kuhn-Tucker conditions     Solutions 11 Handout 7, Chapter 7
14 15 Dec. Computing capacity: Kuhn-Tucker conditions; Joint Source Channel Coding Theorem; differential entropy   Exercise 13 (22 Dec.)   Chapter 7 & 8
  17 Dec. Differential entropy, AEP for continuous RVs Handout 8   Solutions 12 Chapter 8
15 22 Dec. AEP for continuous RVs, Gaussian channel   Exercise 14 (29 Dec.)   Chapter 8 & 9
  24 Dec. Gaussian channel     Solutions 13 Chapter 9
16 29 Dec. Sampling theorem, bandlimited AWGN channel   Exercise 15 (5 Jan.)   Class evaluation online until 8 January!
Chapter 9
  31 Dec. Parallel Gaussian channels     Solutions 14 Chapter 9
17 5 Jan. Introduction to cryptography (not part of exam)   Exercise 16 (7 Jan.)    
  7 Jan. Introduction to cryptography (not part of exam), questions     Solutions 15,
Solutions 16
 
18 12 Jan. Final Exam  
  ATTENTION: This is a 3 hours exam: 10:10–13:00
ATTENTION: Different Location: EE132
  14 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: Fri Oct 29 10:42:26 UTC+8 2010