• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Whenever you search in PBworks, Dokkio Sidebar (from the makers of PBworks) will run the same search in your Drive, Dropbox, OneDrive, Gmail, and Slack. Now you can find what you're looking for wherever it lives. Try Dokkio Sidebar for free.


Autumn 2011 IERG5154 Information Theory

Page history last edited by sidjaggi 10 years, 11 months ago

Welcome to IERG5154 Information Theory!


Final Paper 


Here are some official documents provided by the University. Please read them in advance.


Student/Faculty Expectations on Teaching and Learning



Academic honesty and plagiarism

Attention is drawn to University policy and regulations on honesty in academic work, and to the disciplinary guidelines and procedures applicable to breaches of such policy and regulations. Details may be found at http://www.cuhk.edu.hk/policy/academichonesty/ . With each assignment, students will be required to submit a statement that they are aware of these policies, regulations, guidelines and procedures.


Course Information


Instructor: Professor Sidharth (Sid) JAGGI



Calendar: http://calendar.jaggi.name



Office Hour: Monday 2:00-3:00, SHB729



Time and Location: T 2:30-5:15pm SHB 833


Learning resources for students

Recommended Textbooks (first two available in the CUHK Bookstore, third free online):

  1. Elements of Information Theory by T M Cover & J A Thomas, Wiley 2006
  2. Information Theory and Network Coding by Raymond W. Yeung, Springer 2008

    3. Lecture Notes on Network Information Theory by Abbas El Gamal & Young-Han Kim, 2010



Related courses

1. 1st Sem: IERG6120 (Network Information Theory)

2. 2nd Sem: IERG6130 (Network coding)



Course Title: IEG 5154 Information Theory

Description: The course aims to cover


  1. Fundamental definitions of information measure (entropy, conditional entropy, mutual information) and their properties.
  2. Lossless Source Coding/Data Compression -- theory and algorithms
  3. Channel Coding/Error-Correcting Codes/Coding theory
  4. Rate-distortion theory.
  5. Miscellaneous advanced topics depending on time and interest (Kolmogorov Complexity, Universal Portfolio Theory, Network Coding, ...)



Content, highlighting fundamental concepts (not necessarily in the chronological order we will use in classroom discussions)




