Information Theory

Announcements

★★★ 2025/08/06 ★★★ 

This course will be delivered as an EMI (English as a Medium of Instruction) course, in line with our government's bilingual education initiative. Lectures will be conducted primarily in English (approximately 75%) with supplementary explanations in Mandarin (approximately 25%) to enhance accessibility and support students in overcoming language barriers. All course updates will be posted on this webpage. The eCourse2 platform will be used for important announcements, uploading assignments, and distributing course materials. Please check this webpage regularly for the latest information. If you have any questions, feel free to contact me following the guidelines provided below.

Course Information

Instructor: Jian-Jia Weng

Time: Tuesdays and Thursdays, 2:45-4:00PM (F)

Location: R103, Innovation Building

Office and Office Hour: Upon request (please make an appointment before coming, see the following requirement of email format)

Teaching Method: Chalkboard Teaching

Main Reference: Thomas M. Cover and Joy A. Thomas, “Elements of Information Theory,” 2nd Ed, New Jersey: John Wiley & Sons, 2006 

Grading Policy: One Exam (35%, roughly in Week 10?), Homework Assignments (40%; 5% for each and you will get all marks as long as you submit it), One-Page Abstract (5%) + Oral Presentation (10%), In-Class Participation&Others (10%)

Contact Information

Office: R428, Innovation Building 

Campus Internal Phone Number：33528

Email: jjweng AT ccu.edu.tw

If you have any questions regarding the course and cannot reach me during office hours, you can email me with 

• Subject: [IT 2025] Inquiry - Your name and Student ID number (example: [IT 2025] Inquiry - 周杰倫 1234567)

• Contents: (1) topics you want to discuss and (2) your preferred time to meet in person (please specify at least 3 time slots). 

I should reply to your email within 24hours; if not, please send the email again.

Tentative Schedule

• Week 1  (09/09, 09/11): 

  1. Overview

  2. Shannon's Information Measures and Chain Rules

  3. Remark: The entropy H(X) can be thought of as a measure of the following things about X: (1) The average of "self-information" provided by the observation of X, (2) The uncertainty of X, and (3) The randomness of X.

• Week 2 (09/16, 09/18): HW#1 Due

  1. Convex Functions and Jensen's Inequality (and Log-Sum Inequality) 

  2. Information Inequalities

• Week 3 (09/23, 09/25): 

  1. Data Processing Inequality

  2. Sufficient Statistics

  3. Fano's Inequality

• Week 4 (09/30, 10/02): HW#2 Due

  1. Asymptotic Equipartition Property

  2. Lossless/Almost Lossless Data Compression

• Week 5 (10/07, 10/09): 

  1. Markov Processes

  2. Entropy Rates

• Week 6 (10/14, 10/16): HW#3 Due

  1. Example of Codes

  2. Kraft Inequality (for Prefix-free Codes)

  3. Optimal Code Meet Entropy

• Week 7 (10/21. 10/23): 

  1. Block-wise Encoding

  2. Converse Result to Lossless Data Compression

  3. Huffman Codes

  4. Shannon-Fano-Elias Codes

  5. Optimality of Huffman Codes

  6. Informational Channel Capacity

• Week 8 (10/28, 10/30): HW#4 Due

  1. Strongly/Weakly/Quasi/T Symmetric Channels

  2. Channel Coding Theorem (Definitions)

  3. Channel Coding Theorem (Converse Part)

• Week 9 (11/04, 11/06): Official Midterm Exam Week

  1. Channel Coding Theorem (Achievability Part)

• Week 10 (11/11. 11/13): HW#5 Due

  1. Capacity for Channels with Feedback

  2. Information Theory in Puzzles (Guessing Problems)

  3. Separate Source-Channel Coding Theorem

  4. Differential Entropy

• Week 11 (11/18, 11/20): 

  1. Relation of Differential Entropy to Discrete Entropy

  2. Differential Entropy of Gaussian Random Variable

  3. Gaussian Input Maximizes Differential Entropy

• Week 12 (11/25, 11/27): HW#6 Due

  1. Estimation Error and Differential Entropy

  2. Discrete-Time Gaussian Channels and Their Channel Capacity

  3. Bandlimited Channels (Continuous-Time Gaussian Channels) 

• Week 13 (12/02, 12/04): 

  1. Parallel Gaussian Channels

  2. Channels with Colored Gaussian Noise

• Week 14 (12/09, 12/11): HW#7 Due

  1. Scalar Quantization and Loyld-Max Algorithm

  2. Introduction to Rate Distortion Theory 

• Week 15 (12/16, 12/18): 

  1. Examples and Properties of Rate Distortion Functions

  2. Rate Distortion Theory Achievability & Converse Parts

• Week 16 (12/23, 12/25): Official Final Exam Week/HW#8 Due

  1. Computation of Channel Capacity and Rate-Distortion Functions

• Week 17 (12/30, 01/01): 

  1. Arithmetic Coding

  2. Maximum Entropy Principle

  3. Capacity Cost Function

  4. Duality of Source and Channel Coding

