Information Theory
Fall 2016

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.

• [01.06]
  Policy of the final exam is posted.
• [12.23]
  P2 and P3 of HW5 is modified. Please donwload the updated version V1.
• [12.23]
  Homework 5 is posted. It is due on 01.04 in class.
• [12.20]
  Lecture 08 and updated Lecture 07 are posted. Please download the latest version before attending the class on 12/21.
• [12.08]
  Homework 4 is posted. It is due on 12.21 in class.
• [11.23]
  Midterm problems are posted. We will discuss about them on 11/30.
• [11.15]
  A sample of the midterm is posted. We will discuss about it in class on 11/16.
• [11.13]
  Minor typo fixed for HW3.
• [11.13]
  Policy of the midterm exam is posted.
• [11.13]
  Please fill out the poll by 11/15 and give us some feedback.
• [11.09]
  Hint for HW3 is posted.
• [11.05]
  HW3 is now due on 11.16 in class per students' request.
• [10.27]
  Homework 3 is posted. It is due on 11.09 in class.
• [10.22]
  For Problem 5 of HW2, the hint is slightly modified. See the updated V1 below (a footnote added).
• [10.18]
  Hint for HW2 is posted.
• [10.12]
  Homework 2 is posted. It is due on 10.26 in class.
• [09.30]
  Submission of homework is free-format. LaTeX is required only when you are assigned to make a detailed solution.
• [09.30]
  Hint for HW1 is posted; Problem 5 a) of HW1: m should be at least 2. See the updated V1 below.
• [09.21]
  Homework 1 is posted. Problem 1,2,3,5 are due on 10.05 in class. Problem 4 is due on 10.12 in class.
• [08.31]
  The location of the lecture is changed to BL-114 (博理館114室).
• [08.24]
  Welcome! Please see the Resources section to get an idea about what the course looked like in the past.
  The loading this semester, however, should be lighter than Fall 2015, and the syllabus will also be slightly different. Please attend the first lecture on 9/14 to find out what's new.

• 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:
  BL-114 (博理館114室), Time: Wednesday 09:10 - 12:10
• Teaching Assistant:
  Wei-Ning Chen (陳偉寧), r05942078 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.
  7. Y. Polyanskiy and Y. Wu, Lecture notes on Information Theory, MIT (6.441), UIUC (ECE 563), 2012-2016. Link
• Prerequisites:
  Probability, Linear Algebra.
• Grading:
  Homework (30%), Midterm (30%), Final (40%).

• Lecture 00: Introduction
    Slide: [09.13] V0
• Lecture 01: Measures of Information
    Slide: [09.13] V0 [09.15] V1 [09.21] V2
    Reading: Ch 2, Cover&Thomas[1] or Ch 1, Moser[4]
    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 02: Lossless Source Coding
    Slide: [10.02] V0
    Reading: Ch 3,4, Cover&Thomas[1] or Ch 5,19.1-19.8, Moser[4]
    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.28. 4.29, 4.30
• Lecture 03: Noisy Channel Coding
    Slide: [10.18] V0
    Reading: Ch 7, Cover&Thomas[1] or Ch 9, Moser[4]
    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 04: Lossy Source Coding
    Slide: [11.01] V0 [11.05] V1
    Reading: Ch 10, Cover&Thomas[1]
    Selected exercises from Cover&Thomas: 10.2, 10.6, 10.10, 10.14, 10.17, 10.19
• Lecture 05: Continuous-Valued Sources and Channels
    Slide: [11.05] V0
    Reading: Ch 8,9, Cover&Thomas[1] or Ch 15,16, Moser[4]
    Selected exercises from Cover&Thomas: 8.1, 8.6, 8.8, 9.3, 9.4, 9.7, 9.9, 9.15, 9.17, 9.20, 9.21, 10.8
• Lecture 06: Polar Coding
    Slide: [11.13] V0 [12.04] V1
    Reading: Ch 12, Moser[4]. See Resources for more information.
• Lecture 07: Introduction to Statistical Decision Theory
    Slide: [12.14] V0 [12.20] V1
• Lecture 08: Hypothesis Testing
    Slide: [12.20] V0 [12.21] V1
    Reading: Ch 12-15, Polyanskiy&Wu[7].

• Homework 1 Due: 10.05 in class. Problem 4 is due on 10.12 in class.
    Problems: [09.21] V0 [09.30] V1
    Hints: [09.30] V0
    Solutions: V0 Contributed by b02901179, b02901076, t05902116, r05942076, b02901023.
• Homework 2 Due: 10.26 in class.
    Problems: [10.12] V0
    Hints: [10.18] V0 [10.22] V1
    Solutions: V0 Contributed by b02901178, b02901030, r05942013, r05942034, r05942058.
• Homework 3 Due: 11.16 in class.
    Problems: [10.27] V0
    Hints: [11.09] V0
    Solutions: V0 Contributed by b03901045, b02901052, r05921076, r04921050, b03901158.
• Homework 4 Due: 12.21 in class.
    Problems: [12.08] V0
    Hints:
    Solutions: V0 Contributed by r05921031, b03901030, b02901119, r05942059, r05942096.
• Homework 5 Due: 01.04 in class.
    Problems: [12.23] V0 [12.26] V1
    Hints:
    Solutions: V0 Contributed by b04901116, b02901028, b02901047, r05942119, r04942097, b02901027

• Midterm 11/23 in class (09:10 – 12:10).
    Range: Lecture 1-5, Homework 1-3.
    Logistics: [11.13] Policy. [11.15] Sample. [11.23] Exam.
• Final 1/11 in class (09:00 – 12:30 [tentative]).
    Range: Lecture 1-8, Homework 1-5.
    Logistics: [01.06] Policy. [01.11] Exam.

• Information Theory, Fall 2015. Advices from the Class of Fall 2015 can be found here.
• Network Information Theory, Fall 2014
• Arikan's first paper on polar codes
• A simple proof of polarization (By Alsan and Telatar)
• On the rate of channel polarization (By Arikan and Telatar)