
Back to overview over all lectures...
Information Theory Fall 2012/2013
⇒ to time table and download of class material
News
 New version of Lecture Notes: A corrected version of the lecture notes (version 2.7) is available online. Chapters 17 to 19 have been worked over.
 Final Exam: The final exam will take place on
 Monday, 14 January, 12:20–15:10 (Note that this is ONE HOUR EARLIER than usual!)
Location: Engineering Building IV, Room 219 (ED219)
Regulations:
 openbook: any book or notes are 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 Chapter 19), i.e., Chapters 1–17
 style: similar to midterm exam
 recommendation: bring along a pocket calculator for simple quick calculations
 Class Evaluation: The class evaluation will be online until 13 January. 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 2.6) is available online. Chapters 13–16 and Appendix C have been worked over.
 New version of Lecture Notes: A corrected version of the lecture notes (version 2.5) is available online. Chapters 11 and 12 and Appendix B have been worked over.
 New version of Lecture Notes: A corrected version of the lecture notes (version 2.4) is available online. Chapters 10 to 12 have been worked over.
 Double lectures: On Wednesday, 12 December, and Wednesday, 19 December, we will be having a twohours lecture to make up the class that will be canceled on December 31.
 Late lectures: On Wednesday, 5 December, the class will be starting one hour later, i.e., from 11:10 to 12:00.
 New version of Lecture Notes: A corrected version of the lecture notes (version 2.3) is available online. Chapters 7 to 9 have been worked over.
 MidTerm Exam: The midterm exam will take place on
 Monday, 19 November, 12:20–15:10 (Note that we start ONE HOUR EARLIER than usual!)
Location: Engineering Building IV, Room 219 (ED219)
Regulations:
 openbook: 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: Chapters 1 to 8
 style: similar to exercises, only easier... :)
 recommendation: bring along a pocket calculator for simple quick calculations
 New version of Lecture Notes: A corrected version of the lecture notes (version 2.2) is available online. Chapters 1 to 6 have been worked over.
 Change of room: Note that the class room has changed. The lecture will be held on Monday in Room 219 (ED219) and on Wednesday in Room B26 (ED026).
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 the following schedule:
 Introduction and basic definitions:
 entropy
 mutual information
 relative entropy
 Source coding: how to compress data efficiently?
 Kraft inequality
 source coding theorem for a single random variable
 Shannontype codes
 Shannon code
 Fano code
 Huffman code
 source coding theorem for a discrete memoryless source
 arithmetic coding
 Tunstall code
 source coding theorem for a sources with memory
 adaptive Huffman coding
 universal codes: Elias–Willems coding, Lempel–Ziv coding
 Tools in information theory:
 Asymptotic Equipartition Property (AEP)
 Karush–Kuhn–Tucker (KKT) conditions
 Gambling and Horse Betting
 Channel coding: how to transmit data reliably?
 Fano's inequality and data processing lemma
 channel coding theorem for a discrete memoryless channel
 computing capacity
 error exponents
 joint source and channel coding
 Continuous random variables and differential entropy
 Gaussian Channel:
 channel coding theorem for the Gaussian channel
 bandlimited AWGN channel
 parallel Gaussian channels
 Brief overview over cryptography
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: 03571 21 21 ext. 54548
email:
Teaching Assistant
In case you would like to discuss some questions in Chinese, you may contact the TA of this class:
 Huang YuMing
email:
Office: Engineering Building IV, Lab 716A (ED716A)
Phone: 03571 21 21 ext. 54630
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, they have the right to tell you that they haven't got time right at that moment.
Time and Place
The course is scheduled for 4 hours per week:
 Monday, 13:20–15:10 (EF), Engineering Building IV, Room 219 (ED219)
 Wednesday, 10:10–12:00 (CD), Engineering Building IV, Room B26 (ED026)
On Wednesday, the second hour is reserved for exercises. The midterm and final exams will be 3 hours.
The course starts on Monday, 17 September 2012, and finishes on Wednesday, 16 January 2013.
Office Hours
NCTU requests that every teacher offers two hours per week where students may come to ask questions. I will, of course, also do so:
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.)
 James L. Massey: “Applied Digital Information Theory I and II,” lecture notes, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland. (Link to electronic version)
 Thomas M. Cover and Joy A. Thomas: “Elements of Information Theory,” second edition, Wiley, 2006.
 Robert G. Gallager: “Information Theory and Reliable Communication,” Wiley, 1968.
 PoNing Chen and Fady Alajaji: “Lecture Notes in Information Theory,” Volume I, National Chiao Tung University (NCTU), Hsinchu, Taiwan. (PDF)
 PoNing Chen and Fady Alajaji: “Lecture Notes in Information Theory,” Volume II, National Chiao Tung University (NCTU), Hsinchu, Taiwan. (PDF)
 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 midterm 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 midterm and one final exam. Both exams are going to last three hours and be openbook. Details about the covered material will be published in due time. The final exam will cover everything taught in class.
