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

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

Autumn 2011 IERG5154 Information Theory

This version was saved 12 years, 3 months ago View current version     Page history
Saved by lt010@...
on December 9, 2011 at 1:23:38 pm
 

Welcome to IERG5154 Information Theory!

 

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

 

Student/Faculty Expectations on Teaching and Learning

http://www.erg.cuhk.edu.hk/erg-intra/upload/documents/StaffStudentExpectations.pdf

 

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

jaggi@ie.cuhk.edu.hk

http://staff.ie.cuhk.edu.hk/~sjaggi/

Calendar: http://calendar.jaggi.name

TA: Fan CHENG,

cf008@ie.cuhk.edu.hk

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)

 

 

Topic

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

Lecture

Problem Sets

Online Activities (Scribe Notes/Discussion)

Homeworks

 

 

(hr)
in class

 

 

(hr)
in/out class

 

 

(hr)
out of class

 

 

(hr)
out of class

36

 

 

0

36

12

12

6

15

0

M

 

 

O

M

O

M

O

M

O

M: Mandatory activity in the course

O: Optional activity

NA: Not applicable

 

 

 

 

Assessment scheme

Task nature

Description

Weight

Problem sets

Homework

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

Examination 

20% (8)

20% (4)

20% (2)

15%

25% 

 

 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)

DATE TOPIC READINGS
 
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/...

 

Item

Date

Topic

Author

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-1 Scribe Note 7-1  

 

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 

 

Sid

 

Sid

wang Limin

siyao

 

Sid

Paco Wong

Zirui Zhou

 

Sid

Manson Fong

Eric Chan 

Yiyong Feng

Wang Qike

Yuen Piu Hung 

 

Sid

JIANG Yunxiang

Sid

Lee Chin Ho

Yip Kit Sang Danny

 

Sid

Xihao Hu

Wanrong Tang

Lei ZHAN

CAI SHENG

 

Sid

Luk Hon Tung

 

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

 Sid

chengfan

Sid

chengfan

  

Important Announcements:

 

Item

Date

Topic

Author

Details

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

 

Scribe Notes Schedule:

Week Tuesday  
1  
 
2

 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 (0)

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