• 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

last edited by 12 years, 8 months ago

## IEG5154 Information Theory

Semester: Spring 2009

 Course Title: IEG 5154 Information Theory Description: The course aims to cover   Fundamental definitions of information measure (entropy, conditional entropy, mutual information) and their properties. Lossless Source Coding/Data Compression -- theory and algorithms Channel Coding/Error-Correcting Codes/Coding theory Rate-distortion theory. 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:   Demonstrate ability to manipulate basic information-theoretic quantities to prove relevant theorems. Demonstrate understanding of foundational topics in information theory, and an ability to use the theoretic tools required to prove corresponding theorems. 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 Homeworks Scribe Notes Class participation Final Exam In-class problems, handed in next class Collaborative homeworks Scribe notes of a particular lecture In-class discussion/Discussion on wiki Examination 20% (8) 20% (4) 20% (2) 15% 25%

Learning resources for students

 Recommended Textbooks (first two available in the CUHK Bookstore, third free online): Elements of Information Theory by T M Cover & J A Thomas, Wiley 2006 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

Feedback for evaluation:

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 5 Jan Logistics/Introduction. Worst-case compression. Binary trees. 9 Jan Method of types, typical/atypical sets, sizes/probabilities, Sanov's Theorem 11.1-11.5, Cover/Thomas 12 Jan Sanov's Theorem -- Achievability/Converse of Source Coding Theorem 11.1-11.5, 2.1-2.6, 2.8, 2.10, Cover/Thomas 16 Jan Entropy definitions in terms of typical sets, properties. 11.1-11.5, 2.1-2.6, 2.8, 2.10, Cover/Thomas 19 Jan Properties of entropy-type functions. 2.1-2.6, 2.8, 2.10, Cover/Thomas 23 Jan Information-theoretic proof of Source Coding Theorem 7.1-7.7, 7.9, Cover/Thomas 2 Feb Discussion of Channel Coding Theorem 7.1-7.7, 7.9 Cover/Thomas 6 Feb Proof of Channel Coding Theorem 7.6-7.7,7.9 Cover/Thomas 9 Feb Classifications and Properties of Per-Symbol Source Coding Schemes 5.1-5.5 Cover/Thomas 13 Feb Shannon Code, Huffman Code 5.6 Cover/Thomas 20 Feb Entropy Rates of a Stochastic Process 4 Cover/Thomas 23 Feb Arithmetic Code, Weak Typicality 5.9, 13.3, 3 Cover/Thomas

Teachers’ or TA’s contact details

 Professor/Lecturer/Instructor: Name: Prof. Sidharth Jaggi Office Location: SHB Room 706 Telephone: 2609-4326 Email: jaggi [AT] ie {dot} cuhk {dot} edu {dot} hk Teaching Time and Venue: Mon 11:30am to 1:00pm, (ELB 202), Fri 3:30pm to 5:00pm, (ERB 703). Website: http://ieg5154.pbwiki.com Other information: Office Hours: by appointment

Teaching Assistant/Tutor:

Name:

#### Mr. Cho Yiu Ng (Michael)

Office Location:

SHB Room 826A

Telephone:

2609-8383

Email:

michaelng [AT] ieee {dot} org

Website:

http://ieg5154.pbwiki.com

Other information:

Office Hours: Thu 5:30pm-6:15pm

A facility for posting course announcements

 Course announcements and materials will be posted on the course wiki https://ieg5154.pbwiki.com

 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.

#### MEI Yuchen said

at 4:43 pm on Jan 6, 2009

Do we have tutorial class?

#### Cho Yiu Ng said

at 7:36 pm on Jan 6, 2009

No. But I reserve Thursday 5:30pm-6:15pm to be the office hour for this course. I'll be in my office to offer any helps for this course.

#### sidjaggi said

at 7:46 pm on Jan 6, 2009

Also, you're welcome to make appointments via email to see me or Michael any time you have problems that can't be dealt with in/immediately after class. My calendar is at http://calendar.jaggi.name