Back to overview over all lectures...
Information Theory
|
Chen Wei-Hsiang | Lin 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 |
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 Tuesday, 15 September 2009, and finishes on Thursday, 14 January 2010.
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" lecture).
The course will be mainly be based on
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:
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. This course is worth 3 credits.
The lecture will be held in English.
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/