Course Outline
This is a tentative outline of the
contents of the lectures.
- 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
- 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
Last modified Oct 24, 2001