Back to overview over all lectures...

Information Theory
Fall 2010/2011


⇒ to time table and download of class material

News

  • Class Evaluation: The class evaluation will be online between 28 December and 14 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
    • Monday, 10 January, 10:10–13:00 (Note that this is one hour longer than usual!)
    Location: Engineering Building IV, Room 203 (ED203)
    Regulations:
    • open book: any book is 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 Cryptography (taught in Week 17)
    • style: similar to mid-term exam
    • recommendation: bring a pocket calculator along for simple quick calculations
  • Change of office hours of one TA: The office hours of Weng Jian-Jia have been switched back to Tuesday, 19:00–21:00.
  • Mid-Term Exam: The mid-term exam will take place on
    • Monday, 8 November, 10:10–13:00 (Note that this is one hour longer than usual!)
    Location: Engineering Building IV, Room 203 (ED203)
    Regulations:
    • open-book: 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: everything until the lecture of 28 October, i.e., until Handout 7, Sec. 3
    • style: similar to exercises, only easier... :-)
    • recommendation: bring a pocket calculator along for simple quick calculations
  • Change of room: Note that the class room has changed. The lecture will be held on both days in Room 203 (ED203).

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 approximately the following schedule:

  • Introduction and basic definitions:
    • entropy
    • mutual information
    • relative entropy
    • gambling and horse betting
  • Source coding: how to compress data efficiently?
    • Kraft inequality
    • source coding theorem for a single random variable
    • Shannon-Fano codes
    • Huffman codes
    • source coding theorem for a discrete memoryless source
    • Tunstall codes
    • universal codes
  • Channel coding: how to transmit data reliably?
    • Fano's inequality and data processing lemma
    • converse to channel coding theorem for discrete memoryless channel
    • AEP and typical sequences
    • channel coding theorem
    • continuous random variables and entropy
    • channel coding theorem for the AWGN channel
    • band-limited AWGN channel

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: 03-571 21 21 ext. 54548
e-mail:

Teaching Assistants

In case you would like to discuss some questions in Chinese, you may contact the TAs of this class:

Chang Hui-TingWeng Jian-Jia
e-mail:
office:Engineering Building IV, Office 716A (ED716A)Engineering Building IV, Office 708 (ED708)
phone:03-571 21 21 ext. 5463003-571 21 21 ext. 54624
office hours:on appointmentTuesday, 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.

Time and Place

The course is scheduled for 4 hours per week:

  • Monday, 10:10–12:00 (CD), Engineering Building IV, Room 203 (ED203)
  • Thursday, 15:40–17:30 (GH), Engineering Building IV, Room 203 (ED203)

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.

Office Hours

NCTU requests that every teacher offers two hours per week where students may come to ask questions:

  • Monday, 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 and particularly in the second hour on Thursday (the "exercise" hour).

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. Moreover lecture notes will be handed out during class.

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)
  • Robert G. Gallager: “Information Theory and Reliable Communication,” Wiley, 1968.
  • Po-Ning Chen and Fady Alajaji: “Lecture Notes in Information Theory,” Volume I, National Chiao Tung University (NCTU), Hsinchu, Taiwan. (PDF)
  • Po-Ning 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 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 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 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/


Last modified: Mon Jan 10 13:34:34 UTC+8 2011