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:
    • open-book: 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 mid-term 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 two-hours 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.
  • Mid-Term Exam: The mid-term 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:
    • 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: 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
    • Shannon-type 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: 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:

  • Huang Yu-Ming
    e-mail:
    Office: Engineering Building IV, Lab 716A (ED716A)
    Phone: 03-571 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 mid-term 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:

  • Will be announced.

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.
  • 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. 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, leaf-counting and leaf-depth lemma, Kraft inequality   Exercise 2 (1 Oct.)   Chapters 1 & 3
  26 Sep. Trees with probabilities, path length lemma, leaf-entropy theorem, converse part of coding theorem for a single random message, Shannon-type codes     Solutions 1 Chapter 3
3 1 Oct. Shannon-type codes, Shannon codes, Fano codes, binary Huffman codes, D-ary Huffman codes   Exercise 3 (8 Oct.)   Chapter 3
  3 Oct. Types of codes: McMillan's theorem; coding of an information source: block–to–variable-length coding     Solutions 2 Chapters 3 & 4
4 8 Oct. Arithmetic coding & decoding, variable-length–to–block coding   Exercise 4 (15 Oct.)   Chapter 4
daryexp.m
invdaryexp.m
  10 Oct. No lecture (holiday)     Solutions 3  
5 15 Oct. Variable-length–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://moser-isi.ethz.ch/


Last modified: Wed Jan 16 12:38:50 UTC+8 2013