Back to overview over all lectures...

Advanced Topics in 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
    • Wednesday, 13 January, between 15:00-18:30.
    Regulations:
    • The exam is oral: we have a chat together about some topics in class.
    • Duration: each student will be questioned separately for 30 minutes. The exact schedule will be distributed in advance.
    • Location: my office (ED727)
    • Covered material: everything covered in class
  • Mid-Term Exam: The mid-term exam will take place one week later than originally posted online! It will take place on
    • Wednesday, 18 November, 15:40-18:30 (Note that this is one hour longer than usual!)
    Regulations:
    • open book: any book is allowed
    • not allowed are: any telecommunication devices like mobile phones, any laptop with wireless capabilities, any "friend", or any other help from outside...
    • covered material: everything up to rate distortion, but not including the error exponent

Course Description

This course is an advanced course in information theory. Based on the theory we have learned in the course Information Theory we will continue to explore the most important results concerning data compression and reliable communication over a communication channel. We will talk about multiple-user communication and lossy compression schemes. The course will cover approximately the following topics:

  • Methods of types
  • Rate distortion theory (lossy compression)
  • Multiple-users channels:
    • Multiple-access channel
    • Broadcast channel
    • Relay channel
    • Interference channel
  • Gel'fand-Pinsker problem: channels with random parameters known at the transmitter
  • Correlated source encoding (Slepian-Wolf)
  • Information theory and the stock market

For more detail see the time table below.

We hope that a student who finishes the course will be able to better understand the principles underlying all state-of-the-art communication systems and the difficulties encountered when designing and trying to improve them.

Prerequisites

  • Probability
  • Information Theory

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 Hsuan-Yin
    e-mail:
    Office: Engineering Building IV, Lab 716A (ED716A)
    Phone: 03-571 21 21 ext. 54630

Time and Place

The course is scheduled for 3 hours per week:

  • Wednesday, 15:40–17:30 (GH), Engineering Building IV, Room 303 (ED303)
  • Friday, 9:00–9:50 (B), Engineering Building IV, Room 303 (ED303)

The course starts on Wednesday, 16 September 2009, and finishes on Friday, 15 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.

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:

  • Robert G. Gallager: “Information Theory and Reliable Communication,” Wiley, 1968.
  • Imre Csiszár, János Körner: “Information Theory: Coding Theorems for Discrete Memoryless Systems,” 3rd edition, Akademiai Kiado, Budapest.
  • Gerhard Kramer: “Topics in Multi-User Information Theory”, Foundations and Trends in Communications and Information Theory, vol. 4, nos. 4–5, pp. 265–444, 2007. (Link to electronic version)
  • 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)
  • James L. Massey: “Applied Digital Information Theory I and II,” lecture notes, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland. (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. Method of types Syllabus (Version 1) Exercise 1 (23 Sep.)   Chapter 11.1
  18 Sep. Method of types, large deviation theory (Sanov's theorem)    
Chapter 11.1, 11.4
2 23 Sep. Large deviation theory (Sanov's theorem), conditional limit theorem   Exercise 2 (30 Sep.)   Chapter 11.4–6
  25 Sep. Sanov's theorem, conditional limit theorem     Solutions 1 Chapter 11.4–6
3 30 Sep. Conditional limit theorem, joint and conditional types, strongly typical sets   Exercise 3 (7 Oct.)   Chapter 11.6, 10.6
  2 Oct. Conditional limit theorem, joint and conditional types, strongly typical sets Handout 1   Solutions 2 Chapter 11.6, 10.6
4 7 Oct. Strongly typical sets   Exercise 4 (21 Oct.)
Exercise 5 (21 Oct.)
  Chapter 10.6
  9 Oct. No lecture (Conference)     Solutions 3  
5 14 Oct. No lecture (Conference)  
   
  16 Oct. No lecture (Conference)    
 
6 21 Oct. Strongly typical sets, rate distortion theory   Exercise 6 (28 Oct.)   Chapter 10
  23 Oct. Rate distortion theory     Solutions 4
Solutions 5
Class starts at 8 am already!
Chapter 10
7 28 Oct. Rate distortion theory Corr. Exercise 5 Exercise 7 (4 Nov.)   Chapter 10
  30 Oct. Rate distortion theory: Gaussian sources, characterization of rate distortion function     Solutions 6 Chapter 10
8 4 Nov. Characterization of rate distortion function, error exponent for rate distortion function: type covering lemma Handout 2 Exercise 8 (11 Nov.)   Chapter 10, Csiszar
  6 Nov. Error exponent for rate distortion function, multiple descriptions     Solutions 7 Class starts at 8 am already!
Csiszar, Handout 3
9 11 Nov. Multiple descriptions Handout 3 Exercise 9 (25 Nov.)   Handout 3
  13 Nov. Multiple descriptions, Wyner-Ziv problem: rate distortion with side-information     Solutions 8 Handout 3, Chapter 15.9
10 18 Nov. Midterm Exam  
  ATTENTION: This is a 3 hours exam: 15:40-18:30
  20 Nov. Discussion exam, Wyner-Ziv problem: rate distortion with side-information    
Chapter 15.9
11 25 Nov. Wyner-Ziv problem: rate distortion with side-information   Exercise 10 (2 Dec.)   Chapter 15.9
  27 Nov. Wyner-Ziv problem: rate distortion with side-information     Solutions 9 Chapter 15.9
12 2 Dec. Slepian-Wolf problem: distributed lossless compression   Exercise 11 (9 Dec.)   Chapter 15.4
  4 Dec. Slepian-Wolf problem: distributed lossless compression     Solutions 10 Chapter 15.4
13 9 Dec. Multiple-Access Channel (MAC)   Exercise 12 (16 Dec.)   Chapter 15.3
  11 Dec. MAC: achievability     Solutions 11 Chapter 15.3
14 16 Dec. MAC: achievability and converse, Gaussian MAC   Exercise 13 (23 Dec.)   Chapter 15.3 & 15.1
  18 Dec. Gaussian MAC     Solutions 12 Chapter 15.3 & 15.1
15 23 Dec. Transmission of correlated sources over a MAC Handout 4
Handout 5
Exercise 14 (30 Dec.)    
  25 Dec. Gel'fand-Pinsker problem: channels with non-causal side-information     Solutions 13 Kramer
16 30 Dec. Converse of Gel'fand-Pinsker problem   Exercise 15 (8 Jan.)   Class evaluation online until 8 January!
Kramer
  1 Jan. No lecture (Holiday)    
 
17 6 Jan. Sumary Gel'fand-Pinsker problem, broadcast channel  
Solutions 14 Kramer, Chapter 15.6
  8 Jan. Broadcast channel     Solutions 15 Chapter 15.6
18 13 Jan. Final Exam  
  ATTENTION: This is an oral exam of 30 minutes!
  15 Jan. Coffee time    
 

-||-   _|_ _|_     /    __|__   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:38:06 UTC+8 2010