|
Back to overview over all lectures...
Advanced Topics in Information Theory Spring 2012
⇒ to time table and download of class material
News
- New version of Lecture Notes: A corrected version of the lecture notes (version 1.9) is available online. Chapters 12 and 13 have been worked over.
- New version of Lecture Notes: A corrected version of the lecture notes (version 1.8) is available online. Chapters 10 and 11 (and partially 12) have been worked over.
- Final Exam: The final exam will take place on
- Tuesday, 19 June, between 14:00–16:00.
Regulations:
- The exam is oral: we have a chat together about some topics in class.
- Duration: each student will be questioned separately for 20 minutes. The exact schedule will be distributed in advance.
- Location: my office (ED727)
- Covered material: everything covered in class
- Class Evaluation: The class evaluation is online between 30 May and 15 June. I would very much appreciate your feedback, so please spend a couple of minutes to fill out the online form. Thanks!
- New version of Lecture Notes: A corrected version of the lecture notes (version 1.7) is available online. Chapter 9 has been worked over.
- New version of Lecture Notes: A corrected version of the lecture notes (version 1.6) is available online. Chapter 8 has been worked over, and Section 1.5 has been enlarged.
- New version of Lecture Notes: A corrected version of the lecture notes (version 1.5) is available online. Chapter 7 has been worked over, a new Section 1.3 added and some more typos in Chapters 1–6 corrected.
- New version of Lecture Notes: A corrected version of the lecture notes (version 1.4) is available online. Chapter 6 has been worked over.
- Mid-Term Exam: The mid-term exam will take place on
- Tuesday, 24 April, 13:30–15:20
Regulations:
- half-open book: the lecture notes are allowed to bring, but not the exercises.
- also 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 and including Chapter 5 (rate distortion, but not including the error exponent)
- New version of Lecture Notes: A corrected version of the lecture notes (version 1.3) is available online. Chapter 5 has been worked over.
- New version of Lecture Notes: A corrected version of the lecture notes (version 1.2) is available online. Chapters 3 and 4 have been worked over.
- New version of Lecture Notes: A corrected version of the lecture notes (version 1.1) is available online. Chapters 1 and 2 have been worked over.
- Change of classroom: Please be aware that the location of this course has changed: we will be now in ED102.
- New Lecture Notes: Starting from this spring, we will be using newly typed lecture notes. The notes will be distributed free of charge to all registered students.
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:
- Method of types.
- Large deviation theory (Sanov's theorem, conditional limit theorem).
- Strong typicality.
- Rate distortion theory.
- Error exponents in rate distortion theory.
- Multiple description.
- Rate distortion with side-information (Wyner–Ziv).
- Distributed lossless data compression (Slepian–Wolf).
- Multiple-access channel (MAC).
- Transmission of correlated sources over a MAC.
- Channels with noncausal side-information (Gel'fand–Pinsker).
- Broadcast channel.
- Interference channel.
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:
- Kuo Yuan-Chu
e-mail:
Office: Engineering Building IV, Lab 716A (ED716A)
Phone: 03-571 21 21 ext. 54630
office hours: on appointment
To make our and your life easier, let's agree on the following rule: You may contact or visit the TA at any time also outside of office hours. However, if you haven't made an appointment in advance, she has the right to tell you that she hasn't got time right at that moment.
Time and Place
The course is scheduled for 3 hours per week:
- Tuesday, 13:30–15:20 (EF), Engineering Building IV, Room 102 (ED102)
- Thursday, 13:30–15:20 (EF), Engineering Building IV, Room 102 (ED102)
On Thursday, the second hour is reserved for exercises.
The course starts on Tuesday, 21 February 2012, and finishes on Thursday, 21 June 2012.
Office Hours
NCTU requests that every teacher offers two hours per week where students may come to ask questions:
- Tuesday, 15:30–17: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" hour).
Textbook
The course will follow my own lecture notes:
These lecture notes will be distributed free of charge to all registered students of the course during the first week of the semester.
Further references and recommended readings:
- Claude E. Shannon: “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, pp. 379–423 and 623–656, July and October 1948. (PDF) (Some remarks about this electronic version.)
- 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)
- 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.
- Thomas M. Cover and Joy A. Thomas: “Elements of Information Theory,” second edition, Wiley, 2006.
- 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. The exact form (oral, written, etc.) will be decided in due time.
Grading
The grade will be an average of
- the homework and class participation (20%),
- the midterm exam (40%), and
- the final exam (40%).
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. Moreover, I will try to reward students who participate actively in the course.
This course is worth 3 credits.
Special Remarks
The lecture will be held in English.
Time Table
Note that some details of this program might change in the course of the semester.
Note that some linked documents in this table can only be downloaded from within NCTU and NTHU!
W |
Date |
Topic |
Handouts |
Exercise (due on) |
Solutions |
Comments |
1 |
21 Feb. |
Some important inequalities, law of large numbers |
Syllabus (Version 3) |
Exercise 1 (1 Mar.) |
|
Chapter 1 |
|
23 Feb. |
Method of types |
|
|
|
Chapter 2 |
2 |
28 Feb. |
No lecture (Holiday) |
|
|
|
|
|
1 Mar. |
Method of types |
|
Exercise 2 (6 Mar.) |
Solutions 1 |
Chapter 2 |
3 |
6 Mar. |
Large deviation theory: Sanov's theorem, Pythagorean theorem |
|
Exercise 3 (13 Mar.) |
|
Chapter 3 |
|
8 Mar. |
Large deviation theory: Pinsker's inequality, conditional limit theorem |
|
|
Solutions 2 |
Chapter 3 |
4 |
13 Mar. |
Large deviation theory: conditional limit theorem; strongly typical sets: TA |
|
Exercise 4 (20 Mar.) |
|
Chapters 3 & 4 |
|
15 Mar. |
Strongly typical sets: TA, TB |
|
|
Solutions 3 |
Chapter 4 |
5 |
20 Mar. |
Strongly typical sets: TB, TC, TD; rate distortion theory: introduction |
|
Exercise 5 (27 Mar.) |
|
Chapters 4 & 5 |
|
22 Mar. |
Rate distortion theory: information rate distortion function |
|
|
Solutions 4 |
Chapter 5 |
6 |
27 Mar. |
Rate distortion theory: coding theorem |
|
Exercise 6 (10 Apr.) |
|
Chapter 5 |
|
29 Mar. |
Rate distortion theory: characterization |
|
|
Solutions 5 |
Chapter 5 |
7 |
3 Apr. |
No lecture (Holiday) |
|
|
|
|
|
5 Apr. |
Rate distortion theory: characterization |
|
|
|
Chapter 5 |
8 |
10 Apr. |
Rate distortion theory: Gaussian sources; error exponent for rate distortion theory |
|
Exercise 7 (17 Apr.) |
|
Chapters 5 & 6 |
|
12 Apr. |
Error exponent for rate distortion theory: strong converse |
|
|
Solutions 6 |
Chapter 6 |
9 |
17 Apr. |
Error exponent for rate distortion function: type covering lemma, achievability |
|
Exercise 8 (1 May) |
|
Chapter 6 |
|
19 Apr. |
Error exponent for rate distortion function: converse |
|
|
Solutions 7 |
Chapter 6 |
10 |
24 Apr. |
Mid-Term Exam |
|
|
|
|
|
26 Apr. |
Discussion exam, multiple descriptions |
|
|
|
Chapter 7 |
11 |
1 May |
Multiple descriptions |
|
Exercise 9 (8 May) |
|
Chapter 7 |
|
3 May |
Multiple descriptions |
|
|
Solutions 8 |
Chapter 7 |
12 |
8 May |
Wyner–Ziv problem: rate distortion with side-information |
Handout 1 |
Exercise 10 (15 May) |
|
Chapter 8 |
|
10 May |
Wyner–Ziv problem: rate distortion with side-information |
|
|
Solutions 9 |
Chapter 8 |
13 |
15 May |
Slepian–Wolf problem: distributed lossless compression; multiple-access channel (MAC) |
|
Exercise 11 (22 May) |
|
Chapters 9 & 10 |
|
17 May |
Multiple-access channel (MAC) |
|
|
Solutions 10 |
Chapter 10 |
14 |
22 May |
Multiple-Access Channel (MAC) |
|
Exercise 12 (29 May) |
|
Chapter 10 |
|
24 May |
Multiple-Access Channel (MAC), transmission of correlated sources over a MAC |
|
|
Solutions 11 |
Chapters 10 & 11 |
15 |
29 May |
Transmission of correlated sources over a MAC; Gel'fand–Pinsker problem: channels with noncausal side-information |
|
Exercise 13 (5 Jun.) |
|
Chapters 11 & 12 |
|
31 May |
Gel'fand–Pinsker problem: channels with noncausal side-information |
|
|
Solutions 12 |
Please fill out online class evaluation before 15 June! Chapter 12 |
16 |
5 Jun. |
Gel'fand–Pinsker problem: channels with noncausal side-information; broadcast channel |
Handout 2 Handout 3 |
Exercise 14 (12 Jun.) |
|
Chapters 12 & 13 |
|
7 Jun. |
Presentation about Fading Channels |
|
|
Solutions 13 |
ED 202 |
17 |
12 Jun. |
Broadcast channel |
|
Exercise 15 (14 Jun.) |
|
Chapter 13 |
|
14 Jun. |
Broadcast channel |
|
|
Solutions 14, Solutions 15 |
Chapter 13 |
18 |
19 Jun. |
Final Exam |
|
|
|
|
|
21 Jun. |
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: Wed Jun 20 06:59:34 UTC+8 2012
|