• Week 18 (01/06, 01/08): Presentation Session

Presentation List
Time: TBD
Location:  TBD
Abstract Due: TBD (eCourse2)

Homework Assignments

You need  to submit your answer sheet to each bi-weekly exercises (given in class) on eCourse2. Group discussions are encouraged. but you have to write the final answers by your own and submit it. Copy&paste is NOT allowed! I won't mark your answer sheet but will skim them to check your learning performance! 

• HW#1: 2.2-2.6, 2.10, 2.12, 2.14 (due: /, 23:59)

• HW#2: 2.19, 2.21, 2.23, 2.26, 2.33, 2.36 (due: /, 23:59)

• HW#3: 3.2, 3.4, 3.10, 3.13 (the second column of the table has typo; it is not sum to 1), 4.7, 4.11, 4.28  (due: /, 23:59)

• HW#4: 5.1, 5.6, 5.7, 5.14, 5.20, 5.30, 5.39 (due: /, 23:59)

• HW#5: 7,1, 7.2, 7.4, 7.5, 7.7, 7.8, 7.13, 7.18, 7.20, 7.34 (due: /, 23:59) 

• HW#6:  8.1, 8.5, 8.8, 8.9, 8.11 (due: /, 23:59) 

• HW#7: 9.1, 9.2, 9.5, 9.7, 9.15  (due: /, 23:59) 

• HW#8: 10.1, 10.2, 10.3, 10.5, 10.7  (due: /, 23:59) 

Reading Assignments

• Week 1: Skim Section 1 for a general idea, and read Sections 2.1-2.4

• Week 2: Sections 2.5-2.7

• Week 3: Sections 2.8-2.10

• Week 4: Section 3

• Week 5: Sections 4.1-4.3, 4.5

• Week 6: Sections 5.1-5.4

• Week 7: Sections 5.5-5.10

• Week 8: Section 7.1-7.6

• Week 9: Sections 7.7-7.13

• Week 10: Sections 8.1-8.6 

• Week 11: Sections 9.1-9.4

• Week 12: 

• Week 13: 

• Week 14: 

• Week 15:

• Week 16:

Potential Presentation Directions

The final presentation can either be a literature survey of a few information theory papers, or an original research idea. The project will be due towards the end of the semester. Some project directions are listed below:

• Universal source coding 

• Arithmetic coding

• Zero-error channel capacity

• MIMO channel capacity

• Capacity of channels with memory

• Algorithms for computing channel capacity and the rate-distortion function

• Bounds on the performance of block channel codes (error exponents)

• Low-density parity check (LDPC) codes or Polar codes

• Group Testing

• Quantum information theory

• Information theory and biology

References

1. F. Alajaji and P.-N. Chen, “An Introduction to Single-User Information Theory.” Singapore: Springer, 2018

2. S. Lin and D. J. Costello, “Error Control Coding,” Second Edition, Prentice Hall, 2004 (a classical book for data protection)

3. P.-N. Chen and S. Moser, "A Student's Guide to Coding and Information Theory," Cambridge, 2012 (suitable for general readers)

Additional Materials

• David Tse, Shannon Award Lecture: The Spirit of Information Theory, 2017

• David Tse, How Claude Shannon Invented the Future, Quanta Magazine, 2020 

• Natalie Wolchover, New Theory Cracks Open the Black Box of Deep Learning, Quanta Magazine, 2017

• David Mackay, Course on Information Theory, Pattern Recognition, and Neural Networks, Video Recordings

Fun Readings

• A Brief History of Information Theory

• Claude Shannon’s 1952 Lecture on Creative Thinking

• 3Blue1Brown, Solving Wordle Using Information Theory and Oh, wait, actually the Best Wordle Opener is not... 2022

• D. Bertsimas and A. Paskov, Optimal Wordle - An Exact and Interpretable Solution to Wordle, 2022

• R. H. Thouless, "The 12-balls problem as an illustration of the application of information theory," The Mathematical Gazette, vol. 54, no. 389, pp. 246-249, Oct. 1970. https://doi.org/10.2307/3613775

• Y. Dagan, Y. Filmus, A. Gabizon, and S. Moran, "Twenty (simple) questions," STOC, 2017. [Link]

• Y. Dagan, Y. Filmus, D. Kana, and S. Moran, "The entropy of lies: playing twenty questions with a liar," ITCS, 2021. [Link]

• The Shannon entropy of Sudoku matrices

• T. K. Moon, J. H. Gunther, and J. J. Kupin, "Sinkhorn solves Sudoku," IEEE Trans. Inf. Theory, vol. 55, no. 4, pp. 1741-1746, Apr. 2009. [IEEEXplore]

• J. H. Gunther and T. K. Moon, "Entropy minimization for solving Sudoku", IEEE Trans.  Signal Processing, vol. 60, no. 1, pp. 508-513, Jan. 2012. [IEEEXplore]

• C. Atkins and J. Sayir, "Density evolution for SUDOKU codes on the erasure channel", in Proc. Turbo Codes and Iter. Inf. Processing (ISTC), pp. 233-237, 2014.