Information Theory
Fall 2015

Information Theory is a senior (undergraduate) level course designed for students who are interested in the quantitative fundamental limits of information. What is information and how to quantify information? What is the ultimate data compression rate and what is the ultimate transmission rate of communication? In this course, we introduce the fascinating theory originated from Claude E. Shannon, which addresses the above fundamental questions in communication theory. We will develop methods and coding techniques to achieve these fundamental limits. Finally, we will also demonstrate the application of information theory to other fields, including statistics (hypothesis testing and estimation) and statistical inferences.

• (1/8) More information about the final exam is posted. Please check the policy of the final exam. In particular, you are allowed to bring two A4-size cheat sheet (single-sheet, double-sided).
• (1/5) We post some resources on polar codes. Please check.
• (12/24) Homework 6 is posted. Please download the findal version - we made some changes in Problem 1.
• (12/19) Homework 6 (draft) is uploaded. Please take a look and let me know if there is any issue. Final version will be posted on 12/24.
• (12/19) Please fill in the poll, decide the topic of the last lecture and the form of the final exam, and give us feedback.
• (12/14) We rearrange the materials of Lecture 08, and split them into Part I and II. Please download the new versions.
• (12/9) Homework 5 is posted. Please download the findal version.
• (12/6) Homework 5 (draft) is uploaded. Please take a look and let me know if there is any issue. Final version will be posted on 12/8.
• (12/2) Review your midterm exam sheets on 12/3. Time: 12:30 – 14:00. Location: MD-205 (明達館205室). If you cannot make it, send us an email so that we can schedule another slot before 12/8.
• (11/24) Slides of the guest lecture by Vincent Tan is posted.
• (11/18) The regular lecture on 11/24 is canceled. Instead, we will have a guest lecture on "Second-Order Asymptotics in Information Theory", delivered by Vincent Tan from National University of Singapore. Please attend this lecture.
• (11/18) Midterm exam problems are posted. We will discuss them on 11/25.
• (11/13) Solution to HW2 and HW3 are posted.
• (11/12) Sample Midterm is posted. We will discuss the problems on 11/17 in class.
• (11/11) Problem 4 of the original Homework 4 is removed since some students have no knowledge about optimal signal detection under Gaussian noise. Please download the new version.
• (11/10) Homework 4 is posted. Please download the findal version - a lot of changes have been made.
• (11/6) Homework 4 (draft) is uploaded. Please take a look and let me know if there is any issue. Final version will be posted on 11/9.
• (10/26) Homework 3 is posted. Please download the findal version.
• (10/26) Solution to HW1 is posted.
• (10/26) We expand the slides of Lecture 4 to include the topic "channel coding with input cost". Please download the latest version.
• (10/22) Homework 3 (draft) is uploaded. Please take a look and let me know if there is any issue. Final version will be posted on 10/26.
• (10/19) Homework 2 is slightly updated: (1) Problem 5 b) of Homework 2 will not be graded - an assumption was missing. (2) Additional hints for Problem 3 b) and 6 b) are posted. Please see the updated version here. Check the text with blue color for the modification.
• (10/15) Please fill in the poll and give us some feedback.
• (10/15) A typo on Slide #22 in Lecture 3 is fixed.
• (10/12) Homework 2 is posted. Please download the findal version.
• (10/8) Homework 2 (draft) is uploaded. Please take a look and let me know if there is any issue. Final version will be posted on 10/12.
• (9/28) Homework 1 is posted. Please download the findal version.
• (9/22) Homework 1 (draft) is uploaded. Please take a look and let me know if there is any issue. Final version will be posted on 9/28.
• (8/25) Welcome!

• Instructor:
  I-Hsiang Wang (王奕翔), ihwang AT ntu DOT edu DOT tw
• Office Location and Office Hours:
  MD-524 (明達館524室), Time: Monday and Tuesday 17:00 - 18:00.
• Lecture Room and Lecture Hours:
  EE2-225 (電機二館225室), Time: Tuesday 13:20 - 14:10 and Wednesday 10:20 - 12:10
• Teaching Assistant:
  Yao-Shan Hsiao (蕭樂山), r04942043 AT ntu DOT edu DOT tw
  Office hour: Monday and Thursday 13:00 - 14:00, BL-524 (博理館524室)

• References:
  
  1. T. Cover and J. Thomas, Elements of Information Theory, 2nd Edition, Wiley-Interscience, 2006.
  2. R. Gallager, Information Theory and Reliable Communications, Wiley, 1968.
  3. I. Csiszar and J. Korner, Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd Edition, Cambridge University Press, 2011.
  4. S. M. Moser, Information Theory (Lecture Notes), 4th edition, ISI Lab, ETH Zürich, Switzerland, 2014. Link
  5. R. Yeung, Information Theory and Network Coding, Springer, 2008.
  6. A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011.
• Prerequisites:
  Probability, Linear Algebra.
