|Lectures||Monday||11:00 – 13:00 (Room: BC01)|
|Tuesday||13:00 – 15:00 (Room: ELA 2)|
|Exercises||Tuesday||15:00 – 17:00 (Room: ELA 2)|
|Credits :||7 ECTS|
See the course information.
Midterm Exam (40%)
- Midterm date: 29 October, Place: ELA2 and DIA 004.
- Closed book, closed notes.
- ONE two-sided A4 cheat sheet allowed.
Graded Homework (10%)
- Due Tuesday, December 3, at the beginning of the exercise session. You can prepare handwritten or typewritten sheets for the solutions.
Final Exam (50%)
- Final date: 18 January, 08.15-11.15, Place: CE4.
- Closed book, closed notes.
- TWO two-sided A4 cheat sheet allowed.
|Sep 16||Public Holiday|
|Sep 17||– Introduction to Source Coding
– Non-singular codes
– Uniquely decodable codes
– Prefix-free codes
– Kraft’s inequality for prefix-free codes
– Kraft’s sum for products of codes
|Sep 23||– Kraft’s inequality for non-singular codes
– Kraft’s inequality for uniquely decodable codes
– Reverse Kraft’s inequality
– Expected codeword length
– Entropy as a lower-bound to the expected codeword length
– Existence of prefix-free codes with expected length at most entropy + 1
– Properties of optimal codes
– Huffman procedure
– Equivalence of prefix-free codes and strategies for guessing via binary questions
– Entropy of multiple random variables
– Source coding by describing words of n letters
– Conditional entropy and mutual information
– Chain Rules for entropy and mutual information
– Short reminder for Markov Chains
– Minimal and maximal values of H(U)
– Data Processing inequality
– Entropy Rate
– Entropy rate of Stationary Processes
– Coding Theorem for Stationary Sources
– Fixed-to-Fixed Length Source Codes
– Properties of Typical Sets
– Asymptotic Equipartition Property
|Oct 07||– Source Coding via Typicality
– Finite state machine (FSM) compressors
|Oct 08||-Invertible machines, information lossless (IL) machines
– Lower bound to the output length for IL FSMs
|Oct 14|| (Lecture by Ruediger Urbanke)
– Communication channels
– memoryless/stationary channels, communication without feedback
– C(W) = max I(X;Y), examples with binary erasure channel and binary symmetric channels
-Multi-letter Fano’s Inequality
|Oct 15||(Lecture by Ruediger Urbanke)-Weak converse of noisy channel coding theorem
-The necessity part of KKT condition for capacity achieving input distribution.
|Oct 21||-Review of the last lecture
-The sufficiency part of KKT condition for capacity achieving input distribution.
-Computation of capacity C(W).
|Oct 22||-Information Lossless machines cont.
-Lempel Ziv Algorithm
|hw6.pdf||sol6.pdf||Some old midterm exams|
|Oct 28||– Channel coding theorem
– Channels with input cost
– Proofs by random constructions
|Nov 4||Exercise session
|Nov 5||-Differential Entropy
-Properties of Differential Entropy
|Nov 11||-Relationship between H(X) and h(X)
-Entropy of Gaussian R.Vs
-Capacity of Gaussian Channel
|Nov 12||-Parallel Gaussian Channels, water-filling
-Bandlimited AWGN Channels
|Nov 18||– Hamming codes- Hamming weight
– Hamming distance
|Notes on coding|
|Nov 19||– Sphere-packing bound- Gilbert bound
– Singleton bound
– Linear codes
– Generator and parity check matrices
|Nov 25||– Polar Codes|
|Nov 26||– Polar Codes||hw10.pdf||sol10.pdf|
|Dec 2||– Polar Codes|
|Dec 3||-Rate-Distortion Theory||hw11.pdf||sol11.pdf|
|Dec 9||-Rate-Distortion Theory|
|Dec 10||-Slepian-Wolf Coding||hw12.pdf||sol12.pdf|
|Dec 16||-Multiple Access Channels (MAC) (Achievability)|
|Dec 17||-Multiple Access Channels (MAC) (Converse)||hw13.pdf||sol13.pdf|
|Jan 18||Final Exam||Final||Final Sol|
T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley 2006.
Additional Reading Material
- C. E. Shannon, A Mathematical Theory of Communications, Bell System Technical Journal, 1948.
Notes on Tunstall Coding.
Notes on Lempel-Ziv Algorithm
To Review Basic Probability Theory
K. L. Chung, A Course in Probability Theory, Academic Press.
W. Feller, An Introduction to Probability Theory and Its Applications, Wiley.
G. Grimmett and D. Stirzaker, Probability and Random Processes, Oxford University Press.
A. Papoulis, Probability, Random Variables, and Stochastic Processes, McGraw-Hill.
S. M. Ross, A First Course in Probability, Pearson Education.