Contents/fundamental concepts

  • Information theoretic quantities







  • Lossless source coding





  • Channel coding






  • Rate-distortion theory


  • Entropy, conditional entropy, mutual information, divergence, differential entropy, Markov/ergodic sources, properties (chain rules, positivity, convexity, Jensen's inequality, Fano's inequality, conditioning, data processing inequality, Law of large numbers, Sanov's theorem, AEP, entropy rates) 


  • Achievability and converse proofs, Kraft inequality, codes -- Shannon-Fano-Elias, Huffman, Arithmetic, Lempel-Ziv (universal codes)


  • Hamming codes, channel capacity (achievability and converse proofs), zero-error capacity, joint source-channel coding, feedback capacity, Gaussian channels (parallel channels, coloured noise)


  • Scalar/vector quantization, rate-distortion theorem (achievability and converse)


Learning outcomes:


  1. Demonstrate ability to manipulate basic information-theoretic quantities to prove relevant theorems.
  2. Demonstrate understanding of foundational topics in information theory, and an ability to use the theoretic tools required to prove corresponding theorems.
  3. Use the above to characterize and design information storage, manipulation and transmission systems.








Learning activities


Problem Sets

Online Activities (Scribe Notes/Discussion)




in class



in/out class



out of class



out of class





















M: Mandatory activity in the course

O: Optional activity

NA: Not applicable





Assessment scheme

Task nature



Problem sets


Scribe Notes

Class participation

Final Exam 

In-class problems, handed in next class

Collaborative homework

Scribe notes of a particular lecture

In-class discussion/Discussion on wiki


20% (8)

20% (4)

20% (2)




 Homework Policy: Answer all the questions according to the lecture progress and hand in them in the next class.      

The weekly problem set is cancelled.

Feedback for evaluation:

Class evaluations


Students are welcome to express their comments and suggestions via the following formal and informal feedback channels:



  • Two course evaluations. First one to be conducted in the middle of the term and the second one at the end of the term. Students are encouraged to provide specific comments and/or suggestions in addition to the numeric ratings.
  • At the end of each lecture there will be a single question feedback slip given to each student.
  • Students are also encouraged to provide feedbacks using informal channels, such as email/discussion to instructor/tutor, and via the talk pages on the class wiki.




Tentative Course Schedule (will edit as we go along)

Logistics/Introduction. Basic probability theory. Worst-case compression. Binary trees.  
Method of types, typical/atypical sets, sizes/probabilities, Sanov's Theorem 11.1-11.5, Cover/Thomas 

Sanov's Theorem -- Achievability/Converse of Source Coding Theorem

11.1-11.5, 2.1-2.6, 2.8, 2.10, Cover/Thomas 
Entropy definitions in terms of typical sets, properties.  11.1-11.5, 2.1-2.6, 2.8, 2.10, Cover/Thomas 
Properties of entropy-type functions. 2.1-2.6, 2.8, 2.10, Cover/Thomas
  Information-theoretic proof of Source Coding Theorem  7.1-7.7, 7.9, Cover/Thomas
Discussion of Channel Coding Theorem 7.1-7.7, 7.9 Cover/Thomas  
Proof of Channel Coding Theorem 7.6-7.7,7.9 Cover/Thomas 
Classifications and Properties of Per-Symbol Source Coding Schemes 5.1-5.5 Cover/Thomas
  Shannon Code, Huffman Code  5.6 Cover/Thomas 
Entropy Rates of a Stochastic Process  4 Cover/Thomas 
Arithmetic Codes, Weak Typicality  5.9, 13.3, 3 Cover/Thomas 






Lectures/Problem Sets/Homeworks/...






0  Background material


1.0 Problem Set 1 

     Scribe Note 1

     Scribe Note 1


2.0 Problem Set 2

     Scribe Note 2

     Scribe Note 2


3.0 Problem Set 3

     Scribe Note 3

     Scribe Note 3 

     Scribe Note 3 

     Scribe Note 3  

     Scribe Note 3


4.0 Problem Set 4

      Scribe_Note 4 

5.0 Problem Set 5

      Scribe Note 5 

      Scribe Note 5  


6.0 Problem Set 6

      Scribe Note 6

      Scribe Note 6

      Scribe Note 6 

      Scribe Note 6 


7.0 Problem Set 7

     Scribe Note 7 

     Scribe Note 7-1

     Scribe Note 7-2  


06 Sep


06, 13, 20 Sep




27 Sep




4 Oct

Basic probability theory


A simple (source) coding theorem




Entropy: Definitions and Properties




Source/Channel Coding Theorems







Symbol-by-symbol Source Coding


Memory/Universal (arithmetic) codes/Weak typicality/Differential entropy 




Coding theorems and coding theory                                              






Quantization/Rate distortion theory 





wang Limin




Paco Wong

Zirui Zhou



Manson Fong

Eric Chan 

Yiyong Feng

Wang Qike

Yuen Piu Hung 



JIANG Yunxiang


Lee Chin Ho

Yip Kit Sang Danny



Xihao Hu

Wanrong Tang





Luk Hon Tung

Tan Lu

Xixuan Wu


Homework 1

Homework 2

Presentation ideas

Homework 3

 30 Sep

 13 Oct

Last class

Due: 2011/10/18 2011HW1.pdf

Due: 2011/10/25    Homework2.pdf

Presentation in last class. Ideas

Due: 2011/12/02  IERG5154hw3.pdf






Important Announcements:







Homework 1
  2011/09/30     We update the description of problem 1 in   homework 1 
Lecture on 10/4
    We will have lecture on 2011/10/04
    The take-home final will start at 11:59 a.m. Friday, 2011/12/16. The duration is 24 hours.
Course Review
    We will have a class at 2 p.m.-5 p.m.  Thursday, 2012/12/08. Room833
  cheng fan

The final will last  for 72 hours from Friday noon (11:59 a.m.) to Monday noon (11:59 a.m.). 

It is open notes/book -- cover/thomas, closed internet/collaboration.



Scribe Notes Schedule:

Week Tuesday  

 Siyao, WANG Limin 



 Yang liu , Zirui Zhou, Chi Zhang, WONG Pak Kan

4  LEONG Ho Ka, CHAN Chun Lam, FONG Cheuk Man Manson
5  YE Jihang, FENG Yiyong
6  Yuen Piu Hung, Wang Qike, LIU Zhongchang
7   Yichao Li, Jiang Yunxiang
8   Yip Kit Sang Danny, Lee Chin Ho,
9  TANG Wanrong, YAO Leiyi, Hu Xihao
10  CAI Sheng, TU Jinlong ,Zhan Lei  
11  LU Lian, BI Suzhi Wu Xixuan, LU Tan
12   Luk Hon tung


Free help:

1. Learn how to use PBwiki: The PBwiki Manual

2. If you prefer video, watch a recording of our popular webinar, PBwiki 101: Your Guide to Wiki Basics.

3. Need more help? Sign up for a Free introductory webinar

4. Not So Short Introduction to LaTeX




Comments (14)

sidjaggi said

at 6:01 pm on Oct 4, 2011

Two comments/classes of comments stood out today.

One pointed out that the workload is perhaps unreasonable -- in particular, requiring every problem set to be turned in (in addition to scribe notes/homeworks/exam) is a lot.

henceforth, you don't need to turn in problem sets -- the grades for problem sets will be redistributed to the homeworks.

the second class of comments, which is a reprise of comments i've seen before as well, is that many of you would like me to also formally write down definitions/statements/theorems/etc.

valid point. my own style tends to be to wax eloquent about the intuition verbally, and get carried away, and forget to write things down. this can be a disadvantage when it comes to abstract concepts. i'll try to keep this in mind, but whenever i forget, i'm going to request that those of you who find this problem, please raise your hand and gently request that i write down the appropriate definition/formula/whatever...

others liked the review/intuition/etc. i liked that you liked it :)

