---

Course Outline

---

• Lecture 1. 09/04
  • Course information; historical overview of the origins of information theory; coin flips and entropy.

• Lecture 2. 09/06
  • Entropy, conditional entropy, relative entropy, mutual information. Examples.

• Lecture 3. 09/11
  • Chain rules. Jensen's inequality, log-sum inequality. Inequalities for entropy, mutual information, and relative entropy.

• Lecture 4. 09/13
  • Data processing inequality, Fano's inequality, entropy and the "Asymptotic Equipartition Property" (AEP).

• Lecture 5. 09/18
  • Lossless data compression. Fixed-rate codes and the AEP. Variable-rate codes and decodability: Non-singular, uniquely decodable, and instanteneous codes.

• Lecture 6. 09/20
  • More on variable-rate codes. Kraft inequality; variable-rate compression and entropy; the Shannon code; the "entropy rate."

• Lecture 7. 09/25
  • More on variable-rate codes: Optimal codes, Huffman coding, 20 questions, Huffman vs. Shannon. Optimality of Huffman codes.

• Lecture 8. 09/27
  • More on variable-rate codes: Idealized Shannon codes, mismatched coding, competitive optimality.

• Lecture 9. 10/02
  • Gambling and data compression.

• Lecture 10. 10/04
  • More on gambling. Intro to channel coding and channel capacity.

• Lecture 11. 10/09
  • The channel coding theorem. Channel capacity evaluation.

• Lecture 12. 10/11
  • Random coding: Proof of the direct coding theorem.

• NO CLASS ON 10/16

• IN-CLASS MIDTERM ON 10/18

• Lecture 13. 10/23
  • Fano's inequality, and the converse to the channel coding theorem.

• Lecture 14. 10/25
  • Zero-error codes, capacity of symmetric channels, source/channel separation theorem.

• Lecture 15. 10/30
  • Proof of converse for the source/channel separation theorem. Error correcting codes: Hamming codes, linear codes.

• Lecture 16. 11/01
  • Feedback capacity.

• Lecture 17. 11/06
  • Continuous random variables: Differential entropy, joint and conditional entropy, relative entropy, mutual information; the AEP.

• Lecture 18. 11/08
  • Properties of differential entropy, joint and conditional entropy, relative entropy, mutual information; maximum entropy distributions.

• Lecture 19. 11/13
  • Gaussian channels: Power constraints, capacity, converse to the coding theorem.

• Lecture 20. 11/15
  • Outline of direct coding theorem proof. The "hat problem." Lossy data comression, quantization.

• 11/20 - NO CLASS

• Lecture 21. 11/27
  • Lossy data compression: rate vs distortion, the rate-distortion function.

• Lecture 22. 11/29
  • Proof of the coding theorem.

• Lecture 23. 12/04
  • Introduction to Kolmogorov complexity

• Lecture 24. 12/06
  • Information and the brain