• Grading:
  Homework (35%), Midterm (30%), Final (35%).

• Lecture 01 Introduction: Version 0 (8/25), Version 1 (9/15)
• Lecture 02 Measures of Information (Reading: Ch 2, Cover&Thomas[1]; Ch 1, Moser[4]):
  Version 0 (9/15), Version 1 (9/22), Version 2 (9/25)
  Selected exercises from Cover&Thomas: 2.4, 2.10, 2.14, 2.15, 2.17, 2.26, 2.27, 2.30, 2.39, 2.48
• Lecture 03 Lossless Source Coding (Reading: Ch 3,4, Cover&Thomas[1]; Ch 5,19.1-19.8, Moser[4]):
  Version 0 (9/25), Version 1 (10/8; typo fixed 10/15)
  Selected exercises from Cover&Thomas: 3.2, 3.4, 3.9, 3.10, 3.11, 3.13, 4.2, 4.6, 4.7, 4.9, 4.11, 4.14, 4.18, 4.26, 4.28. 4.29, 4.30
• Lecture 04 Noisy Channel Coding (Reading: Ch 7, Cover&Thomas[1]; Ch 9, Moser[4]):
  Version 0 (10/8), Version 1 (10/26)
  Selected exercises from Cover&Thomas: 7.3, 7.5, 7.8, 7.11, 7.12, 7.13, 7.18, 7.20, 7.23, 7.28
• Lecture 05 Measures of Information for Continuous R.V. (Reading: Ch 8, Cover&Thomas[1]; Ch 15, Moser[4]):
  Version 0 (10/26)
  Selected exercises from Cover&Thomas: 8.1, 8.6, 8.8
• Lecture 06 Channel Coding over Continuous Channels (Reading: Ch 9, Cover&Thomas[1]; Ch 16-18, Moser[4]):
  Version 0 (11/2), Version 1 (11/3), Version 2 (11/9), Version 3 (11/10)
  Selected exercises from Cover&Thomas: 9.3, 9.4, 9.7, 9.9, 9.15, 9.17, 9.20, 9.21
• Guest Lecture by Vincent Tan Second-Order Asymptotics in Information Theory: Slides (11/24)
• Lecture 07 Lossy Source Coding (Reading: Ch 10, Cover&Thomas[1]):
  Version 0 (11/30), Version 1 (12/2), Version 2 (12/9)
  Selected exercises from Cover&Thomas: 10.2, 10.6, 10.8, 10.10, 10.14, 10.17, 10.19
• Lecture 08 Part I Information Theory and Statistics: Method of Types and Large Deviations
  (Reading: Ch 11.1, 11.2, 11.4, 11.5, Cover&Thomas[1]): Version 0 (12/14); Version 1 (12/15)
  Selected exercises from Cover&Thomas: 11.5, 11.13, 11.14, 11.18
• Lecture 08 Part II Information Theory and Statistics: Hypothesis Testing and Estimation
  (Reading: Ch 11.7-11.10, Cover&Thomas[1]): Version 0 (12/14); Version 1 (12/22); Version 2 (12/22); Version 3 (12/23)
  Selected exercises from Cover&Thomas: 11.1, 11.6, 11.7, 11.8, 11.9, 11.11, 11.17, 11.19
• Lecture 09 Polar Coding (Reading: Ch 12, Moser[4]):
  Version 0 (12/29); Arikan's Slides; Telatar's Slides. See Resources for more information.

• Homework 1: Due: 10/7.
  Solution to HW1. Contributed by B01902046, R04942057, B01901107, B01901135, R03942043, B01902066
• Homework 2: Due: 10/21.
  Solution to HW2. Contributed by B01901146, R04942103, B02901056, R03942058, B01209024, B02901062
• Homework 3: Due: 11/06.
  Solution to HW3. Contributed by B01901113, B01901044, B02901088, B01901020, R04942048, R04942046
• Homework 4: Due: 11/20.
  Solution to HW4. Contributed by R04942106, R03942118, R03942063, R03942066, B01901049
• Homework 5: Due: 12/18.
  Solution to HW5. Contributed by B01901018, R03942039, B01901099, B03901027, R04942032
• Homework 6: Due: 1/6.
  Solution to HW6. Contributed by B01901009, B01901193, B02901016, B01901091, R03942059

• Midterm: 11/18 in class.
  Range: Lecture 1-6, Homework 1-4.
  Policy. Sample Midterm. Problems. Statistics.
  Solution. Contributed by R02941088, B00901094, R03942138, R03922125
• Final: 1/13, 09:10 - 12:10, EE2-225.
  Range: Lecture 1-9, Homework 1-6.
  Policy. Problems.

• Network Information Theory, Fall 2014
• Arikan's first paper on polar codes
• On the rate of channel polarization (By Arikan and Telatar)
• A simple proof of polarization (By Alsan and Telatar)