Grading
The grade will be an average of
 the homework and class participation (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. 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 within NCTU and NTHU!
W 
Date 
Topic 
Handouts 
Exercise (due on) 
Solutions 
Comments 
1 
17 Sep. 
Introduction, motivation, entropy, IT Inequality, conditional entropy 
Syllabus (Version 2) 
Exercise 1 (24 Sep.) 

Chapter 1 

19 Sep. 
Conditional entropy, chain rule, relative entropy 
Lecture Notes 


Chapter 1 
2 
24 Sep. 
Relative entropy, mutual information, Jensen's inequality; data compression: efficient coding of a single RV, trees, leafcounting and leafdepth lemma, Kraft inequality 

Exercise 2 (1 Oct.) 

Chapters 1 & 3 

26 Sep. 
Trees with probabilities, path length lemma, leafentropy theorem, converse part of coding theorem for a single random message, Shannontype codes 


Solutions 1 
Chapter 3 
3 
1 Oct. 
Shannontype codes, Shannon codes, Fano codes, binary Huffman codes, Dary Huffman codes 

Exercise 3 (8 Oct.) 

Chapter 3 

3 Oct. 
Types of codes: McMillan's theorem; coding of an information source: block–to–variablelength coding 


Solutions 2 
Chapters 3 & 4 
4 
8 Oct. 
Arithmetic coding & decoding, variablelength–to–block coding 

Exercise 4 (15 Oct.) 

Chapter 4 daryexp.m invdaryexp.m 

10 Oct. 
No lecture (holiday) 


Solutions 3 

5 
15 Oct. 
Variablelength–to–block coding, Tunstall coding, performance bounds on Tunstall coding; stochastic processes, stationarity, Markovity 

Exercise 5 (22 Oct.) 

Chapters 4 & 5 guessParagraph.zip 

17 Oct. 
Entropy rate, Cesáro mean 


Solutions 4 
Chapter 5 
6 
22 Oct. 
Coding of sources with memory: adaptive Huffman coding, converse, Elias codes for integers, Elias–Willems universal coding scheme, Lempel–Ziv universal coding scheme 

Exercise 6 (29 Oct.) 

Chapter 6 

24 Oct. 
Analysis of Lempel–Ziv universal coding scheme, maximum entropy distribution 


Solutions 5 
Chapter 6 
7 
29 Oct. 
Analysis of Lempel–Ziv universal coding scheme, convex and concave functions, KKT conditions 

Exercise 7 (5 Nov.) 

Chapters 6 & 7 

31 Oct. 
KKT conditions, gambling and horse betting 


Solutions 6 
Chapters 7 & 8 
8 
5 Nov. 
Gambling and horse betting 

Exercise 8 (12 Nov.) 

Chapter 8 

7 Nov. 
Gambling and horse betting, transmission over a noisy channel: introduction 


Solutions 7 
Chapters 8 & 9 
9 
12 Nov. 
Transmission over a noisy channel: DMC, capacity, Fano's lemma, data processing inequality, converse of coding theorem 

Exercise 9 (26 Nov.) 

Chapter 9 

14 Nov. 
Transmission over a noisy channel: random coding 


Solutions 8 
Chapter 9 
10 
19 Nov. 
Midterm Exam (bring calculator!) 
Exam statistics 

Preliminary Solutions 9 
ATTENTION: This is a 3 hours exam: 12:20–15:10 

21 Nov. 
Discussion midterm exam; transmission over a noisy channel: coding theorem 



Chapter 9 
11 
26 Nov. 
Computing capacity: strongly & weakly symmetric DMCs, KKT conditions 

Exercise 10 (3 Dec.) 

Chapter 10 

28 Nov. 
Convolutional codes: encoding and decoding 


Solutions 9 
Chapter 11 
12 
3 Dec. 
Convolutional codes: quality 

Exercise 11 (10 Dec.) 

Chapter 11 

5 Dec. 
Error exponents 


Solutions 10 
Chapter 12 Class from 11:10 to 12:00! 
13 
10 Dec. 
Error exponents 

Exercise 12 (17 Dec.) 

Chapter 12 

12 Dec. 
Joint source and channel coding, transmission above capacity 


Solutions 11 
Chapter 13 double lecture! 
14 
17 Dec. 
Continuous RVs: differential entropy, mutual information; Gaussian channel 

Exercise 13 (24 Dec.) 

Chapters 14 & 15 

19 Dec. 
Gaussian channel 


Solutions 12 
Chapter 15 double lecture! 
15 
24 Dec. 
AWGN channel 

Exercise 14 (2 Jan.) 

Chapter 16 

26 Dec. 
AWGN channel; parallel Gaussian channels 


Solutions 13 
Class evaluation online until 13 January! Chapters 16 & 17 
16 
31 Dec. 
No lecture (holiday) 

Exercise 15 (7 Jan.) 



2 Jan. 
Parallel Gaussian channels 


Solutions 14 
Chapter 17 
17 
7 Jan. 
Introduction to cryptography (not part of exam) 

Exercise 16 (9 Jan.) 

Chapter 19 

9 Jan. 
Introduction to types (not part of exam), questions 


Solutions 15, Solutions 16 
Chapter 18 
18 
14 Jan. 
Final Exam 
Exam statistics 


ATTENTION: This is a 3 hours exam: 12:20–15:10 

16 Jan. 
Discussion final exam, coffee time 




 __ __ / ____ Stefan M. Moser
[] ____ /__\ /__ Senior Researcher & Lecturer, ETH Zurich, Switzerland
__   _ / / Adj. Professor, National Chiao Tung University (NCTU), Taiwan
/ \ [] \ _ / \/ Web: http://moserisi.ethz.ch/
Last modified: Wed Jan 16 12:38:50 UTC+8 2013
