Back to overview over all lectures...
Information Theory
|
Chang Hui-Ting | Weng Jian-Jia | |
e-mail: | ||
office: | Engineering Building IV, Office 716A (ED716A) | Engineering Building IV, Office 708 (ED708) |
phone: | 03-571 21 21 ext. 54630 | 03-571 21 21 ext. 54624 |
office hours: | on appointment | Tuesday, 19:00–21:00 (in 716A!) |
To make our and your life easier, let's agree on the following rule: You may contact or visit the TAs at any time also outside of office hours. However, if you haven't made an appointment in advance, they have the right to tell you that they haven't got time right at that moment.
The course is scheduled for 4 hours per week:
On Thursday, the second hour is reserved for exercises. The mid-term and final exams will be 3 hours.
The course starts on Monday, 13 September 2010, and finishes on Thursday, 13 January 2011.
NCTU requests that every teacher offers two hours per week where students may come to ask questions:
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).
The course will be mainly be based on
You find here a link to an electronic version of the book. Moreover lecture notes will be handed out during class.
Further references and recommended readings:
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.
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.
The grade will be an average of
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.
The lecture will be held in English.
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 within NCTU and NTHU!
W | Date | Topic | Handouts | Exercise (due on) | Solutions | Comments |
1 | 13 Sep. | Introduction, measure of information: entropy | Syllabus (Version 3) Handout 1 |
Exercise 1 (20 Sep.) | Chapter 1 & 2; Handout 1 | |
16 Sep. | IT Inequality, conditional entropy, chain rule | Handout 2 | |
Chapter 2; Handout 1 | ||
2 | 20 Sep. | Relative entropy, mutual information, Jensen's inequality; data compression: efficient coding of a single RV, leaf-counting and leaf-depth lemma | Handout 3 | Exercise 2 (27 Sep.) | Chapter 2 & 5; Handout 1 & 3 | |
23 Sep. | Kraft inequality, trees with probabilities, path length lemma, leaf-entropy theorem, converse part of coding theorem for a single random message | Solutions 1 | Chapter 5; Handout 3 | |||
3 | 27 Sep. | Converse part of coding theorem for a single random message, Shannon-type coding, Shannon codes, Fano codes, binary Huffman codes, D-ary Huffman codes | Exercise 3 (4 Oct.) | Chapter 5; Handout 3 | ||
30 Sep. | D-ary Huffman codes, types of codes: McMillan's theorem | Handout 4 | Solutions 2 | Chapter 5; Handout 3 | ||
4 | 4 Oct. | Coding of an information source: block–to–variable-length coding, variable-length–to–block coding, Tunstall coding | Exercise 4 (11 Oct.) | Chapter 5; Handout 4 | ||
7 Oct. | Tunstall coding, performance bounds on Tunstall coding, stochastic processes, stationarity | Handout 5 | Solutions 3 | Chapter 5; Handout 4; Chapter 4; Handout 5 | ||
5 | 11 Oct. | Stochastic processes, stationarity, Markovity, entropy rate, Cesáro mean | Handout 6 | Exercise 5 (18 Oct.) | Chapter 4; Handout 5 | |
14 Oct. | Entropy rate, coding of sources with memory, adaptive Huffman coding, converse | Solutions 4 | Chapter 4; Handout 5; Chapter 5 & 12 & 13; Handout 6 | |||
6 | 18 Oct. | Elias codes for integers, Elias-Willems universal coding scheme, Lempel-Ziv universal coding scheme | Exercise 6 (25 Oct.) | Chapter 5 & 12 & 13; Handout 6 | ||
21 Oct. | Analysis of Lempel-Ziv universal coding scheme | Solutions 5 | Chapter 5 & 12 & 13; Handout 6 | |||
7 | 25 Oct. | Analysis of Lempel-Ziv universal coding scheme, maximum entropy distribution | Handout 7 | Exercise 7 (1 Nov.) | Chapter 5 & 12 & 13; Handout 6 | |
28 Oct. | AEP, typical sets | Revised Version of Problems 4/5 of Exercise 6 | Solutions 6 | Chapter 3; Handout 7 | ||
8 | 1 Nov. | Data compression revisited, gambling and horse betting | Handout 8 Handout 9 | Exercise 8 (15 Nov.) | Chapter 3; Handout 7; Chapter 6; Handout 8 | |
4 Nov. | Convex and concave functions, Kuhn-Tucker conditions | Solutions 7 | Chapter 6; Handout 8 & 9 | |||
9 | 8 Nov. | Midterm Exam | |
ATTENTION: This is a 3 hours exam: 10:10–13:00 | ||
11 Nov. | Discussion midterm exam, Kuhn-Tucker conditions | |
Handout 9 | |||
10 | 15 Nov. | Gambling and horse betting: subfair odds, betting with side-information, dependent horse races, transmission over a noisy channel: introduction | Handout 10 | Exercise 9 (22 Nov.) | Chapter 6; Handout 8 & 9; Chapter 7; Handout 10 |
|
18 Nov. | Transmission over a noisy channel: introduction | Solutions 8 | Chapter 7; Handout 10 | |||
11 | 22 Nov. | Transmission over a noisy channel: introduction, Fano's lemma, data processing inequality, Converse Coding Theorem | Exercise 10 (29 Nov.) | Chapter 7; Handout 10 | ||
25 Nov. | Converse Coding Theorem, jointly typical sequences | Solutions 9 | Chapter 7; Handout 10 | |||
12 | 29 Nov. | Achievabilty part, Channel Coding Theorem; computing capacity: strongly symmetric DMCs | Handout 11 | Exercise 11 (6 Dec.) | Chapter 7; Handout 10 & 11 | |
2 Dec. | Computing capacity: strongly & weakly symmetric DMCs, Kuhn-Tucker conditions | Solutions 10 | Chapter 7; Handout 11 | |||
13 | 6 Dec. | Computing capacity: Kuhn-Tucker conditions; Joint Source Channel Coding Theorem | Handout 12 Handout 13 |
Exercise 12 (13 Dec.) | Chapter 7; Handout 11 & 12 | |
9 Dec. | Continuous RVs: differential entropy, mutual information | Handout 14 (download only) | Solutions 11 | Chapter 8; Handout 13 | ||
14 | 13 Dec. | AEP for continuous RVs, multivariate Gaussian RVs, Gaussian channel: definition, information capacity | Handout 15 | Exercise 13 (20 Dec.) | Chapter 8 & 9; Handout 13 & 15 | |
16 Dec. | Gaussian channel: channel coding theorem, achievability proof, converse | Solutions 12 | Chapter 9; Handout 15 | |||
15 | 20 Dec. | Gaussian channel: channel coding theorem, achievability proof, converse, joint source and channel coding, transmission above capacity | Exercise 14 (27 Dec.) | Chapter 9; Handout 15 | ||
23 Dec. | Gaussian channel: transmission above capacity | Handout 16 | Solutions 13 | Chapter 9; Handout 15 | ||
16 | 27 Dec. | Bandlimited AWGN channel, sampling theorem | Handout 17 | Exercise 15 (3 Jan.) | Class evaluation online until 14 January! Chapter 9; Handout 16 |
|
30 Dec. | Parallel Gaussian channels | Solutions 14 | Chapter 9; Handout 17 | |||
17 | 3 Jan. | Introduction to cryptography (not part of exam) | Handout 18 | Exercise 16 (6 Jan.) | Handout 18 | |
6 Jan. | Introduction to cryptography (not part of exam), questions | Solutions 15, Solutions 16 |
Handout 18 | |||
18 | 10 Jan. | Final Exam | |
ATTENTION: This is a 3 hours exam: 10:10–13:00 | ||
13 Jan. | Discussion Final Exam, 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/