thanks for the feedback, and please keep it coming!

sidjaggi said

at 10:30 pm on Oct 5, 2011

On further thought, instead of jus cancelling the problem sets, we'll substitute it with a two-hour in-class mid-term on the 25th of October.

Shiney Wanrong TANG said

at 5:03 pm on Oct 10, 2011

Dear prof,

Actually, most of us would prefer to hand in problem sets rather than have a mid-term exam. In addition, we have already handed in two or three sets.


ZhanLei_Jacky said

at 5:08 pm on Oct 10, 2011

Hmm, I think so, too~~

ZhanLei_Jacky said

at 6:00 pm on Oct 10, 2011

I mean I prefer problem sets~~

Jiang Yunxiang said

at 6:54 pm on Oct 10, 2011

I agree

sidjaggi said

at 1:46 am on Oct 11, 2011

hmm, ok, let's do it this way. Those who prefer problem sets can continue to do problem sets instead of the midterm. Those who prefer the mid-term can do the midterm in lieu of the problem set. You have to (in-class) tell the TA which you'd prefer.
The midterm will nonetheless occur on the 25th (since I'm traveling that week anyway, and will not be able to teach then -- the TA will do a 45-minute in-class review session, followed by a 2 hour midterm for those who want it).

sidjaggi said

at 1:48 am on Oct 11, 2011

Also, even if you choose the midterm, but like turning in problem sets since they give you more practice, we'd be happy to look at them and grade them for you (without those grades changing your score).

Chin Ho Lee said

at 5:19 pm on Oct 10, 2011

I'd prefer midterm...

sidjaggi said

at 2:36 pm on Oct 7, 2011

A mistake, and a glaring omission, in my discussion on Tuesday. Anyone who emails me with both before the next class gets an automatic grade bump... ;)

Yip Kit Sang Danny said

at 12:04 pm on Dec 16, 2011

Where is the final exam paper?

sidjaggi said

at 2:03 pm on Dec 16, 2011

Just updated Q1 of final to make part a easier (1400 hours Friday)

Xihao said

at 3:17 pm on Dec 16, 2011

For question 1:
Where does the F_2 come from?
Whether c is positive or negative in formula 1-2^{c|m-n|}?
Three sub-questions have point 2, point 3 and point 3, but their sum is 7 points!

sidjaggi said

at 5:02 pm on Dec 16, 2011

Thanks for pointing those out. Updated question paper with corresponding (minor) changes. In particular:
1. F_2 is the binary field. As the question says, your are expected to use a binary linear code.
2. c is positive.
3. Good point(s :) Corrected. Total points now 8.

You don't have permission to comment on this page.